哈希表详解与实现
哈希表详解与实现
哈希表（Hash Table）是一种通过哈希函数将关键字与存储位置建立映射关系的数据组织方式，其核心在于利用哈希函数快速计算关键字的位置，从而实现高效查找。
哈希概念剖析
1.1 哈希冲突
不同的关键字（key）通过一系列操作之后映射到同一个位置上的情况被称为哈希冲突或哈希碰撞。那么如何去避免哈希冲突呢？理想情况就是要找出一个好的哈希函数避免冲突（此处的哈希函数将在后文进行介绍），但是实际上冲突是不可避免的，我们只能尽可能设计出优秀的哈希函数，从而减少冲突次数，另外设计解决冲突的方案也是必不可少的。
1.2 负载因子
假设哈希表中已经映射存储了N个值，哈希表的大小为M，那么负载因子=N / M。在某些场景下，负载因子也被称为载荷因子或者装载因子等。负载因子越大，哈希冲突概率也越高，空间利用率高；相反负载因子越小，哈希冲突的概率就越低，空间利用率越低。
1.3 哈希函数
一个好哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，而常见的几种构建哈希函数的方法如下。
1.3.1 除法散列法/除留余数法
除法散列法也叫做除留余数法，是目前较为常用的一种设置哈希函数的方法，顾名思义，假设哈希表的大小为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。
tips：
- 当使用除法散列法时，应避免使用某些值作为M，例如2的幂、10的幂等。因为如果M等于2的幂，那么key%M本质上就是保留key的后x位，那么后x位相同的值所得的哈希值也相等。如：{63，31}看起来没有关联的值，如果M是如果M是16，也就是 2^4，那么计算出的哈希值都是15，因为63的二进制后8位是 00111111，31的二进制后8位是 00011111，他们的后几位都一样。
- 当使用除法散列法时，建议M取不太接近2的整数次冥的一个质数(素数)。
1.3.2 乘法散列法
乘法散列法相较于除法散列法不这么常用。乘法散列法是一种用于哈希表的技巧，它的好处是不用特别在意哈希表的大小M。这个方法主要分两步走：
- 首先，拿你的关键字K去乘以一个小于1的正数A，然后只取这个乘积的小数部分。
- 接着，用哈希表的大小M去乘刚才得到的小数部分，最后把结果向下取整，得到一个整数。
这个过程的目的就是把关键字K转换成一个哈希表中的位置，而且这个转换方法比较灵活，不受哈希表大小M的限制。简单来说，就是通过一些数学运算，把任意的关键字K变成一个适合放在哈希表里的位置。
通常h(key) = floor(M × ((A × key)%1.0))，其中floor表示对表达式向下取整，(0 ＜ A ＜ 1。一般来说 A = (√5 - 1) / 2 = 0.6180339887....(黄金分割点)比较好。
示例：假设M为1024，key为1234，A = 0.6180339887, Akey = 762.6539420558，取小数部分为0.6539420558, M×((A×key)%1.0) = 0.65394205581024 = 669.6366651392，那么h(1234) = 669。
1.3.3 全域散列法
如果有人故意使坏，他们可以研究我们公开的哈希函数，然后故意制造一堆数据，这些数据通过哈希函数后都会指向哈希表中的同一个位置，这就会导致严重的冲突，影响哈希表的性能。
为了避免这种情况，我们可以给哈希函数加点“随机调料”，这样即使有人知道哈希函数的基本做法，他们也没法预测或制造出一定会导致冲突的数据。这种通过引入随机性来增强哈希函数安全性的方法，就叫做全域散列。简单来说，就是让哈希函数变得不可预测，以此来防止恶意攻击。
hab(key) = ((a × key + b)%P )%M，P需要选一个足够大的质数，a可以随机选[1,P-1]之间的任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了一个P*(P-1)组全域散列函数组。
假设P=17，M=6，a = 3， b = 4, 则 h34(8) = ((a × key + b)%P )%M = ((3 × 8 + 4)%17)%6 = 5
当我们使用全域散列（一种增强哈希表安全性的方法）时，需要注意一个关键点。在初始化哈希表的时候，我们需要从一组哈希函数中随机选择一个来使用。一旦选定了这个哈希函数，后续的所有操作（比如插入、删除、查找等）都必须固定使用这个函数，不能随意更换。
如果每次操作都随机选择一个不同的哈希函数，就会导致问题。比如，插入数据时用的是哈希函数A，而查找时却用了哈希函数B，这样就会找不到之前插入的数据，因为两个函数计算的结果可能完全不同。
简单来说，就是选好一个哈希函数后，从头到尾都要用它，不能换来换去，否则数据就乱套了！
处理哈希冲突
1.1 开放定址法
这是一种解决哈希表冲突的方法。它的核心思想是：所有的数据都直接存放在哈希表里，如果某个关键字key通过哈希函数计算出的位置已经被占用了（发生冲突），就按照一定的规则去找下一个空闲的位置来存放这个key。
在开放定址法中，哈希表的负载因子（即已存放数据占整个表的比例）必须小于1，也就是说，表不能完全被填满，否则就找不到空闲位置了。
具体的规则有三种：
- 线性探测：如果冲突了，就依次往后找一个空闲的位置。
- 二次探测：如果冲突了，按照一定的平方规律（比如1, 4, 9, 16...）去找下一个位置。
- 双重探测：用另一个哈希函数来计算下一个位置，相当于双重保险。
1.1.1 线性探测法
规则：先计算key对应的位置，若该位置没有被占用则将key存放入该位置，否则从发生冲突的位置开始，依次线性向后探测，直到找到下一个没有被占用的位置。如果走到了哈希表尾，则回到哈希表头继续开始往后走。
h(key) = hash0 = key % M, hash0位置冲突了，则线性探测公式为：hc(key, i) = hashi = (hash0 + i) % M， i = {1, 2, 3, ..., M - 1}，因为负载因子小于1，则最多探测M-1次，一定能找到一个存储key的位置。
对于{19，30，5，36，13，20，21，12}映射到M=11的表中如下图所示：
具体实现过程如下：首先先插入19，19 % 11 = 8，一开始8位置没有被占据，则19可以直接放在位置8中。第二个要插入的数尾30，30 % 11 = 8，这时候我们发现求余的结果也是8而位置8上已经放有19了，那么我们就将30往8位置的下一个9位置存放。第三个要插入的是5，5 % 11 = 5，位置5没有被占用直接放入。第四个要插入的是36，36 % 11 = 3，3没有被占用直接插入。第五个要插入的是13，13 % 11 = 2，2没有被占用直接插入。第六个要插入的是20，20 % 11 = 9，但是此时位置9已经有30在占着了，因此把20往位置9后面找空余的位置，此时10号位为空，将20放入10号位。第七个要插入的是21，21 % 11 = 10，此时20占据了10号位，那么就重新回到表头，此时表头为空，那么就将21插入在0号位。最后要插入的是12，12 % 11 = 1，1号位为空直接插入。
1.1.2 二次探测法
除了上述的线性探测法，还有没有什么探测方案呢？有的兄弟，有的，这里引入二次探测法。线性探测法在某个位置发生冲突时，很容易会一堆数凑在一起，常常会出现一个哈希表中，一段区间放满了数，一段区间没什么数。为了减少这种情况，二次探测法就应运而生了。
当某个位置发生冲突时，探测的步骤是这样的：
- 左右跳跃式搜索：从冲突的位置开始，先向右按“1²步、2²步、3²步...”的距离跳跃检查，如果右边没空位，再向左按同样的平方步数反向检查。
- 循环绕回：如果向右检查到哈希表末尾还没找到空位，就绕回到表头继续找；如果向左检查到表头还没找到，就绕到表尾继续找。
- 直到找到空位：按这个“左右跳跃+循环绕回”的规则，直到发现一个空闲的位置，把数据存进去。
举个例子：假设当前冲突的位置是5，表长是10：
- 第一次探测从5位置向右跳1²=1步，到位置6；
- 如果还冲突，从5位置向左跳1²=1步，到位置4；
- 如果仍冲突，从5位置向右跳2²=4步，到位置9；
- 再冲突，从5位置向左跳2²=4步，到位置1；
- 依此类推，直到找到能存放的位置。
这种方法通过“平方跳跃”扩大搜索范围，避免像线性探测那样扎堆，同时通过循环绕回覆盖整个哈希表。
则二次探测的公式为：hash0 = key % M
hashi = (hash0 ± i^2) % M, (i ∈ {1，2，3，……，M/2} （先往左跳还是先往右跳可自由选择）
下面演示 {19,30,52,63,11,22} 等这一组值映射到M=11的表中（这里以先往右跳为例）
h(19) = 8, h(30) = 8, h(52) = 8, h(63) = 8, h(11) = 0, h(22) = 0，因此19放在8位置，30放在8的右一格， 52放在8的左一格，11放在0位置，22放在0的右一格。
1.1.3 双重散列法
除了上述提及的两种方法，这里还提供一种更为复杂的方法，双重散列法。
双重散列是什么 双重散列是解决哈希表中哈希冲突的办法。哈希表存数据时，可能不同数据被算到同一个位置，这就是冲突。双重散列的做法是，第一个哈希函数算出的位置有数据了（冲突），就用第二个哈希函数算一个和数据键相关的偏移量，从冲突位置往后一个个找，直到找到空位置存数据。
那么该怎么计算？
- 第一步：初始位置计算。 用第一个哈希函数 h1(key)算初始哈希值，公式是 h1(key) = hash0 = key % M。这里 key 是数据的键，M 是哈希表大小，hash0 就是数据原本该存的地方。
- 第二步：冲突后处理。要是 hash0 位置已有数据，就用双重探测公式找新位置。公式是 hc(key, i) = hashi = (hash0 + i * h2(key)) % M。i 从 1 开始，一个个增加，按公式算新位置，直到找到空的。
- 第二个哈希函数怎么取值。第二个哈希函数
h2(key)算出的值要小于 M，而且 h2(key) 和 M 得是互质的（最大公约数是 1）。有两种取值方法：
- M 是 2 的整数次幂时，在 [0, M - 1] 里随便选个奇数当 h2(key) 的值。
- M 是质数时，h2(key) = key % (M - 1) + 1。
为什么要互质 让 h2(key) 和 M 互质？这其实很关键，按固定偏移量找位置，能找到的位置会形成一个集合。如果 M 和 h2(key) 的最大公约数大于 1，能找到的位置个数就会比 M 小，没法用满整个哈希表。
比如，哈希表大小 M = 12，开始找的位置是 1，偏移量是 3，能找到的位置是 {1, 4, 7, 10}，能找的位置个数是 12 / gcd(12, 3) = 4，比 12 小，没把哈希表全用上。
1.2 链地址法
上述提及的三种开放定址法其实在减少冲突方面还是有所不足，这里介绍一种不同于开放地址法的方法，链地址法。链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成一个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者哈希桶。
至此，关于哈希的基本概念和实现就全部讲完了，感谢您的阅读！