漫谈数据结构-散列表

1. 定义

散列表（Hash Table），平时也叫它“哈希表”或者“Hash 表”。通过把 Key 值映射到表（即数组）中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

散列表用的是 数组支持按照下标随机访问数据的时候，时间复杂度为O(1) 的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

2. 散列思想

• 把 Key(键，关键字) 值转换为数组下标的映射方法叫做散列函数（或“Hash 函数”“哈希函数”），而散列函数计算得到的值就叫作散列值（或“Hash 值”、“哈希值”）。
• 通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。
• 当按照键值key查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

3. 散列函数

散列函数，是一个函数。我们可以把它定义成 hash(key)，其中：

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

散列函数设计的基本要求：

• 散列函数计算得到的散列值是一个非负整数
• 如该 Key1 = Key2，那么hash(Key1) = hash(Key2)
• 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)

散列冲突难以避免：

• 理想情况下Key值和hash(Key)是一一对应的，但现实情况下，想要找到一个不同的Key对应的散列值一定不一样的散列函数，几乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。
• 因为数组的存储空间有限，也会加大散列冲突的概率

4. 散列冲突解决方案

散列冲突难以避免，故需要通过其他途径解决，常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。

4.1 装载因子（load factor）

不管哪种探测方法，当散列表中空闲位置不多时，散列冲突的概率都会大大提高。为了保证效率，一般情况下，都会尽可能的确保散列表中有一定比例的空闲槽位。

对此 使用装载因子用来表示空位的多少 ，其计算公式为：

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

装载因子越大，说明空闲位置越少，冲突越多，性能下降。

4.2 开放寻址法

核心思想是：如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。
优点 ：散列表中的数据都存储在数组中，可以有效的利用 CPU 缓存加快查询速度，而且序列化简单。
缺点 ：

• 删除数据比较麻烦，需要特殊标记已经删除的数据。
• 所有的数据都存储在一个数组中，比起链表来说，冲突的代价更高，导致装载因子的上限不能太大，从而导致比链表法更浪费内存空间。
• 只能适用装载因子小于 1 的情况。接近 1 时，就可能会有大量的散列冲突。

适用场景 ：当数据量比较小，装载因子比较小的时候，适合采用开放寻址法，如Java中的 ThreadLocalMap 。序列化

4.2.1 线性探测（Linear Probing）

插入元素 ：当往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，就从当前位置开始，依次向后查找，看是否有空闲位置，如果遍历到尾部都没有找到空闲位置，则从表头继续找，直到找到空闲位置将其插入为止。
查找元素 ：通过散列函数得出要查找的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，说明就是要查找的元素；否则就顺序往后依次查找。若遍历到数组中的空闲位置，还没找到，说明要查找的元素并未在散链表法列表中。
删除元素 ：对于使用线性探索的散列表，可以将删除的元素特殊标记 deleted 。当线性探测查找时，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。通过特殊标记被删除的空间，可以避免查找元素时，遇到被删除的空间就直接将原本存在的数据认定为不存在。
缺点  ：插入的数据越多，散列冲突发生的可能性越大，空闲位置会越来越少，线性探测的时间会越来越久。极端情况下可能需要探测整个散列表，故最坏时间复杂度为 O(n) 。在查找和删除时也可能出现同样的情况。

4.2.2 二次探测（quadratuc probing）

二次探测和线性探测很像：

• 线性探测每次探测的步长是1，它探测的下表序列就是hash(key)+0,hash(key)+1…
• 二次探测的探测步长就变成了原来的“二次方” ，即探测下标序列为hash(key)+0，hash(key)+1^2…

4.2.3 双重散列(Double hashing)

使用一组散列函数，若使用第一个散列函数计算所得存储位置已被占用再用第二个散列函数，依次类推，直到找到空闲的存储位置。

4.2 链表法

在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

• 当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)。
• 当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。这两个操作的时间复杂度跟链表的长度 k 成正比，也就是 O(k)。
• 对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中 n 表示散列中数据的个数，m 表示散列表中“槽”的个数

优点

• 对内存的利用率比开放寻址法要高 ：链表节点尅了需要的时候创建，不需要像开放寻址那样需要事先申请好。
• 对装载因子的容忍度更高 ：只要散列函数的值随机均匀，即使装载因子变成10，也仅是链表长度变长，随查询效率有所下降，但比起顺序查找还是快很多。
• 若存储的是大对象（即远大于一个指针大小的对象，一个指针4字节或者8字节），则 链表中指针的内存消耗在大对象面前就可以忽略了。
• 可将链表改造为其他高效的动态数据结构，如跳表、红黑数。如此即使出现散列冲突，极端情况下。所有数据都散列到一个桶中，最终退化成的散列表的查找时间也仅是O(logn)。同时有效避免了散列碰撞攻击。

缺点

• 需要存储指针，所以存储比较小的对象比较消耗内存，还可能导致内存消耗翻倍。
• 由于包含指针，序列化相对较难。
• 因为节点是零星分布在内存中，并不连续，所以对CPU缓存不友好，对执行效率有一定影响。

适用场景 ：比较适用于存储大对象、大数据量的散列表，比起开放寻址法，更加灵活，支持更多的优化策略，如用红黑树代替链表。

参考资料

数据结构与算法之美