数据结构与算法之美_18_散列表(上):Word文档中的单词拼写检查功能是如何实现的?

深渊向深渊呼唤

先看个问题:Word 的拼写检查功能是如何实现的?

散列思想

散列表的英文叫“Hash Table”,也叫“哈希表”或者“Hash 表”。

散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,有数组演化而来。可以说,如果没有数组,就没有散列表。

举个例子。假如我们有 89 名选择参加校运会。为了方便记录成绩,每个选手胸前有自己的参赛号码。这些选手的编号依次是 1 到 89。要实现通过编号快速找到对应选手的信息,如何做?

可以把这 89 名选手信息放入数组,编号为 1 的选手,放入数组下标为 1 的位置;编号 2 的选手放到数组下标为 2 的位置。以此类推,编号为 k 的选手放到数组下标为 k 的位置。

因为参数编号与数组下标一一对应,当我们需要查询参赛编号为 x 的选手时,只需要按照下标为 x 的数组元素取出来就可以了,时间复杂度是 O(1)。

这个例子已经用到了散列的思想。参赛编号是自然数,并且与数组的下标一一映射,利用数组的随机访问时间复杂度是 O(1) 特性,可以实现快速查找编号对应的选手信息。

如果参赛编号不能设置这么简单,要加上年级、班级等信息构成了 6 位数字的编号,比如 051167,其中,前两位 05 代表年级,中间 11 表示班级,最后两位还是原来的编号。这个时候我们该如何存储选手信息?

思路还是和前面类似,我们可以截取参赛编号的后两位作为数组下标,来存取选手信息。

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

image

规律:散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询数据时,我们同样利用散列函数,将键值转化为数组下标,从对应的数组下标的位置取数据。

散列函数

散列函数,我们定义成 hash(key),key 表示元素的键值,hash(key) 的值表示经过散列函数计算得到的散列值。

第一个列子中,编号就是数组下标,所以 hash(key) 就等于 key。改造后的例子的散列函数伪代码如下:

int hash(String key) {
  // 获取后两位字符
  string lastTwoChars = key.substr(length-2, length);
  // 将后两位字符转换为整数
  int hashValue = convert lastTwoChas to int-type;
  return hashValue;
}

如果现在参赛选手的编号是随机生成的 6 位数字,又或者是 a 到 z 之间的字符串,该如何构造散列函数?

散列函数设计的基本要求:

    散列函数计算得到的散列值是一个非负整数; 如果 key1 == key2,那 hash(key1) == hash(key2); 如果 key1 != key2,那 hash(key1) != hash(key2)。

对于其中第三点,真实情况下,要想找到一个不同的 key 对应的散列值都不一样的散列函数,几乎是不可能的。即使是著名的 MD5、SH、CRC 等哈希算法,也无法避免这种散列冲突。

而且,因为数组的存储空间有限,也会加大散列冲突的概率。

散列冲突

常用的散列冲突解决的办法有:开放寻址法、链表法。

1. 开放寻址法

开放寻址法的核心思想是,如果出现了算列冲突,我们就重新探测一个空闲位置,将其插入。重新探测的方法有:线性探测、二测探测、双重散列。

线性探测

当我们往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。

下图中黄色的色块表示空闲位置,橙色的色块表示已经存储了数据。

image

从图中可以看出,散列表的大小为 10,在元素 x 插入散列表之前,已经有 6 个元素插入到散列表中了。x 经过散列算法之后,被散列到位置为 7 的位置,但是这个位置已经有数据了,所以就产生了冲突。于是我们就顺序的往后一个一个的找,看有没有空闲位置,遍历到尾部都没有找到空闲位置,于是再从表头开始找,直到找到空闲位置 2,于是将其插入这个位置。

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

image

对于使用线性探测法解决冲突的散列表,删除操作稍微特别些。我们不能单纯地把要删除的元素设置为空。

因为在查找的时候,一旦我们通过线性探测方法,找到一个空闲位置,我们就可以认定散列表中不存在这个数据。但是,如果这个空闲位置是我们后来删除的,就会导致原来的查找算法失效。本来存在的数据,会被定为不存在。

针对这个问题,我们可以将删除的元素,特殊标记为 deleted。当线性探测查找的时候,遇到标记为 deleted 的空间,并不是停下来,而是继续往下探测。

image

线性探测其实存在很大的问题。当散列表中插入的数据越来越多时,散列冲突发生的可能性就会越大,空闲位置会越少,线性探测的时间会越久。极端情况下,我们可能需要探测整个散列表,所以最坏情况的时间复杂度为 O(n)。同理,在删除和查找时,也有可能会线性探测整张散列表,才能找到要查找和删除的数据。

对于开放寻址冲突解决方法,除了线性探测方法之外,还有另外两种比较经典的探测方法,二次探测和双重散列。

二次探测

二次探测,跟线性探测很像,线性探测每次探测的步长是 1,它探测的下标序列就是 hash(key)+0,hash(key)+1,hash(key)+2......而二次探测的步长就是原来的“二次方”,即它探测的下标序列就是 hash(key)+0,hash(key)+1^2,hash(key)+2^2......

双重散列

双重散列就是不仅使用一个散列函数。我们使用一组散列函数 hash1(key),hash2(key),hash3(key)......我们先用第一个散列函数,如果计算得到的存储位置已经被占用,再用第二个散列函数,依次类推,直到找到空闲的存储位置。

不论哪种探测方法,当散列表中空闲位置不多时,散列冲突的概率会大大提高。为了尽可能保证散列表的操作效率,一般情况下,我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子(laod factor)来表示空位的多少。

装载因子的计算公式是:

算列表的装载因子 = 填入表中的元素个数 / 散列表的长度

装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。

2. 链表法

链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它更加简单。

在散列表中,每个“桶(bucket)”或者“槽(slot)”会对应一条链表,所以散列值相同的元素我们都放到相同槽位对应的链表中。

image

在插入的时候,我们只需要通过散列函数计算对应的散列槽位,将其插入到对应链表中即可,所以插入的时间复杂度是 O(1)。当查找、删除一个元素时,我们同样通过散列函数计算出对应的槽,然后遍历链表查找或者删除。

查找和删除操作的时间复杂度和链表的长度 k 成正比,也就是 O(k)。对于散列比较均匀的散列函数来说,理论上讲,k=n/m,n 表示散列中数据的个数,m 表示散列表中“槽”的个数。

解决开篇

Wrod 文档中单词拼写检查功能是如何实现的?

常用的英文单词有 20 万个左右,假设单词平均长度是 10 个字母,平均每个单词占用 10 byte 的内存空间,那 20 万英文单词大约占 20MB 存储空间。我们用散列表来存储整个英文单词词典。

当用户输入某个英文单词时,我们拿用户输入的单词去散列表中查找。如果查到,则说明拼写正确;如果没有查到,则说明拼写错误,给予提示。

内容小结

散列表来源于数组,它借助散列函数对数组这种数据结构进行扩展,利用的是数组支持按照下标随机访问元素的特性。散列表的两个核心问题是散列函数设计和散列冲突解决。散列冲突有两种常用的解决方法,开放寻址法和链表法。散列函数设计的好坏决定散列冲突的概略,也就决定了散列表的性能。

下一节会更加深入的探讨散列函数和散列冲突这两个问题。

课后思考

    假设有 10 万条 URL 访问日志,如何按照访问次数给 URL 排序?

答: 遍历 10 万条数据,以 URL 为 key,访问次数为 value,存储散列表,同时记录下访问次数最大值 k,时间复杂度 O(n)。

如果 k 不是大,可以使用桶排序,时间复杂度 O(n)。如果 k 非常大(比如大于 10 万),就是用快速排序,时间复杂度 O(nlogn)。

    有两个字符串数组,每个数组大约有 10 万条字符串,如何快速找出两个数组中相同的字符串?

答: 以第一个字符串数组固件散列表,key 为字符串,value 为出现的次数。再遍历第二个字符串,以字符串为 key 在散列表中查找,如果 value 大于零,说明存在相同字符串,时间复杂度为 O(n)。

栏目