数据结构与算法之美
王争
前 Google 工程师
283752 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?

装载因子
双重散列
二次探测
线性探测
不同键值散列值不同
相同键值散列值相同
非负整数
链表法
开放寻址法
散列函数设计要求
散列值
hash(key)
散列表是数组的扩展
数组支持随机访问
查找相同字符串
按访问次数给URL排序
单词拼写检查功能实现
散列冲突
散列函数
散列思想
思考题
散列表

该思维导图由 AI 生成,仅供参考

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

散列思想

散列表的英文叫“Hash Table”,我们平时也叫它“哈希表”或者“Hash 表”,你一定也经常听过它,我在前面的文章里,也不止一次提到过,但是你是不是真的理解这种数据结构呢?
散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。
我用一个例子来解释一下。假如我们有 89 名选手参加学校运动会。为了方便记录成绩,每个选手胸前都会贴上自己的参赛号码。这 89 名选手的编号依次是 1 到 89。现在我们希望编程实现这样一个功能,通过编号快速找到对应的选手信息。你会怎么做呢?
我们可以把这 89 名选手的信息放在数组里。编号为 1 的选手,我们放到数组中下标为 1 的位置;编号为 2 的选手,我们放到数组中下标为 2 的位置。以此类推,编号为 k 的选手放到数组中下标为 k 的位置。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

散列表(Hash Table)是一种利用数组支持按照下标随机访问数据的数据结构,通过散列函数将元素的键值映射为数组下标,实现快速查找。本文介绍了散列表的基本原理和实现方式,包括散列函数设计、散列冲突的解决方法(开放寻址法和链表法)等。开放寻址法通过重新探测空闲位置解决冲突,而链表法则将相同散列值的元素放入同一链表中。文章还提到了装载因子的概念,以及散列表在实际应用中的案例,如单词拼写检查功能的实现。读者通过本文可以快速了解散列表的基本原理和实现方式,以及散列函数设计和散列冲突解决的相关知识。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(289)

  • 最新
  • 精选
  • Smallfly
    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)。

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

    2018-10-31
    118
    1669
  • 黄金的太阳
    请教老师,当我在查找元素时候,在相同散列值的链表中遍历如何区分哪个是我要找的元素?毕竟查找时查询条件只包含KEY的信息吧

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

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

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

    2018-11-19
    4
    35
  • 这么写的闫
    当散列冲突,表中存储了多个相同散列值时,查询数据怎么确定查询到的是我想要的那个? 这一点很疑惑,求指点

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

    2018-11-05
    3
    30
  • 吴彪
    为什么数组的存储空间有限,也会加大散列冲突的概率呢?hash函数得出来的散列值相同的概率应该是很低的,比如git hash-object,几乎不可能有碰撞,为啥在散列表里碰撞的可能性就这么大

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

    2018-10-31
    2
    11
  • 之城
    既然说散列表使用了数组的随机访问的优势,那么它如何保证hash函数计算后的hash值集中地位于内存中的一块连续区域,而不是七零八落散落在内存各处呢?对,我问的就是散列函数是怎么回事。😄

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

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

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

    2018-11-04
    2
    9
  • 唐朝农民
    Word 单词验证 是不是用 Trie 树更好,大神讲讲这个数据结构,尤其是编码这块

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

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

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

    2019-09-23
    2
    7
  • Gavin黄炯鹏
    开放寻址法查找那里,我希望通过key得到y的值,我都不知道y是多少,只有key,所以与y比较的究竟是什么?

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

    2019-04-12
    3
收起评论
显示
设置
留言
99+
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部