当前位置：首页 > news >正文

【C++】哈希表的实现（链地址法）

news 2026/5/16 13:42:48

1.其他哈希函数

1.1 乘法散列法（了解）

乘法散列法对哈希表⼤⼩M没有要求，他的⼤思路：

第⼀步：⽤关键字K 乘上常数 A(0<A<1)，并抽取出k*A的⼩数部分
第⼆步：⽤M乘以k*A 的⼩数部分，再向下取整。

其实就是让M去乘一个[0, 1)之间的小数，这个小数要与K相关，K不同，这个小数就不同，就能映射的更分散。

经过大佬Knuth的分析，建议这个A取黄金分割点:

A=(\sqrt{5}-1)/2 = 0.6180339887....

所以乘法散列法的公式为：h(key) = floor(M * (A * key) % 1.0))，其中floor表⽰对表达式进⾏向下取整，A∈(0,1)。

举个例子：乘法散列法对哈希表⼤⼩M是没有要求的，假设M为1024，key为1234，A = 0.6180339887, A*key = 762.6539420558，取⼩数部分为0.6539420558, M×((A×key)%1.0) = 0.6539420558*1024 = 669.6366651392，那么h(1234) = 669。

1.2 全域散列法（了解）

这个函数主要是为了抵御恶意攻击的。如果存在⼀个恶意的对⼿，他针对我们提供的散列函数，特意构造出⼀个发⽣严重冲突的数据集，⽐如，让所有关键字全部落⼊同⼀个位置中。这种情况是可以存在的，只要散列函数是公开且确定的，就可以实现此攻击。

解决⽅法就是给散列函数增加随机性，攻击者就⽆法找出确定可以导致最坏情况的数据。这种⽅法叫做全域散列。

全域散列法的公式为：h(key) = ((a * key + b) % P) % M，P需要选一个足够大的质数，a可以随机选[1, P-1]之间的任意整数，b可以随机选[0, P-1]之间的任意整数。

这些函数构成了一个P * (P - 1)组全域散列函数组。

假设key是8，P=17，M=6，a = 3， b = 4, 则h(8) = ((3 * 8 + 4) % 17) % 6 = 5。

需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的⼀个散列函数使⽤，后续增删查改都固定使⽤这个散列函数，否则每次哈希都是随机选⼀个散列函数，那么插⼊是⼀个散列函数，查找⼜是另⼀个散列函数，就会导致找不到插⼊的key了。

2.处理哈希冲突的方法

在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种：线性探测（已做讲解）、⼆次探测、双重探测。

2.1 开放定址法

性探测的⽐较简单且容易实现，线性探测的问题假设，hash0位置连续冲突，hash0，hash1，hash2位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位置，这种现象叫做群集/堆积。

二次探测：

从发⽣冲突的位置开始，依次左右按加减⼆次⽅跳跃式探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果往右⾛到哈希表尾，则回绕到哈希表头的位置；如果往左⾛到哈希表头，则回绕到哈希表尾的位置。
h(key) = hash0 = key % M, hash0的位置冲突了，则二次探测的公式为hc(key, i) = hashi = (hash0

\pm

i^{2}

) % M, i = { 1, 2, 3, ... ,

\frac{M}{2}

}。