# 字典和散列表

# 字典数据结构

字典(Dictionary)是一个以[键, 值]形式来存储唯一值的数据结构。集合是以[值, 值]形式存储的，这是两者的区别；字典也称作映射、符号表或关联数组；null 和 undefined 不可以用作键或值。

# 字典实现

其实在 es2015，新增了Map (opens new window)类作为 JavaScript API 的一部分，所以我们可以直接使用它（跟 Array 一样可以不用自己实现，但在这里还是实现一下 Map，开发过程中直接使用 es2015 的 Map）。

字典实现代码细节：dictionary.ts (opens new window)

1.先准备一个助手类ValuePair (opens new window)，作为字典的[键, 值]中的“值”。它含有两个公有属性 value 和 key，还有一个重写的 toString 方法。

2.给字典类声明一个私有属性_table，它的类型当然是[键, 值]这样的形式。先选用对象类型，然后对象的属性名和属性值的存储形式必须是 K:V，K 这里一般就是选择 String，而 V 当然就选择我们之前创建的 ValuePair。具体如下

private _table: { [K: string]: ValuePair<K, V> };

3.再声明一个_toStrFn，用以接收实例化时外界传来的“any 转字符串”方法，意思是“键”的类型我们需要统一转换成 String，这样方便作为对象的属性名。

4.set 方法，向字典中添加新元素。将 key 用_toStrFn 的方法转换成 String 类型，然后以 key 作为_table 的属性名、new ValuePair(key, value)作为_table 的属性值形成一个[键, 值]形式的元素（重复的也会被覆盖）。

5.get 方法，通过以键作为参数查找对应的值并返回。将 key 用_toStrFn 的方法转换成 String 类型，然后用对象的[]来直接查找 key 对应的 ValuePair，最后返回 ValuePair.value 即可。

6.hasKey 方法，如果某个键值存在于该字典中返回 true，否则返回 false。这个很简单，直接调用 get 方法，然后判断 get 的结果是否为空。

7.remove 方法，通过键来删除字典中对应的键值对。先调用 hasKey 方法判断这个 key 是否存在于字典中，存在的话使用 delete 操作符去删除_table 对象中对应的属性名 key。

8.keyValues 方法，将字典中所有[键, 值]对返回。直接 Object.values(this._table)就能得到。

9.values 方法，将字典所包含的所有数值以数组形式返回。先调用 keyValues，得到字典中所有[键, 值]对，然后配合map (opens new window)方法得出字典的所有数值。

10.keys 方法，将字典所包含的所有键名以数组的形式返回。先调用 keyValues，得到字典中所有[键, 值]对，然后配合map (opens new window)方法得出字典的所有键名。

11.forEach 方法，迭代字典中所有的键值对（只要有一项不符合 callBackFn 就中断迭代）

public forEach(callBackFn: (key: K, value: V) => any) {
    const valuePair = this.keyValues();
    for (let i = 0, le = valuePair.length; i < le; i ++) {
        const result = callBackFn(valuePair[i].key, valuePair[i].value);
        if (result === false) {
            break;
        }
    }
}

1
2
3
4
5
6
7
8
9

11.其他方法 size、isEmpty、clear、toString 跟以往一样比较好实现。

# 散列表数据结构

字典(HashTable 或 HashMap)是字典的散列表实现。

散列表使用了散列算法，散列算法的作用是尽可能快地在数据结构中找到一个值，它不像其他的方法要迭代整个数据结构。

散列表的应用有很多，例如关系型数据库中的表索引、JavaScript 对象内部的实现（对象的每个属性和方法（成员）被储存为 key 对象类型，每个 key 指向对应的对象成员）。

# 散列表实现

散列表实现代码细节：hash-table.ts (opens new window)

1.散列表的跟字典一样，同样声明了_table 和_toStrFn，可以查看字典那一节回顾一下。

2.创建散列函数，采用的是 lose lose 散列函数，就是将键值中的每个字母的 ASCII 值相加。

private loseloseHashCode(key: K): number {
    if (typeof key === 'number') {
        return key;
    }
    const tableKey = this._toStrFn(key);
    let hash = 0;
    for (let i = 0, le = tableKey.length; i < le; i ++) {
        hash += tableKey.charCodeAt(i);
    }
    return hash % 37;
}

1
2
3
4
5
6
7
8
9
10
11

你可能对“% 37”这个处理感到不解，它主要是为了避免散列值超过 number 的最大值，将散列表约束在一个小的范围内。但是有新问题，这表里不就只能有 37 个元素了？下面一节会解决这个问题。

3.put、get、remove 跟字典的里同名方法实现没什么区别，只是它的 key 多了一次散列处理。其他方法 getTable、size、isEmpty、clear、toString 也不作说明了，很简单。

# 解决散列表的冲突

上面我们提到过，再“% 37”后，最终存下来的元素只有 37 个了，其他很多元素都会在相同的散列值那里被覆盖掉，我们解决的这个问题的方法有三种：分离链接法、线性探查法和双散列法。这里只说前两种。

# 分离链接法

分离链接法就是为散列表的每一个位置创建链表，将相同散列值存储在各自的链表中以解决冲突。
这种方法虽然是最简单的处理冲突的方法，但是比较耗存储空间如果每个位置都用链表。

散列表分离链接法实现代码细节：hash-table-separate-chaining.ts (opens new window)

1.put 方法，先通过散列函数拿到对应的散列值，然后通过对象的[]拿到对应位置的链表，如果这个链表为 null 就新创建一个链表赋给这个对象；我们将新元素通过链表的 put 方法添加到链表里，这样就完成了散列表新增元素的方法。

2.get 方法，先通过散列函数拿到对应的散列值，然后通过对象的[]拿到对应位置的链表，如果链表为 null 或者链表中没有元素，就直接返回 undefined；如果链表存在并且有元素，那么去遍历链表（从 head 开始通过 next 来遍历）只要 key 与元素存的 key 一样，证明这个元素就是我们要 get 的元素。

3.remove 方法，原理同 get 方法类似，找到对应位置链表，遍历链表找到相同 key 的元素，使用链表的 remove 方法删除这个元素；在删除这个元素我们还需要做的一件事就是判断这个链表是否为空了，为空了就将链表从_table 中 delete 掉。

4.其他方法 getTable、size、isEmpty、clear、toString 也不作说明了，很简单。

# 软删除式的线性探查法

线性探查法将每个元素都存储在表中，而不是借助链表等外物来解决冲突。

当想向表中某个位置添加一个新元素的时候，如果索引为 index 的位置已经被占据了，就尝试 index+1 的位置，如果这个位置也被占据就尝试下一个直至找到空闲的位置。
它有个问题：删除时会用一个字段记录删除状态而不是真正的删除它，在查询时可能会查询很多位置的这个字段导致效率变慢。

软删除式的线性探查法实现代码细节：hash-table-linear-probing-lazy.ts (opens new window)

1.因为是用一个字段记录删除的状态，所以我们新建一个助手类ValuePairLazy (opens new window)，它比 ValuePair 多一个 isDeleted 字段，代表是否被删除了。

2.put 方法，先通过散列函数拿到对应的散列值，然后通过对象的[]拿到对应位置的值；判断这个值是否不存在或者它存在的话 isDeleted 为 true，意思是这个位置没有人占，可以将这个位置直接拿下把新元素存在这里；否则，我们让散列值的值+1，再看这个位置的有没有人占，有的话散列值再+1，直到找到空位置才赋值。

3.get 方法

/**
 * 通过以键值作为参数查找对应的值并返回
 * 情况复杂：
 * 1.哈希值所在的位置key相同并且没被删除就返回这个value，否则去下一个位置查找。 {1}
 * 2.下一个位置key相同并且也没被删除就返回这个value。否则只能去寻下下个位置了。{4}
 * 3.但是下一个位置key相同并且被删除就直接return undefined {2}
 * 4.一直找但key一直不相同（删不删除无所谓），就一直找，直到没有元素了（this._table[index]为空） {3}
 */
public get(key: K): V {
    if (key == null) { // 参数不合法
        return undefined;
    }
    const tableKey: number = this.hashCode(key);
    if (this._table[tableKey] == null) { // 因为是线性，这个为空证明下面的也没有，直接返回undefined
        return undefined;
    }
    // key相同，并且没被删除 {1}
    if (this._table[tableKey].key === key && !this._table[tableKey].isDeleted) {
        return this._table[tableKey].value;
    } else {
        let index: number = tableKey + 1;
        while (this._table[index] != null && (this._table[index].key !== key
            || this._table[index].isDeleted)) {
            // 情况1：key相同并且被删除。是我们找的key，但被删除了那就直接return undefined {2}
            if (this._table[index].key === key && this._table[index].isDeleted) {
                return undefined;
            }
            index ++; // 情况2：key不相同，删不删除无所谓。此时必须找下一个位置以保证拿到相同key {3}
        }
        // 情况3：key相同并且没被删除或者this._table[index]根本就为空 {4}
        return this._table[index] != null ? this._table[index].value : undefined;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

4.remove 方法

/**
 * 通过键来删除字典中对应的键值对
 * 情况复杂：
 * 1.哈希值所在的位置key相同并且没被删除就返回这个value，否则去下一个位置查找。 {1}
 * 2.下一个位置key相同并且也没被删除就返回这个value。否则只能去寻下下个位置了。{4}
 * 3.但是下一个位置key相同并且被删除就直接return undefined {2}
 * 4.一直找但key一直不相同（删不删除无所谓），就一直找，直到没有元素了（this._table[index]为空） {3}
 */
public remove(key: K): boolean {
    if (key == null) { // 参数不合法
        return false;
    }
    const tableKey: number = this.hashCode(key);
    if (this._table[tableKey] == null) { // 因为是线性，这个为空证明下面的也没有，直接返回fasle
        return false;
    }
    // key相同，并且没被删除 {1}
    if (this._table[tableKey].key === key && !this._table[tableKey].isDeleted) {
        this._table[tableKey].isDeleted = true;
        return true;
    } else {
        let index: number = tableKey + 1;
        while (this._table[index] != null && (this._table[index].key !== key
            || this._table[index].isDeleted)) {
            // 情况1：key相同并且被删除。是我们找的key，但被删除了那就直接return false {2}
            if (this._table[index].key === key && this._table[index].isDeleted) {
                return false;
            }
            index ++; // 情况2：key不相同，删不删除无所谓。此时必须找下一个位置以保证拿到相同key {3}
        }
        // 情况3：key相同并且没被删除 {4}
        if (this._table[index] != null) {
            this._table[index].isDeleted = true;
            return true;
        }
        return false; // this._table[index]为空, 没有删除的东西
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

5.其他方法 getTable、size、isEmpty、clear、toString 也不作说明了，很简单。

# 真删除式的线性探查法

软删除只是用字段记录了删除状态，不会将元素移除，如果数据够多，查询起来效率很慢。真删除，是真正的将那个元素移除，并且将下面的元素补上来。

软删除式的线性探查法实现代码细节：hash-table-linear-probing.ts (opens new window)

1.put 方法同软删除的很像，少了 isDeleted 的判断而已。先通过散列函数拿到对应的散列值，然后通过对象的[]拿到对应位置的值；判断这个值是否不存在，如果不存在可以将新元素存在这里，如果存在，我们让散列值的值+1，再看这个位置的有没有人占，有的话散列值再+1，直到找到空位置才赋值。

2.get 方法，先通过散列函数拿到对应的散列值，然后通过对象的[]拿到对应位置的值；判断这个值是否存在并且 key 相同，如果满足条件就返回这个值，否则，我们让散列值的值+1，再看新位置的值存不存在并且 key 相同，如果不行再让散列值再+1，直到找到的位置上的值存在并且 key 相同。

3.remove 方法，最麻烦的是这个方法了，它在 get 逻辑基础上增加了 delte 和 verifyRemoveSideEffect 方法。我们 get 到一个元素，先删除它，然后需要把下面的元素补上去。补上去的时候它把遍历到当前位置的散列值与空缺位置的散列值相比较，如果小，会把当前位置的元素补到空缺位置。而不符合这个条件的只是单纯的往上移一个位置。

/**
 * 如果HashTable后面有小于等于被删除key的hash值，先将这移到空缺处，
 * 然后继续向后遍历，当前位置的hash值小于等于空缺处的hash值，就将这移到空缺处，
 * 总之就是在遍历一遍的情况下尽可能的保证hash值有序，可能会存在个别无序或者还有空缺的地方
 * @param key 键
 * @param removedPosition 删除时的位置的散列值（hash值）
 */
private verifyRemoveSideEffect(key: K, removedPosition: number) {
    const hash = this.hashCode(key);
    let index = removedPosition + 1;
    while (this._table[index] != null) {
        const posHash = this.hashCode(this._table[index].key);
        if (posHash <= hash || posHash <= removedPosition) {
            this._table[removedPosition] = this._table[index];
            delete this._table[index];
            removedPosition = index;
        }
        index++;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.其他方法 getTable、size、isEmpty、clear、toString 也不作说明了，很简单。

# 更好的散列函数

lose lose 散列函数并不是一个表现良好的散列函数，它会产生太多冲突。一个表现良好的散列函数由几个方面构成：插入和检索元素的事件（即性能），以及较低的冲突可能性。

private djb2HashCode(key: K) {
    const tableKey = this._toStrFn(key);
    let hash = 5381; // 大多实现用的5381
    for (let i = 0; i < tableKey.length; i ++) {
        // 与一个常数相乘
        hash = (hash * 33) + tableKey.charCodeAt(i);
    }
    return hash % 1013; // 随机质数1013
}

1
2
3
4
5
6
7
8
9

这并不最好的散列函数，但是最受社区推崇的散列函数之一。

# WeakMap 和 WeakSet

前面有介绍过，es2015 已经有自己的 Set 和 Map 了，我们建议使用 es2015 的而不是使用自己实现的 Set 和 Map。es2015 还给我们准备了它们的弱化版本WeakSet (opens new window)和WeakMap (opens new window)。

与 Set 和 Map 相比，WeakSet 和 WeakMap 没有 entries、keys 和 values 等方法，然后就是只能用对象作为键（WeakSet 就是只能对象作为元素）。WeakSet 和 WeakMap 的键是弱引用 (opens new window)，也就是说当程序不再拥有这个对象的引用时，垃圾回收器就可以从 WeakSet 或 WeakMap 中回收这些对象。

← 5.集合 7.递归 →