数据结构与算法javascript描述-散列表(下)

线性探测法

上篇 [1] 讲了通过分离链接法来解决散列表冲突问题。今天我们学习一个新的方法来解决该问题。

核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。那如何重新探测新的位置呢？

当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

黄色的色块表示空闲位置，橙色的色块表示已经存储了数据。

从图中可以看出，散列表的大小为 10，在元素 x 插入散列表之前，已经 6 个元素插入到散列表中。x 经过 Hash 算法之后，被散列到位置下标为 7 的位置，但是这个位置已经有数据了，所以就产生了冲突。于是我们就顺序地往后一个一个找，看有没有空闲的位置，遍历到尾部都没有找到空闲的位置，于是我们再从表头开始找，直到找到空闲位置 2，于是将其插入到这个位置。

在散列表中查找元素的过程有点儿类似插入过程。我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。

代码实现

/**

* @description 在字典中我们是用键值对来存储数据

*/

const assert = require("assert");

// 散列函数

const loseloseHashCode = (key = "") => {

let hashCode = 0;

for (let i = 0; i < key.length; i++) {

hashCode += key.charCodeAt(i);

}

return hashCode % 37;

};

class patchValue {

constructor(key, value) {

this.key = key;

this.value = value;

}

}

class HashTableLine {

constructor() {

this.table = [];

}

put(key, value) {

const position = loseloseHashCode(key);

if (this.table[position] !== undefined) {

let curIndex = position + 1

while (this.table[curIndex] !== undefined) {

curIndex++

}

this.table[curIndex] = new patchValue(key, value)

} else {

this.table[position] = new patchValue(key, value)

}

}

remove(key) {

const position = loseloseHashCode(key);

if (this.table[position] && this.table[position].key === key) {

this.table[position] = undefined;

return true;

}

let curIndex = position + 1;

while (this.table[curIndex].key !== key) {

curIndex++;

}

this.table[curIndex] = undefined

return true;

}

get(key) {

const position = loseloseHashCode(key);

if (this.table[position] && this.table[position].key === key) {

return this.table[position].value;

}

let curIndex = position + 1

while (this.table[curIndex].key !== key) {

curIndex++

}

return this.table[curIndex].value

}

getItems() {

return this.table;

}

}

// test case

const hashTable = new HashTableLine();

hashTable.put("Donnie", "[email protected]");

hashTable.put("Ana", "[email protected]");

console.log(hashTable.getItems());

hashTable.remove("Donnie");

hashTable.remove("Ana");

console.log(hashTable.getItems());

hashTable.put("Donnie", "[email protected]");

console.log(hashTable.getItems());

线性探测法 VS 分离链接法

首先不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子（load factor）来表示空位的多少。

散列表的装载因子=填入表中的元素个数/散列表的长度

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。散列函数设计的好坏决定了散列冲突的概率，也就决定散列表的性能。

散列表的查询效率并不能笼统地说成是 O(1)。它跟散列函数、装载因子、散列冲突等都有关系。如果散列函数设计得不好，或者装载因子过高，都可能导致散列冲突发生的概率升高，查询效率下降。

如何选择冲突解决方法？

线性探测法

线性探测法不像链表法，需要拉很多链表。散列表中的数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度。而且，这种方法实现的散列表，序列化起来比较简单。链表法包含指针，序列化起来就没那么容易。你可不要小看序列化，很多场合都会用到的。

用线性探测法解决冲突的散列表，删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。而且，在线性探测法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。所以，使用线性探测法解决冲突的散列表，装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。

当数据量比较小、装载因子小的时候，适合采用线性探测法。

分离链接法

链表法比起线性探测法，对大装载因子的容忍度更高。线性探测法只能适用装载因子小于 1 的情况。接近 1 时，就可能会有大量的散列冲突，导致大量的探测、再散列等，性能会下降很多。但是对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成 10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。

链表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的，还有可能会让内存的消耗翻倍。而且，因为链表中的结点是零散分布在内存中的，不是连续的，所以对 CPU 缓存是不友好的，这方面对于执行效率也有一定的影响。当然，如果我们存储的是大对象，也就是说要存储的对象的大小远远大于一个指针的大小（4 个字节或者 8 个字节），那链表中指针的内存消耗在大对象面前就可以忽略了。

实际上，我们对链表法稍加改造，可以实现一个更加高效的散列表。那就是，我们将链表法中的链表改造为其他高效的动态数据结构，比如跳表、红黑树。这样，即便出现散列冲突，极端情况下，所有的数据都散列到同一个桶内，那最终退化成的散列表的查找时间也只不过是 O(logn)。这样也就有效避免了前面讲到的散列碰撞攻击。

基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起线性探测法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

如何设计一个散列函数

• 散列函数的设计不能太复杂

过于复杂的散列函数，势必会消耗很多计算时间，也就间接的影响到散列表的性能。

• 散列函数生成的值要尽可能随机并且均匀分布

详细的介绍后续可以单独学习。

参考资料

数据结构与算法之美 [2]

感兴趣的可以关注下公众号

References

[1] 上篇:  https://zhuanlan.zhihu.com/p/102430729

[2] 数据结构与算法之美:  https://time.geekbang.org/column/article/64233