哈希表的概念

哈希表就是：

“将记录的存储位置与它的关键字之间建立一个对应关系，使每个关键字和一个唯一的存储位置对

应。”

哈希表又称：“散列法”、“杂凑法”、“关键字：地址法”。

哈希表思想

基本思想是在关键字和存储位置之间建立一个哈希函数hash，使每一个存储位置和关键字对应。

通常关键字的集合很大，因此经过哈希函数的变换后，可能会将不同的关键字映射到同一个地址

上。这种现象称作：“冲突”，具有相同函数值的关键字称作：“同义词”。

哈希表属性

哈希函数的值域是可以使用的地址空间，称作基本区域。

基本区域的长度是哈希表的长度。

同义词可以存放在基本区域中未占用的单元，也可以放在另外开辟的地方。（溢出区）

哈希函数的构造

哈希函数的构造一般有下面几种方法：

1.直接定址法

hash(key) = key或hash(key) = a * key + b

直接定址法的构造有点像Python里面的字典。

优点:不会产生冲突

缺点:空间效率不高

2.取余法

hash(key) = key % p

p < m，m是哈希表长。

优点：计算简单，适用范围大

缺点：需要选择一个合适的p，p的选择很困难

一般来说，p是不大于m的最大素数：

3.平方取中法

先计算关键字的平方，然后取平方后数的中间几位作为地址。

key = 2587

key ** 2 = 6692569

若取三位，则hash(2587) = 925。

处理冲突的方法：

1.开放定址法

当发生冲突时，在冲突位置的前后寻找可以存放记录的空闲单元。

当用此法时，需要预先设置一个探测序列d，沿着序列d寻找空闲单元。

数学描述公式为：

H = (hash(key) + d) % m

其中探测序列d有下面三种取法：

1.d = 1,2,3,4,.....,n

2.d =

3.d = 随机数列

用的最多的是1和2。

但是使用1的时候，会导致原本不冲突的非同义词也会产生冲突，这种现象叫作：“堆积”（聚

集）。

因此减少堆积可以使用2，但是2并不能保证可以全部使用表中空闲单元，容易造成浪费。

2.拉链法

将具有相同哈希地址的记录连接成一个单链表，然后用一个数组将n个单链表头指针存储起来。

3.再哈希法

当发生冲突时，再用另一个哈希函数计算地址。

4.溢出区法

建立一个额外的公共溢出区，用来存储冲突的记录