2021-06-26散列表

概念

1. 通过散列函数把元素映射为下标。然后将数据存储在数组中对应下标的位置。
2. 当安装键值查询元素时，可以用同样的散列函数，将键值转化成数组下标，从对应的下标位置获取数据。
3. 数组的一种扩展，由数组演化而来。没有数组，就没有散列表。

散列函数

概念

hash(key)（key 表示元素的键值；hash(key) 的值表示经过散列函数计算得到的散列值）。

实现

1. 散列函数计算得到的散列值是一个非负整数。
2. 如果key1 == key2，那hash(key1) == hash(key2)。
3. 如果key1 != key2，那hash(key1) != hash(key2)。

设计要点

1. 散列函数的设计不能太复杂。
2. 散列函数生成的值要尽可能随机且均匀分布。

装载因子

概念

1. 散列表的装置因子 = 填入表中元素个数/散列表的长度。
2. 装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

装载因子过大怎么办？

1. 当装载因子过大时，可以进行动态扩容，重新申请一个更大的散列表，将数据搬移到新的散列表中。
2. 针对散列表的扩容，数据搬移操作比数组要复杂很多，需要通过散列函数重新计算每个数据的存储位置。

如何解决散列冲突

开放寻址法 -- 数组

概念

如果出现散列冲突，就重新探测一个空闲位置，将其插入。

应用

数据量较小，装载因子小的时候，适合采用开放寻址法。

优点

1. 散列表中的数据都存储在数组中，可以有效的利用CPU缓存加快查询速度。
2. 这样实现的散列表，序列化起来比较简单。

缺点

1. 删除数据的时候比较麻烦，需要特殊标记已删除的数据。
2. 装载因子的上限不能太大。

线性探测

往散列表中插入数据时，如果当前位置已被占用，就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

二次探测

1. 跟线性探测很像。
2. 线性探测每次探测的步长是1，探测的下标序列就是hash(key)+0，hash(key)+1，hash(key)+2，....
3. 二次探测的步长就变成了原来的 “二次方”，探测的下标序列是hash(key)+0，hash(key)+1^{2，hash(key)+2}2，....

双重散列

先用一组散列表中的第一个散列函数，计算得到存储位置已经被占用的情况下，再用第二个散列函数，依次类推直到找到空闲的存储位置。

链表法

概念

1. 一种更加常用的散列冲突解决方法，比开放寻址法简单。
2. 每个 “桶(bucket)”或者 “槽(slot)” 会对应一条链表。所有散列值相同的元素都放到相同的槽位对应的链表中。

操作

1. 插入：只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可。
2. 查找：删除一个元素时，同样通过散列函数计算出对应的槽，遍历链表查找或者删除。

应用

1. 适合存储大对象，大数据量的散列表。
2. 更加灵活，支持更多的优化策略，比如用红黑树代替链表。

工业级散列表的特性

1. 支持快速地查询，插入，删除操作。
2. 内存占用合理，不能浪费过多的内存空间。
3. 性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。

实现工业级散列表的要点

1. 设计一个合适的散列函数。
2. 定义装载因子的阈值，并且设计动态扩容策略。
3. 选择合适的散列冲突的解决方法。