散列表 | StoneRiver Blog

什么是散列表

散列表利用是数组支持时间复杂度是 O(1) 按照下标随机访问数据的特性。通过散列函数把元素的键值映射为下标，将数据存储在数组中对应下标的位置的数据结构。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

hash(key) 将元素的键值计算映射为一个整型的函数。

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

第三点不能完全的满足，业界著名的MD5、SHA、CRC等哈希算法也无法完全避免散列冲突。

从散列表的定义可以知道，键值存储在以散列值为下标的数组中。由于数组的长度有限，同时散列函数不能保证不发生冲突，所以一定有数组的某个位置已经有值的情况。如何解决散列冲突？

当发现数组某个位置已存在元素时，会继续向后寻找某个为空的位置放入元素。具体寻找的方法称为探测方法。常见的探测方法为：

线性探测：发生冲突后的探测下标序列为：hash(key)+0，hash(key)+1，hash(key)+2……
二次探测：发生冲突后的探测下标序列为：hash(key)+0²，hash(key)+1²，hash(key)+2²……
双重散列：使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……先用第一个散列函数，如果发生冲突，再用第二个散列函数，依次类推。

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

由于查找数据依据查找到了一个空闲位置而停止，所以对于删除数据不能简单的移除某个元素。可以将删除的元素，标记为 deleted 状态。当线性探测查找的时候，遇到标记为 deleted 的元素，并不是停下来，而是继续往下探测。

链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

开放寻找法的优点是不需要使用链表，只使用数组进行存储，可以充分利用CPU的缓存提高查询效率。缺点是处理冲突的代价高，删除数据内存理由律低。

所以对于数据量小，不需要经常插入删除数据数据的散列表使用开放寻址处理冲突更合适。

装载因子的计算公式是：

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

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。2. 链表法

当装载因子到达某个阈值时，进行再hash，将数据搬移到基于更大数组的散列表中。

解决hash算法在分布式问题中，因为节点的增减造成所有节点的hash值改变，大量重新分布的问题。