【6】js字典与散列表的实现-JavaScript学习数据结构

字典、散列表、JavaScript对象的关系

在集合中，只关心值，即以[值，值]对的形式来储存数据。而字典、散列表、对象都是以[键，值]对的形式来存储数据。在数组中，也是以键值对的形式来存储数据，不过数组中的“键”为“索引”而已，我们都知道在JavaScript中，数组也是一种对象。所以，这里就不讨论数组了。而是说字典、散列表、JavaScript对象（里面包括数组），这三者的关系。

它们都是以键值对的形式来存储数据，好像是一个东西， 但又不是一个东西，似乎比较乱，这里是说自己目前的理解。

• 通过散列函数将键值对应键，键值关系存放在散列表中，可以通过数组进行设计（键映射为数组中的索引）
• 散列表是字典的一种实现方式，可以用散列表来实现字典
• JavaScript的对象是以字典的形式设计的

所以，散列是一种技术，散列得到的是散列表，散列表是字典的一种实现方式，而JavaScript对象是以字典的形式设计的。所以不严谨的说，JavaScript中的对象就是一种字典数据结构，JavaScript中的对象就是一种散列表数据结构（只不过散列函数是语言内置了，不需要自己去设计）。核心都是键值对这种存储数据的方式，然后就是理解何为过程，何为结果，是什么实现了什么。具体名称与叫法，这里初学不用钻牛角尖，重要的还是自己理解了多少。

理解“散列表的一步查找”

const arr = ['cat', 'dog', 'pig'];
复制代码

数组具有的特点是“一步访问”，即通过给索引值，得出具体值的过程只需要一步，也就是说arr[1]得出等于‘dog’的过程只需要一步，只有数组占据连续的内存格子，以及电脑能够一步访问具体的内存地址决定。但是数组的“查找”是O(n),即要想找到arr中“dog”元素的索引,是需要数组从arr[0]开始遍历的。

我们也知道数组也是对象，那么其也应该具有“散列表的一步查找”特点。也可以这么说，不过数组的“键”即位索引，那么数组的“一步查找”就是arr.”1″ = “dog”过程是一步的，但是对象的键“1”（数组对象中‘键’，‘属性’，‘索引’指的是同一东西），不能这么写，在JavaScript中得写成arr[1]，这样就成了上面讲的“数组具有一步访问”。所以，这里都是不矛盾的，关键是如何看待“访问”和“查找”。

const Bob = {
    name: 'Bob',
    age: 20,
    gender: male,
    city: 'Shenzhen'
}
复制代码

“散列表的一步访问”,以JavaScript的对象为例，通过给定“键”（属性）为“age”，就可以一步得出“值”为20；即Bob.age = 20的过程是一步的。在众多的数据中，只要给定一个“键”，那么就能一步找出对应的“值”，这就是散列表的快速查找的特点。试想这些数据保持在数组中（理论上来说当然可以），那么我如果想要获取Jack的生日，那么需要对数组举行遍历，找到包含Jack的这个数组（若用数组寸这些信息，那必定是多维数组）中找到子数组的生日信息，再找到里面的生日。数据越复杂，这个过程越麻烦。如果是散列表保持这些数据的话，只需要给定“键”为birthday，通过Jack.birthday就可以一步得出生日信息。

散列表如果实现一步查找

首先，“散列”是一种技术，将键值对进行对应，存与散列表中。在具体用实现过程中，存放最后键值对的地方为数组，其中索引就对应“键”，两者通过散列函数匹配。一个非常好的例子就是“查电话簿”，我们不需要记住负责的电话号码，只需要通过“查电话簿”，就可以将名字与电话号码对应起来。于是，我们只需要拨打“二哥”就相当于拨打了13912212178这个电话号码。

用数组存储散列表时，散列通过散列函数将键值对中的键对应成数组中的索引。即下图中的Gandalf对应成685，于是通过“键”Gandalf访问邮件的过程就成了访问索引685的过程，而数组中arr[685]得到数据的过程是一步的。其中关键的是怎么散列，即怎么把键对应成数组（散列表）中的索引。最简单的方式就是像下图所示，将每个键值中的每个字母的 ASCII 值相加。（lose lose散列函数）

姓名与邮箱的散列

这里只是说明散列表是如何实现一步查找的，实际中散列函数的设计是一个复杂的问题，又涉及到“碰撞”的问题，即两个“键”映射成同一个“值”，这需要去解决。在继续探究之前，我们有必要心理有数，何为散列表，为什么它能一步访问。具体内容，下面慢慢来。

字典的实现

JavaScript中的对象就是散列表。这里讲的数据类型实现是指ADT实现，重点在于基本操作的实现，具体到JavaScript中，应该是一个封装好的对象或者函数（函数归根也是对象）。所以从ADT角度来说，什么是字典数据类型？具有以下基本操作的就是字典：

• set（key, value）,向字典中添加新元素
• remove（key）
• hasKey(key)
• get(key)
• clear()
• size()
• isEmpty()
• keys()：字典中所有键组成的数组返回
• values()：字典中所有值组成的数组返回
• keyValues():将字典中所有[键，值]对返回
• forEach（callback（key，value））：迭代字典中所有的键值对。callbackFn 有两个参数：key 和 value。

class KeyValue {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
    toString(key, value) {
        return `${this.key}:${this.value}`
    }
}

class Dictionary {
    constructor() {
        //整个字典的数据容器，是一个对象
        this.table = {};
    }

    //js中的键只能是string，因此需要将其他类型转成string
    toStrFn(key) {
        if (key === null) {
            return 'null';
        } else if (key === undefined) {
            return 'undefined';
        } else if (typeof key === 'string' || key instanceof String) {
            return key;
        }
        return key.toString();
    }


    hasKey(key) {
        return this.table[this.toStrFn(key)] != null;
    }

    set(key, value) {
        if (key != null && value != null) {
            this.table[this.toStrFn(key)] = new KeyValue(key, value);
            return true;
        }
        return false;
    }

    remove(key) {
        if (this.hasKey(key)) {
            delete this.table[this.toStrFn(key)];
            return true;
        }
        return false;
    }

    get(key) {
        if (this.hasKey(key)) {
            return this.table[this.toStrFn(key)].value;
        }
        return undefined;
    }

    keyValues() {
        // return Object.values(this.table)
        const result = [];
        //x为table对象的属性值
        for (let x in this.table) {
            if (this.hasKey(x)) {
                result.push(this.table[x])
            }
        }
        return result;
    }

    keys() {
        return Object.keys(this.table);
    }

    values() {
        return this.keyValues().map(x => x.value)
    }

    //迭代字典中的键值对的方法
    forEach(callback) {
        let keyValues = this.keyValues();
        for (let i = 0; i < keyValues.length; i++) {
            let result = callback(keyValues[i].key, (keyValues[i].value))
            if (result === false) {
                break;
            }
        }
    }

    size() {
        return this.keys().length;
    }

    isEmpty() {
        return this.size() === 0;
    }

    clear() {
        this.table = {};
    }
}
复制代码

总体来说，只要确定好字典应该具有哪些基本操作，每个操作是干嘛的，利用JavaScript中已有的方法实现起这些操作是很简单的。字典类实例化应用和之前实现其他数据结构是一样的，这里就不赘述了。

散列表的实现

散列表中关键的就是散列函数的设计，散列函数的设计依赖于键值的数据类型的，如果键是整型，那比较容易就可以转化为数组的索引，可以对数组的长度取余（数组长度为质数较好）。但很多时候键是字符串类型，选择对字符串类型的散列函数是很难的。

对字符串的散列函数，最简单的就是把每个字符串的ASCII码相加。散列值（数组的索引）就是和除以数组长度的余数。为了得到比较小的数值，我们会使用 hash 值 和一个任意数做除法的余数（%）——这可以规避操作数超过数值变量最大表示范围的风险。这个ACSII码相加的散列函数可以定义如下：

 //散列函数：键的所有ASCII码相加，对数组长度（一个质数）取余，得到索引值
    loseloseHashFn(key) {
        let len = this.table.length;
        if (typeof key === 'number') {
            return key % 37;
        }
        let sum = 0;
        for (let i = 0; i < key.length; i++) {
            sum += key.charCodeAt(i);
        }
        return sum % 37;
    }
    //得到键的哈希值（散列值、数组中索引）
    hashCode(key) {
        return this.loseloseHashFn(key)
    }
复制代码

使用一个关联数组（对象）来表示我们的数据结构，和我们在 Dictionary 类中所做的一样。这里实现两个散列表的基本方法：

• put(key, value)
• remove(key)

class KeyValue {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
    toString(key, value) {
        return `${this.key}:${this.value}`
    }
}

class HashTable {
    constructor() {
        this.table = {}
    }

    toStrFn(key) {
        if (key === null) {
            return 'null';
        } else if (key === undefined) {
            return 'undefined';
        } else if (typeof key === 'string' || key instanceof String) {
            return key;
        }
        return key.toString();
    }

    //上面的散列函数
    loseloseHashFn(key) 

    hashCode(key) 

    //put(key, value),同字典中的set，只是大部分语言中HashTable中叫put，命名习惯而已。
    put(key, value) {
        if (key != null && value != null) {
            const index = this.hashCode(key);
            this.table[index] = new KeyValue(key, value);
            return true;
        }
        return false;
    }

    //remove(key)
    remove(key) {
        const hash = this.hashCode(key);
        if (this.table[hash] != null) {
            delete this.table[hash];
            return true;
        }
        return false;
    }

    //get(key)
    get(key) {
        const keyValue = this.table[this.hashCode(key)];
        return keyValue == null ? undefined : keyValue.value;
    }
}
复制代码

const hash = new HashTable(); 
hash.put('Gandalf', 'gandalf@email.com'); 
hash.put('John', 'johnsnow@email.com'); 
hash.put('Tyrion', 'tyrion@email.com');
复制代码

console.log(hash)

键映射为散列值，存储在散列表中

散列“冲突”的解决

上面三个键对应的散列值19、29、16没有重复，很显然也会有其他键（字符串ASCII码相加）的散列值为19，这样在散列表中，19就对应了两个数据，很显然这是不行的。这种两个“键”映射成同一个“值”的情况就及叫做“碰撞”或者“冲突”，如下面的4个名字的散列值都是5。

const hashCode1 = hash.hashCode("Sue");  //5
const hashCode2 = hash.hashCode("Jamie");  //5
const hashCode3 = hash.hashCode("Jonathan");   //5
const hashCode4 = hash.hashCode("Aethelwulf");   //5
复制代码

解决冲突的方法包括：分离链接、线性探查、双按散列法

ES6原生Map，WeakMap，WeakSet类

1. Map与Object

2. Map 和 Set 与其弱化版本

WeakSet 或 WeakMap 类没有 entries、keys 和 values 等方法； 只能用对象作为键。

创建和使用这两个类主要是为了性能。WeakSet 和 WeakMap 是弱化的（用对象作为键）， 没有强引用的键。这使得 JavaScript 的垃圾回收器可以从中清除整个入口。同时必须用键才能访问值，可以用WeakMap设置ES6的私有属性。

3. Map 与 Set

Set（集合）只关心值，而Map是键值对。

参考资料

• 书籍：学习JavaScript数据结构与算法（第3版）
• 书籍：数据结构与算法JavaScript描述
• MND中Map：developer.mozilla.org/zh-CN/docs/…