数据结构算法笔记#4.2:哈希表

这次来聊一聊哈希表(Hash Table)。哈希表本身不难理解，所以我就做点简单的介绍。

哈希表

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

看这些概念或许有点凌乱，但我们举个例子就能很快明白了：假设有一组数据 15, 24, 16, 32, 40 要进行存储，此时我们就可以开放一个数组 int HashTable[7] ，并设计哈希函数 index = key % 10 ，就容易算出 index(15) = 5 ，index(24) = 4 ，index(16) = 6 ，index(32) = 2 ，index(40) = 0 ，并按照这些角标进行存储，得到 HashTable = [40, 0, 32, 0, 24, 15, 16] 。

接下来我来介绍两个比较典型的哈希函数构造方法。

哈希函数

直接定址法

直接定址法的哈希函数为 index = key * a + b ，其中a与b都是自由取的变量。一般用于 地址数组长度>=key值个数 的情况。

除留取余法

除留取余法的哈希函数为 index = key % p ，其中p为自由取的变量。上方例子用的就是除留取余法，只不过p值取的不太恰当，导致容易出现冲突的情况（如20与30），所以一般情况下，p的取值为 素数或不含20以下素因子的合数 。

但不论取的哈希函数有多么恰当，难免还是会出现冲突，那么我再来介绍一下几种处理冲突的方法。

冲突处理

开放定址法

所谓开放定址法，便是对哈希函数做略微修改，使其按规律不断地计算地址，直到找到一个空余的地址，此时的哈希函数可以写作 index = (key + di) % p = key % p + di % p ，di即为第i次计算时的增量，一般情况下有两种取法：

线性探测再散列： di = c * i ，其中c为常数
二次探测再散列： di = 1², -1², 2², -2² ...

举个例子，假如我们要将 16, 22, 29 三个数存进 int HashTable[3] 当中，并取哈希函数为 index = (key + di) % 3, di = 2*i，首先存入16，得到 HashTable = [0, 16, 0] ，其次存入22，计算 (22+0)%3=1 ，但 HashTable[1] 已经被 16 所占据，我们便要进行第一次开放定址，此时 di = 2 * 1 = 2 ，计算得 index = (22+2)%3 = 0 ，发现 HashTable[0] 为空，便将22存入，接着将29存入，得到 HashTable = [22, 16, 29] 。