18 | 散列表（上）：Word文档中的单词拼写检查功能是如何实现的？

2018-10-31 王争
《数据结构与算法之美》
课程介绍


讲述：冯永吉

时长:大小13.42M


Word 这种文本编辑器你平时应该经常用吧，那你有没有留意过它的拼写检查功能呢？一旦我们在 Word 里输入一个错误的英文单词，它就会用标红的方式提示“拼写错误”。Word 的这个单词拼写检查功能，虽然很小但却非常实用。你有没有想过，这个功能是如何实现的呢？
其实啊，一点儿都不难。只要你学完今天的内容，散列表（Hash Table）。你就能像微软 Office 的工程师一样，轻松实现这个功能。

散列思想

散列表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“Hash 表”，你一定也经常听过它，我在前面的文章里，也不止一次提到过，但是你是不是真的理解这种数据结构呢？
散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
我用一个例子来解释一下。假如我们有 89 名选手参加学校运动会。...

展开全文
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。

精选留言

  • Smallfly
    2018-10-31
    1. 假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？ 遍历 10 万条数据，以 URL 为 key，访问次数为 value，存入散列表，同时记录下访问次数的最大值 K，时间复杂度 O(N)。 如果 K 不是很大，可以使用桶排序，时间复杂度 O(N)。如果 K 非常大（比如大于 10 万），就使用快速排序，复杂度 O(NlogN)。 2. 有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串？ 以第一个字符串数组构建散列表，key 为字符串，value 为出现次数。再遍历第二个字符串数组，以字符串为 key 在散列表中查找，如果 value 大于零，说明存在相同字符串。时间复杂度 O(N)。

    作者回复: 👍 这条留言可以顶上去了 其他同学都看看吧

    共 99+ 条评论
    1694
  • 黄金的太阳
    2018-10-31
    请教老师，当我在查找元素时候，在相同散列值的链表中遍历如何区分哪个是我要找的元素？毕竟查找时查询条件只包含KEY的信息吧

    作者回复: 相同散列值 但是key不同的 可以再对比key

    共 13 条评论
    43
  • 王荣慧
    2018-11-19
    有个疑问，如果在冲突的位置的下一个空闲位置存储数据，文中提到，根据key算出的位置存储的值和要查询的数据进行对比，确定是否是要查询的数据，如果我已经知道了要查询的数据，应该就不用查询了吧，这个地方不大理解。

    作者回复: 表述的不准确 我的意思是散列表中存储对象 对象包含key和附属字段 根据key构建散列表 查询的时候也是根据key 但是同一个散列值可能对应多个key 在查询的时候不能仅仅通过key的散列值 还要对比key

    共 4 条评论
    35
  • 这么写的闫
    2018-11-05
    当散列冲突，表中存储了多个相同散列值时，查询数据怎么确定查询到的是我想要的那个？ 这一点很疑惑，求指点

    作者回复: 再全量对比 因为散列表中存储的不仅仅是哈希值 还有全量的数据信息

    共 3 条评论
    32
  • 吴彪
    2018-10-31
    为什么数组的存储空间有限，也会加大散列冲突的概率呢？hash函数得出来的散列值相同的概率应该是很低的，比如git hash-object，几乎不可能有碰撞，为啥在散列表里碰撞的可能性就这么大

    作者回复: 我们还要把散列值转化为数组下标的 单纯散列值是没法直接拿来当下标的

    共 2 条评论
    12
  • 之城
    2019-07-21
    既然说散列表使用了数组的随机访问的优势，那么它如何保证hash函数计算后的hash值集中地位于内存中的一块连续区域，而不是七零八落散落在内存各处呢？对，我问的就是散列函数是怎么回事。😄

    作者回复: 通过取模的方式，限定在了0~n范围内

    
    11
  • 肖小强
    2018-11-04
    老师，关于置顶的那个回答有些疑问。 比如第一题的解答说到“url为key，出现次数为value” 我的疑问是，hash(key)=VALUE，这个VALUE经过处理后不应该是一个随机的数组的下标吗？然后把出现次数value存入到这个位置中并不断更新。我对上面那句话的理解是hash(url)=value，所以为什么可以把出现次数作为value，value不应该是一个随机值吗？还是这个value本来就不是那个VALUE？

    作者回复: value并不是hash函数的值。更好的表述应该是声明一个count字段

    共 2 条评论
    9
  • 唐朝农民
    2018-11-02
    Word 单词验证 是不是用 Trie 树更好，大神讲讲这个数据结构，尤其是编码这块

    作者回复: 马上就要讲了 别急

    
    9
  • Angus
    2019-09-23
    没有理解为什么散列冲突产生的具体原因是什么，所以后面讲到为何空闲位置减少发生散列冲突的几率就增加了，这块有点疑惑。

    作者回复: 因为散列表中槽的个数一般都小于要放入的数据的个数，根据鸽巢原理，总会有冲突的情况。

    共 2 条评论
    7
  • Gavin黄炯鹏
    2019-04-12
    开放寻址法查找那里，我希望通过key得到y的值，我都不知道y是多少，只有key，所以与y比较的究竟是什么？

    作者回复: 比如：你希望在一堆订单order中快速地根据id来查询订单数据，你可以把订单组织成散列表结构。散列表中存储订单的id和指向订单本身的地址。 你去查询的时候，也是按照id来查询的。只不过在散列表中，会先将id映射成hash值。

    
    3