本文共 4404 字，大约阅读时间需要 14 分钟。

1. 什么是哈希表

   回顾前面学习的线性表的顺序查找，二分查找，二叉排序树，平衡二叉树在查找某个关键字key时，都需要从数据表中进行挨个比较，直到相等时，则说明查找成功并返回该关键字的下标位置，在这个查找过程中，不同的查找算法需要比较的次数也不同，查找性能也是不一样的。

   那么思考这么一个问题：我们在查找某个关键字key的过程中，这些比较是否真的有必要？是否有更好的办法：例如直接通过某个关键字key计算出该关键字的存储地址，从而找到数据？

   因此，我们需要另一种解决方案：哈希表。

  哈希表又称散列表，是一种散列存储结构，用于关键字和存储地址之间建立一种对应关系h，每个关键字key对应一个存储地址（loc），即loc = h（key）。

图1

  如图1所示，我们可以把这个关系h（key）理解为是一个哈希函数（又称为散列函数），而哈希函数的作用就是根据关键字key，计算得出一个内存单元的存储地址（或下标）。

图2

  理想的哈希表是一个具有固定大小的数组（连续存储空间），例如存储n个关键字的集合{

$k_1,k_2......k_n$}，哈希表的大小为m，将关键字$k_i（0 ≤ i ≤ n-1）$映射到哈希表从0到m-1范围内，并且存储到合适的内存单元中。这个映射过程就是用哈希函数h将关键字映射到哈希表中，而h($k_i$)这个存储地址称为哈希地址（散列地址）。

  因此通过哈希表求解查找问题时，不需要比较，而是直接通过关键字和哈希函数直接找到存储位置，提高了查找效率。但是在理想情况下，哈希表的哈希函数应该计算起来简单，并且应该保证不同的关键字映射到不同的内存单元中。不过，这是不可能的，因为单元的数目是有限的，而关键字实际上是用不完的，一旦超过单元的数目，那么关键字映射到的单元就会出现重复，这也说明了设计一个合理的哈希函数显得尤为重要。

  还要考虑一个问题是：对于两个关键字$k_i$和$k_j$，$i≠j$，且$k_i≠k_j$，但是$h(k_i)=h(k_j)$时，这种现象叫做哈希冲突。这种具有不同关键字而具有相同哈希地址的对象称做“同义词”，引起的冲突称作同义词冲突。

  如图2所示，当选择的两个不同关键字$k_2$和$k_5$会映射到同一个哈希地址时就叫做哈希冲突，而这种情况是有可能会发生的，我们需要考虑怎么避免哈希冲突。

   但实际上同义词冲突很难避免，除非关键字的变化区间小于等于哈希地址的变化区间（例如：对于100个关键字，哈希表提供了200个单元存储空间，这样所有的关键字在映射时，就不会超过哈希表的单元的数目），但是这种情况当关键字取值不连续时是非常浪费存储空间的。

2. 构造哈希函数

  哈希函数的构造方法一般有以下几种：直接定址法，除留余数法，数字分析法等等 …… 还有很多其他的方法，这里就不一一列举了

  而构造哈希函数的目标则是：使得到的哈希地址，尽可能均匀地分布在n个连续内存单元地址上，同时使计算过程尽可能简单，以达到尽可能高的时间效率。

2.1直接定址法

直接定址法思想：以关键字k本身或关键字加上或减去某个数值常量c作为哈希地址的方法。

直接定址法的哈希函数：h(k) = k - c

图3-直接定址法

  示例：h(学号) = 学号 - 201001001

  在这个示例中，以每个学生的学号作为关键字，把201001001作为常量C，用每个学生的学号减去常量C来计算每个学生信息的哈希地址，映射关系如图3所示。

  比如：对于张三来说，201001001 - 201001001 = 0，那么就把张三的信息存储到下标0的位置。对于李四来说201001003 - 201001001 = 2，把李四的信息存储在下标2的位置，王五同理。

2.2 数字分析法

  数字分析法思想：提取关键字中取值较均匀的数字位作为哈希地址的方法。适合于所有关键字值都已知的情况，并需要对关键字中每一位的取值分布情况进行分析。

图4-数字分析法

  例如有一组关键字，每个关键字从左到右的第1、2、3位和第6位取值较集中，不容易区分，因此不宜作为哈希函数，剩余的第4、5、7和8位取值较分散，容易区分，可根据实际需要取其中的若干位作为哈希地址，因此我们取7和8两位作为哈希地址。

2.3 除留余数法

除留余数法思想：用关键字k除以p(某个不大于哈希表长度m的数)， 所得的余数作为哈希地址。

除留余数法的哈希函数：h(k)=k mod p (mod为求余运算，p ≤ m)，p最好是质数（素数）

图5-除留余数法

示例：h(区号)=VAL(区号) mod 7

  在这个示例中，把每个城市的区号转换为VAL区号，以区号作为关键字k，p的值取7，用区号对p进行取余，来计算每个城市的哈希地址H（key）。比如：对于北京市的区号为010，我们把010转换为VAL（区号）10，然后通过哈希函数10 mod 7 得到哈希地址为3，那么把区号为010城市的数据存储到城市哈希表中下标为3的位置。

  除留余数法是比较常用的构造哈希函数方法，但是这个方法的关键在于选择合适的p，如果p的取值不好的话，那么将可能会容易产生同义词，也就是哈希冲突，下面我们通过一个除留余数法的示例来说明。

3. 示例—除留余数法

  假设哈希表长度m=13，采用除留余数法哈希函数建立如下关键字集合的哈希表：{16,74,60,43,54,90,46,31,29,88,77}。

  n=11表示要保存的关键字个数，m=13表示单元的个数。

  确定除留余数法的哈希函数为：h(k)=k mod p

p的选择：应为小于等于m的素数，假设p取值13。则有：

  如上所示，对于关键字16和29来说，哈希函数计算完后，它们的存储地址产生了哈希冲突；对于关键字90和关键字77也是哈希冲突。

4. 哈希冲突

   其实到这里不难想象，即便哈希函数设计的再合理也难免会出现哈希冲突，那么引起哈希冲突的因素有哪些？我们又该怎么处理呢？

引起哈希冲突一般有以下几个原因：

   1. 与装填因子有关，通俗来讲，装填因子就是哈希表的存储空间的元素的多少，如果装填因子为1，则说明哈希表的存储空间满了。

   装填因子α = 哈希表存储的记录个数n / 哈希地址空间大小m，当α越小，存储空间的利用率就越低，则哈希冲突的可能性就越小，当α越大（最大值可取1），存储空间的利用率就越高，哈希冲突的可能性也越大。那么装填因子α的取值到底多少合适呢？ 通常在实际的工程应用中，α的取值应该考虑既兼顾减少冲突的发生，又兼顾提高存储空间的利用率，α的取值一般控制在0.6～0.9的范围内。

   2. 所采用的哈希函数有关

   若哈希函数选择合适的话，可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发生；如果哈希函数选择不当，就可能使哈希地址集中于某些区域，从而使这一区域增加冲突的发生。

  3. 与解决冲突的哈希冲突函数有关

  哈希冲突函数选择的好坏也将减少或增加发生冲突的可能性，解决哈希冲突的方法有以下几种：开放定址法，线性探测法，拉链法。

5. 开放定址法

  开放定址法：以发生冲突的哈希地址为自变量，通过某种哈希冲突函数得到一个新的空闲的哈希地址。

线性探测法又分为两种：

  1. 线性探测法，是从发生冲突的地址（设为d）开始，依次探测d的下一个地址是否为空闲单元，直到找到一个空闲单元为止（当m≥n时一定能找到一个空闲单元），当到达下标为m-1的哈希表表尾时，下一个探测的地址是下标为0的哈希表表首的位置 。

线性探测法的数学递推描述公式为：

$d_0=h(k)$ //通过这个公式，再根据key计算出首地址，是否产生哈希冲突

$d_i=(d_{i-1}+1)\;\; mod \;\;\; m \;\;\;\;(1≤i≤m-1)$ //当产生哈希冲突时，就通过该公式计算下一个地址，即探测下一个地址是否冲突。

2.平方探测法

设发生冲突的地址为d，则平方探测法的探测序列为：$d±1^2$，$d±2^2$，……

平方探测法的数学描述公式为：

$d_0=h(k)$ //通过这个公式，再根据key计算出首地址，是否产生哈希冲突

$d_i=(d_0 ± i^2) \;\; mod \;\; m \;\;\;\;\;(1≤i≤m-1)$ //当产生哈希冲突时，就通过该公式计算下一个地址，但是这个地址可能是跟首地址隔了好几个地址，也就是说并不会直接探测首地址的下一个地址。

开放定址法总结：   虽然平方探测法是一种较好的处理冲突的方法，可以避免出现堆积问题。但是它的缺点是不能探测到哈希表上的所有单元，但至少能探测到一半单元。对于线性探测法来说，可以探测到哈希表中的所有单元，但是可能会出现堆积的问题。

现在来看一个以除留余数法定址和线性探测法解决哈希冲突的例子：

  假设哈希表长度m=13，采用除留余数法哈希函数建立如下关键字集合的哈希表：{16,74,60,43,54,90,46,31,29,88,77}。

n=11表示要保存的关键字个数，m=13表示单元的个数。

确定除留余数法的哈希函数为：h(k)=k mod p

p的选择：应为小于等于m的素数，假设p取值13，有：

图6-一个示例

  当把每个关键字的哈希地址都计算出来后，就可以把每个关键字存储在对应的哈希表的地址空间中，比如关键字16存储在哈希表中下标为3的位置，关键字74存储在哈希表中下标为9的位置，关键字60放在哈希表中下标为8的位置，其他关键字以此类推……

  当在存储关键字29时，我们发现该关键字的哈希地址也是3，但是哈希表中下标为3的位置已经存储了一个关键字，那么按照线性探测法，我们探测下一个哈希地址（下标为4）不空闲，因为该地址已经存储了关键字43；于是继续探测下一个哈希地址（下标为5）还是不空闲，接着探测下一个哈希地址，发现下标为6的哈希地址是空闲的，于是把关键字29存储在哈希表中下标为6的位置。从这个过程中不难看出，在发生哈希冲突后，线性探测法在探测过程中总共探测了3次。

  对于关键字77来说，由于计算出的哈希地址已经是哈希表的尾地址，在探测下一个地址时又重新回到了哈希表的首地址，且首地址（下标为0）是空闲，并把关键字77存储在下标为0的位置。