分享｜哈希算法（Hash Function）

2023.07.18

发布于未知归属地

哈希表 C 学习分享

1、哈希函数（散列函数）

1.1、定义

哈希（Hash）就是把任意长度的输入（Key），通过散列算法，变换成固定长度的输出，这个输出值就是散列值。

哈希表（Hash table，散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

载荷因子： α = 已插入元素数量 / 哈希表的容量。

同义词：具有不同关键码而具有相同哈希地址的数据元素，同义词产生哈希碰撞。

1.2、特性

一致性 —— 等价（equal）的key必然产生相等的hash code
高效性 —— 高效的计算，易于实现
均匀性 —— 均匀地散列所有的key
冲突性 —— 哈希算法必定会有哈希冲突

2、构造哈希函数

2.1、除法哈希法（余数哈希法）

hash(key) = key mod M，其中M是质数

2.2、乘法哈希法

hash(key) = floor( M/W * ( a * key mod W) )，其中通常设置 M 为 2 的幂次方，W 为计算机字长大小（也为2的幂次方），a 为一个非常接近于W的数。

2.3、斐波那契（Fibonacci）哈希法

属于乘法哈希法”的一种特例：
 a ≈ W/φ，1/φ ≈ (√5-1)/2 = 0.618 033 988

2.4、平方取中法

先对关键字取平方，然后选取中间几位为哈希地址；取的位数由表长决定，适用于不知道关键字的分布，而位数又不是很大的情况。

2.5、折叠法

将关键字分成位数相同的几部分（最后一部分位数可以不同），然后求这几部分的叠加和（舍去进位），并按照散列表的表长，取后几位作为哈希地址。

折叠法适用于关键字位数很多，而且关键字每一位上数字分布大致均匀。

备注：Switch lookup table很多采用折叠法（不同bit异或）来构造Hash函数。

2.6、数字分析法

数字分析法用于处理关键字是位数比较多的数字，通过抽取关键字的一部分进行操作，计算哈希存储位置的方法。

例如：关键字是手机号时，众所周知，我们的１１位手机号中，前三位是接入号，一般对应不同运营商的子品牌；中间四位是ＨＬＲ识别号，表示用户号的归属地；最后四位才是真正的用户号，所以我们可以选择后四位成为哈希地址，对其在进行相应操作来减少冲突。

数字分析法适合处理关键字位数比较大的情况，事先知道关键字的分布且关键字的若干位分布均匀。

3、哈希冲突（哈希碰撞）

3.1、闭散列（开放地址法）

闭散列，也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

Hi=(H(*key) + Di) mod m ，(i = 1,2,3,….,k k<=m-1)，其中H（key）为哈希函数；m为哈希表表长；Di为增量序列

3.1.1、线性探测再散列（Linear probing）

Di = 1,2,3,…,m-1

3.1.2、二次探测再散列

Di = 1²，－１²，２²，－２²，。。。，±ｋ²，（k<= m/2)

3.1.2、伪随机数探测再散列

Di = 伪随机数序列

3.2、开散列（拉链法，Separate chaining）

开散列法，又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

3.3、公共溢出区法

设立两个表：基础表和溢出表。将所有关键字通过哈希函数计算出相应的地址。然后将未发生冲突的关键字放入相应的基础表中，一旦发生冲突，就将其依次放入溢出表中即可。

在查找时，先用给定值通过哈希函数计算出相应的散列地址后，首先与基本表的相应位置进行比较，如果不相等，再到溢出表中顺序查找。

备注：Switch lookup table很多采用公共溢出区法来处理哈希冲突，一张大的SRAM基础表和一张小的BCAM溢出表。

4、4-way Hash

4-way Hash指的是一个哈希值对应哈希表中的4个地址（一般是连续地址）。

之所以采用4-way hash，而不用one-way hash是因为采用4-way Hash能在发生冲突的时候仍然可以保存，而不至于一发生哈希冲突就抛弃。