数据结构和算法之——散列表上

散列表的英文叫 "Hash Table"，我们也叫它 “哈希表” 或者 “Hash 表”。

1. 散列思想？

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。

假如我们有 100 名选手参加运动会，参赛号码从 0~99。为了方便记录查询成绩，我们将参赛号码为 0 的选手的成绩放在数组下标为 0 的位置，参赛号码为 1 的选手的成绩放在数组下标为 1 的位置，以此类推。

这样，当我们想要查找某个选手的成绩时，我们只需要取出数组中该选手参赛号码对应下标的数值即可，时间复杂度为 $O(1)$，效率非常高。

在这个例子中，参赛号码是自然数，并且与数组的下标形成一一映射，这其实就有了散列的思想。

但事实上，有时候我们不能直接将编号作为数组下标，比如参赛选手的编号可能为 051167，05 表示年级，11 表示班级，67 表示序号。

这时候，我们可以通过截取参赛编号的后两位作为下标，当查询选手信息的时候，我们用同样的方法，取出后两位数字，作为数组下标来读取数据。

这就是典型的散列思想。其中，参赛选手的编号我们叫作键（key）或关键字，我们用它来标识一个选手。而把参赛编号转化为数组下标的映射方法就叫作散列函数（或 “Hash 函数”，“哈希函数”），而散列函数计算得到的值就叫作散列值（或 “Hash 值”，“哈希值”）。

散列表其实就是通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素的时候，我们用同样的散列函数，将键值转化为数组下标，从对应下标位置的数组中取数据。

2. 散列函数？

散列函数在散列表中起着非常关键的作用。

上面两个例子中的散列函数都比较简单，也很容易理解。但如果参赛选手的编号是随机生成的 6 位数字，又或者是字符时，我们该如何构造散列函数呢？

散列函数有以下三个基本要求：

• 散列函数计算得到的散列值是一个非负整数
• 如果 $key1 = key2，那么 hash(key1) = hash(key2)$
• 如果 $key1 \not= key2，那么 hash(key1) \not= hash(key2)$

第一点和第二点都非常好理解，第三点要求看起来合情合理，但在真实情况下，要想找到一个不同 key 值对应的散列值都不一样的散列函数，几乎是不可能的。而且，因为数组的存储空间有限，也会加大散列冲突的概率。因此，我们需要通过其他途径来解决散列冲突问题。

3. 散列冲突？

再好的散列函数也无法避免散列冲突，常用的解决蛋类冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。

3.1. 开放寻址法

开放寻址发的核心思想就是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。

线性探测（Linear Probing） 就是当我们往散列表中插入数据时，如果计算得到的散列值对应的位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

看下面的例子，橙色表示已经有元素，黄色表示空闲。当计算新插入的 x 的散列值为 7 时，我们发现数组中下标为 7 的地方已经有数据了，于是我们就依次向后查找，遍历到尾部都没有找到空闲位置。我们再从头开始查找，直到找到数组第 2 个位置空闲，我们就将 x 插入到这个地方。

在散列表中查找元素的过程与插入类似，我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，那说明就是我们要查找的元素；否则就顺序往后依次查找，若遍历到数组中的空闲位置还没有找到，说明要查找的元素并没有在散列表中。

散列表跟数组一样，不仅支持插入、查找操作，还支持删除操作。对于使用线性探测解决冲突的散列表，删除操作稍微有点特别，我们不能单纯地把要删除的元素设置为空。

因为在查找的过程中，一旦我们遍历到数组中的空闲位置，我们就认定数据不在散列表中。但如果这个空闲位置是我们后来删除的，就会导致我们的查找算法失效，本来存在的数据也会被认定为不存在。

我们可以将删除的元素特殊标记为 deleted，然后当我们查找到标记为 deleted 的位置时，我们不是停下来，而是继续往下探测。

线性探测存在很大的问题，当散列表中插入的数据越来越多时，散列冲突的可能性就会越来越大，空闲位置越来越少，线性探测的时间也会越来越久。

除了线性探测，还有另外两种比较经典的探测方法，二次探测（Quadratic Probing）和双重探测（Double Probing）。

所谓二次探测，就是说每次探测的步长变成了原来的二次方，也就是说，它探测的下标序列变为 $hash(key) + 0, hash(key) + 1^2, hash(key) + 2^2 ……$。

所谓双重探测，就是说每次不仅仅使用一个散列函数，当第一个散列函数计算得到的存储位置被占用的时候，再使用第二个散列函数，以此类推，直到找到空闲的位置。

不管采用哪种探测方法，当散列表中的空闲位置不多时，散列冲突的概率就会大大提高。我们引入一个装载因子（load factor）来表示散列表中空位的多少 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度。装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

3.2. 链表法

链表法是一种更加常用的散列表冲突解决方法，相比开放寻址法，它要简单很多。

在散列表中，每个桶（bucket）或者槽（slot）会对应一条链表，所有散列值相同的元素会放到相同槽位对应的链表中。

向散列表中插入数据的时间复杂度为 $O(1)$，而查找或者删除的时间复杂度则与链表的长度 k 成正比。

4. Word 文档中单词拼写检查功能是如何实现的？

常见的英文单词有 20 万个左右，我们可以将这些常见单词建立起一个散列表。当用户输入某个英语单词时，我们拿用户输入的单词去散列表中查找，如果查到则说明拼写正确，如果没有查到，则说明拼写可能有误给予提示。

参考资料-极客时间专栏《数据结构与算法之美》

获取更多精彩，请关注「seniusen」!