散列表(上):单词拼写检查功能如何实现

1. 散列思想

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

散列

2. 散列函数

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

该如何构造散列函数?有三点基本要求:

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

第一、二点很好理解,第三点实际上几乎不可能,因为它无法避免散列冲突。

3. 散列冲突

解决方法:开放寻址法和链表法。

开放寻址法

核心思想是,如果出现了散列冲突,就重新探测一个空闲位置,将其插入。探测方法有线形探测、二次探测和双重散列。

开放寻址法

线性探测

  • 插入数据:当我们往散列表中插入数据时,如果某个数据经过散列函数之后,存储的位置已经被占用了,就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。
  • 查找数据:通过散列函数求出要查找元素的键值对应的散列值,然后比较数组中下标为散列值的元素和要查找的元素是否相等。如果相等,则说明就是要找的元素;否则,就顺序往后依次查找。如果遍历到数组的空闲位置还未找到,就说明要查找的元素并没有在散列表中。
  • 删除数据:为了不让查找算法失效,可以将删除的元素特殊标记为 deleted,当线性探测查找的时候,遇到标记为 deleted 的空间,并不是停下来,而是继续往下探测。

结论:最坏的时间复杂度为O(n)

二次探测

线性探测每次探测的步长为1,即在数组中一个个探测,而二次探测的步长变为原来的平方。

双重散列

使用一组散列函数,直到找到空闲位置为止。

散列表用装载因子(load factor)来表示空位的多少,计算公式是:

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

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

链表法

更加常用,比开放寻址法简单。

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

链表法

  • 插入数据:当插入的时候,通过散列函数计算出对应的散列槽位,将其插入到对应的链表中即可,所以时间复杂度为 O(1)。
  • 查找或删除数据:当查找、删除一个元素时,通过散列函数计算对应的槽,然后遍历链表查找或删除。对于散列比较均匀的散列函数,链表的节点个数 k=n/m,其中 n 表示散列表中数据的个数,m 表示散列表中槽的个数,所以时间复杂度为 O(k)。

课后思考

  1. Word 文档中单词拼写检查功能是如何实现的?
  2. 假设我们有 10 万条 URL 访问日志,如何按照访问次数给 URL 排序?
  3. 有两个字符串数组,每个数组大约有 10 万条字符串,如何快速找出两个数组中相同的字符串?

本文标题:散列表(上):单词拼写检查功能如何实现

文章作者:落英坠露

发布时间:2019年05月12日 - 20:05

最后更新:2019年05月12日 - 20:05

原始链接:https://isuperqiang.cn/2019/05/12/散列表(上):单词拼写检查功能如何实现/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

赞赏是一种行为艺术