哈希表原理

什么是hash

一句话就是,一个关键字 key 通个一个函数 f 的计算得到一个值。其中,这个关键字就是我们要存储的任何东西;函数 f 被称为哈希函数;计算出的值是作为存储位置使用的,被称为哈希地址或散列地址。

哈希函数

哈希函数要求为关键字通过哈希可以得到一个“随机的地址”。

1. 直接定址法

直接使用有关关键字的某个线性函数值为哈希地址。即 $ Hash(key) = a * key + b $。 因为哈希地址集合与关键字集合的大小相同,所以不同的关键字之间不会发生冲突。但是在实际中能够使用直接定址法的情况很少。

2. 数字分析法

要求关键字是以 r 为基的数字,分析所有关键字中随机的部分组成哈希地址。具体看严蔚敏《数据结构(C语言版)》适用情况:关键字某些部分不随机,其他部分比较随机。

3. 平方取中法

取关键字平方后的中间几位为哈希地址。适用情况:通常不一定都能知道关键字的全部情况。

4. 折叠法

将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后这几部分叠加求和(舍去进位)作为哈希地址。适用情况:关键字位数较多,而且关键字每一位上数字分布大致均匀。折叠法中有两种方法:

  1. 移位叠加

    国际标准图书编号0-442-20586-4移位叠加的4位哈希地址为 $ 5864 + 4220 + 04 = (1)0088 $。

  2. 间界叠加

    国际标准图书编号0-442-20586-4间界叠加的4位哈希地址为 $ 5864 + 0224 + 04 = 6092 $。

5. 除留余数法

取关键字被某个不大于哈希表表长 m 的数 p 除后所得余数为哈希地址。即 $ H(key) = key  MOD  p, p <= m $。不仅可以对关键字直接取模(MOD),也可以在折叠平方取中等运算后取模(MOD)。 p 的选择对于除留余数法很关键,若 p 选得不好,容易产生冲突。详细例子 使用除留余数法的一个经验是,若散列表表长为 m,通常 p 为小于或等于表长(最好接近 m )的最大质数或不包含小于 20 质因子的合数。

6. 基数转换法

如果关键字 key 是整数,那么可以通过将 key 的 A 进制形式当作是 B 进制形式,然后再转换成 A 进制形式,最后再结合平方取中、折叠等方法获得哈希地址。 例子,(864579578)10 看成 (864579578)16 = (36043199864)10,再用间界折叠法计算 4 位哈希地址,即 $ 9864 + 9134 + 360 = (1)9358 $。

7. 字符串数值哈希法

推荐使用 BKDRHash 算法。详情见行云——字符串哈希函数MyZee——各种Hash函数冲突率分析

1
2
3
4
5
6
7
8
9
10
11
// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}

哈希冲突解决

开放定址法

$ H_i = (H(key) + d_i) MOD m  i = 1,2,...,k (k  m-1)$。其中,H(key) 为哈希函数;m 为哈希表表长;di 为增量序列。

  1. 线性探测再散列

    di = 1, 2, ..., m-1,平均查找长度 $ S_{nl} (1+ ) $

  2. 二次探测再散列

    di = 12, -12, 22, -22, 32, ..., k2(或-k2) (k<=m/2) ,平均查找长度 $ S_{nr} - ln(1-a)$

  3. 伪随机探测再散列

    d = 伪随机数序列

再哈希法

$ H_i = RH_i(key)  i=1,2,...,k $

RHi 均是不同的哈希函数,在关键字产生地址冲突时计算另一个哈希函数地址,直到冲突不再发生。

链地址法

将所有关键字为同义词的记录存储在同一线性链表中。平均查找长度 $ S_{nc} 1+$

建立一个公共溢出区

将同义词填入溢出表,查找时去遍历溢出表。

参考以及推荐

[1] YoungerChina——【整理】hash算法原理及常见函数

[2] C语言实现的数据结构之------哈希表

本文结束感谢您的阅读
感谢打赏,继续前行!