散列查找(哈希表)基础讲解

温馨提示：由于简书不能解析 LaTex 公式，所以为了良好的阅读体验，强烈建议各位读者跳转到我的个人博客平台阅读 散列查找(哈希表)基础讲解，谢谢！

背景：还记得上个月面试官问我能不能谈谈哈希表，然后我就说了”数组+链表“。然后就再也憋不出任何一句话了，因为数据结构我刚好学到二叉树，一段黑历史了。不说了，现在补上之前没有填上的坑......

---

引子

相信大家多多少少肯定会对查找算法有些了解，比如顺序查找、二分查找、利用“二叉搜索树”查找等等。顺序查找适用于数据量不大的时候；二分查找虽然时间复杂度较为乐观，但前提是数据元素已经按照关键字排序并且存储在连续的地址空间中；二叉搜索树查找具有相当不错的时间复杂度，但有时需要附加条件。那这样我们就需要一种适应性广而速度又快的查找算法。这就是本篇要讲的散列查找。

其实我们生活中有许多例子也是运用到了散列查找的精髓。举个栗子，我们琢磨一下查英文字典的过程，其实这个过程结合了散列查找、二分查找和顺序查找这几种查找方法。

基本概念

讲解基本概念之前，我们再回到查字典这个例子。我们会根据所查单词的首字母去字典的检索表获取该单词所在位置大概在整本字典的哪一部分。然后再翻到大概页面仔细查找相对应的单词。而在散列查找的概念，上面所说的单词首字母就是散列查找中的“关键词”(key)。然后通过“散列函数”求出关键词所在的存储位置(value)。但我们也得重点说明一下查字典时我们事先“估计”关键词的“大致位置”，而散列函数“计算”的是关键词的“准确位置”。

hash diagram

散列查找之所以能够通过计算来快速定位要找的关键词，一个基本的前提是在存放的时候也要通过同样的“计算方法”来定位存储的位置。

从抽象的数据类型的角度看，上表实际上就是一张符号表(Symbol Table)，我们也称它为散列表或哈希表(Hash Table)。它定义为“名字-属性”对的集合。名字和属性的含义随着应用的不同而不同，

符号表的抽象数据类型描述为：

类型名称：符号表(SymbolTable)

数据对象集：符号表是“名字(Name)-属性(Attribute)”对的集合

操作集：对于一个具体的符号表 $ Table \in SymbolTable $，一个给定名字 $Name \in NameType$，属性 $Attr \in AttributeType$，以及正整数 $TableSize$，符号表的基本操作主要有

• SymbolTable CreateTable(int TableSize)-创建空的符号表，其最大长度为 TableSize
• boolean IsIn(SymbolTable Table,NameType Name)-查找指定名字Name 是否在符号表中，若是返回true；否则返回false
• AttributeType Find(SymbolTable Table,NameType Name)-获取符号表Table中指定名字Name对应的属性
• boolean Modify(SymbolTable Table,NameType Name,AttributeType Attr)-将Table中指定名字Name的属性修改为Attr。成功返回true；找不到Name则返回false
• boolean Insert(SymbolTable Table,NameType Name,AttributeType Attr)-向Table中插入一个新名字Name及其属性Attr。成功则返回true；若Name已存在则返回false
• boolean Delete(SymbolTable Table,NameType Name)-从Table中删除一个名字Name 及其属性。成功返回true；找不到Name则返回false

散列(Hashing)是一种重要的查找算法。它的基本思想是：以数据对象的关键词 key 为自变量，通过一个确定的函数关系 $h$ ,计算出对应的函数值 $h(key)$ ，把这个值解释为数据对象的存储地址，并按此存放，即“$存储位置=h(key)$”。

在查找某数据对象时，有函数 $h$ (也称为哈希函数)对给定值 key 计算出地址，将 key 与该地址单元中数据对象关键字进行比较，确定查找是否成功。因此散列法又称为“关键字-地址转换法”。

说到这里，读者可能会有疑问：如果有两个（或更多）关键词通过某散列函数计算出相同的存储位置，那又该怎么办？总不能把多个多个关键词对应的信息都存放在相同的位置吧？我们把这种情况叫做冲突。因此，我们还需要研究解决冲突的方法。这就引出了后面我们要讲的散列查找法的两个基本内容：

1.如何构造散列函数

2.如何解决冲突

散列函数的构造方法

一个“好”的散列函数一般应考虑下列两个因素：

1.计算简单，以便提高转换速度

2.关键词对应的地址空间分布均匀，以尽量减少冲突。

关键词可分为数字型关键词和字符串型关键词这两种类型

数字关键词的散列函数构造

构造这类散列函数只不过把原来的数字按某种规律转换成另一个数字

直接定址法

$$ h(key)=a \times key + b (a、b为常数) $$

这类函数计算简单，分布均匀，不会产生冲突，但要求地址集合与关键词集合大小相同，因此对于较大的关键词集合不适用。

除留余数法

假设散列表长为 TableSize（TableSize 的选取，通常由关键词集合的大小 $n$ 允许最大装填因子 $\alpha$ 决定），选择一个正整数 $p \leq TableSize$ ，散列函数为：

$$
h(key)= key \bmod p
$$

设散列表空间大小为 $m$ ，填入表中的元素个数是 $n$，则称 $\alpha = n/m$ 为散列表的装填因子。一般散列表大小设计使得 $\alpha=0.5 \sim0.8$为宜

使用除留余数法，选取合适的 $p​$ 很重要，一般选取 $p​$ 为小于或等于散列表表长 $TableSize​$ 的某个最大素数比较好。用素数求得的余数作为散列地址，比较均匀分布在整个地址空间上的可能性比较大。

大家也可能注意到如果 $p < TableSize$ ，则意味着地址 $p \sim TableSize -1$ 是不能通过散列函数直接映射到的。

数字分析法

如果数字关键词的位数比较多，我们可以根据实际情况将关键词中随机性比较大的位数提取出来形成一个新的关键词。例如 11 位手机号，前 3 位和中间 4 位在一定范围内很容易发生重复。所以直接选取最后 4 位作为散列地址。如果 4 位正整数太大，不适合作为地址，可以结合前面的除留余数法再做一次转换。

手机号码各位数含义

字符串关键词的散列函数构造

简单的散列函数——ASCII 码加和法

$$
h(key)=(\sum key[i]) \bmod TableSize
$$

函数很简单，然而均匀性也较差。但仔细研究一下你会发现关键词集合元素可能性个数大大超过存储的散列地址个数。显然冲突会是很严重的，特别是关键词集合元素个数比较大的情况下。

简单的改进——前 3 个字符移位法

我们改进一下上面的散列函数
$$
h(key)=(key[0]+key[1]\times 27+key[2]\times 27^{2})
$$
这里我们先假设字符串的每个字符只有不分大小的英文字母（26个）和空格符（1个）。函数仅考虑关键词的前 3 个字符。若忽略空格符不急，则前 3 位所有可能的不同组合为 $26^{3}=17576$ 种，似乎该数字不大。但是现实生活中英文不是随机的，真正的英文单词中前 3 位的不同组合大约不到 3000 种。这样不仅难以确定 $TableSize$ 大小而且具有相同的前 3 个字符的不同关键词一定会发生冲突。显然这个还不是很合适。

好的散列函数——移位法

$$
h(key)=(\sum_{i=0}^{{n-1}key[n-i-1]\times32}i)\bmod TableSize
$$

这个散列函数涉及关键词的所有 $n$ 个字符，并且分布得很好。每位字符占 5 位(即 $2^5=32$)。具体实现时并不需要一一做乘法运算，而是通过将每位字符转换成 二进制 ASCII 码值，通过一次左移 5 位来完成，低位补 0 ，得到的二进制结果再转换成十进制数值，这就是字符 ASCII 码值乘以一次 32 的结果。

移位法求积

处理冲突的方法

在前面的散列函数构造过程中，我们努力使散列地址均匀分布于整个地址空间，但是实际应用中，冲突不可避免只能减少。因此我们应该研究如何解决冲突的问题。

开放定址法

假如你打算在某个小区买套房子住，根据你的生辰八字(关键词)，风水先生(散列函数)告诉你 8-801 最适合你。正准备下单的时候，开发商却告诉你说该房子已被人预定（冲突发生）。此时我们可能会看看其他附近其他套房子。这就是开放定址法。

所谓开放地址法，就是一旦产生了冲突，即改地址已经存放了其他数据元素，就去寻找另一个空的散列地址。在没有装满的散列表中，空的散列地址是有的，但是怎么去找，这是我们应该考虑的因素之一

一般来说，如果关键词经过散列函数得出散列地址后发现有冲突，那么就需要试探性散列函数去试试其他附近的散列地址是否是空的。如果还发生冲突的话就再次使用试探性散列函数再去试试其他散列地址。试探性散列函数的基本公式是：
$$
p_i(key)=(h(key)+d_i)\bmod TableSize (1\leq i < TableSize)
$$
上面式子中，$i$ 表示冲突次数。根据 $d_i$ 的选取方式不同，我们可以得到不同的解决冲突方法。上面的地址必须对 $TableSize$ 取余。

线性探测法

我们举个栗子，某个关键词 $key$ 经过散列函数 $h$ 获得散列地址 $h(key)$ 。但是发现该散列地址不是空的，发生了第一次冲突，此时 $d_1=1$ 。这时候我们就需要使用试探性散列函数去获取试探性散列地址 $p_1(key)$ 。如果 $p_1(key)$ 散列地址也不是空的，就发生了第二次冲突,此时 $d_2=2$ 求得 $p_2(key)$ 散列地址再去尝试。以此类推，我们可以得出 $d_i=i$ ，确定 $d_i$ 取值之后再不断用试探性散列函数去尝试新的散列地址直到没有发生冲突为止。这就是线性试探法。

线性试探法可能使第 $i$ 个散列地址的同义词存入第 $i+1$ 个散列地址，也就说本应存入第 $i$ 个散列地址的数据对象变成了第 $i+1$ 个散列地址的同义词。因为线性试探就是不断在发生冲突的地方附近一一试探，因此极容易出现很多元素在相邻的散列地址上“堆积”起来的叫做“一次聚集”的现象，这种现象会大大降低查找效率。为减轻这种一次聚集效应，可采用下面讲解的平方探测法或双散列探测法。

平方探测法

按上面的流程，如果 $d_i =\pm i^{2}$ ，即 $d_i$ 的取值依次为 $1^{2}$，$-1{2}$ ，$2^{2}$ ，$-2^{2}$ ，... ，$q^{2}$ ，$-q^{2}$ 且 $q \leq [TableSize/2]$ 去不断试探下一个存储地址的形式就是平方探测法。我们需要注意一点的就是散列表长度 $TableSize$ 是某个 $4k+3$ ($k$ 是正整数)形式的素数时能保证平方探测法可以探查到这个散列空间。这个是平凡探测法的理论基础。

双散列探测法

如果公式 $p_i(key)$ 中的 $d_i=i \times h_2(key)$ ，其中 $h_2(key)$ 是另一个散列函数。我们就把它叫做双散列探测法。而第二个散列函数 $h_2(key)$ 的选取至关重要，要确保 $h_2(key)$ 都不能是 0 值，否则所有探测都是同一个位置。我们同时也需要保证所有的散列存储单元都应该能够被探测到，一般形如
$$
h_2(key)=p-(key \bmod p)(p是小于TableSize 的素数)
$$
的 $h_2(key)$ 函数具有良好的探测效果。采用双散列探测法会增加探测过程中的计算量，但其期望的探测次数比较少，这使得它在理论上很有吸引力。不过平方探测法不需要计算第二个散列函数，从而在实践中可能更简单又实用。

再散列法

开放地址法的装填因子 $\alpha$ 会严重影响查找效率，由于表长在一定时间是定值，$\alpha$ 与“填入表中的元素个数”成正比，所以 $\alpha$ 越大填入表中的元素越多，产生冲突的可能性就越大。减少冲突是提高查找速度的直接因素，因为散列表的查找过程基本上与建表过程相同。一些关键词可通过散列函数转换的地址直接找到，另一些关键词在散列函数得到的地址上产生了冲突，需要按处理冲突的方式进行查找。因此加倍扩大散列表减少冲突是一种提高查找效率的方法，此方法的过程就叫做再散列(Rehashing)。

再散列需要新建一个新的两倍大的散列表，再将原表中的数据重新计算分配到新表中。这个过程集中花费时间长，体现在交互系统的现象就是使人感觉系统有“停顿”现象。这种现象在一些实时系统中是致命的，例如医用的生命保障系统中，设备的短暂“停顿”可能导致严重后果，所以需谨慎使用。此时可以采用不需要再散列的“分离链接法”。

分离链接法

分离链接法(Separate Chaining)是解决冲突的另一种方法，其做法是将所有关键词为同义词(散列地址一致的关键词)的数据对象通过结点链接存储在同一个单链表中。

Separate Chaining

最后

懂得基本的数据结构与算法是程序猿的必备素养，学习数据结构与算法的方式也有多种多样。浙江大学计算机系的数据结构的网络课程是个相当不错在线课程，课程还提供了在线编程平台PTA，感兴趣的朋友可以去看看。

最后是广告时间，我的原创博文将同步更新在三大平台上，欢迎大家点击阅读！谢谢

刘志宇的新天地

简书

稀土掘金