数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

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

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

散列思想

散列表的英文叫“Hash Table”,我们平时也叫它“哈希表”或者“Hash 表”,你一定也经常听过它,我在前面的文章里,也不止一次提到过,但是你是不是真的理解这种数据结构呢?
散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。
我用一个例子来解释一下。假如我们有 89 名选手参加学校运动会。为了方便记录成绩,每个选手胸前都会贴上自己的参赛号码。这 89 名选手的编号依次是 1 到 89。现在我们希望编程实现这样一个功能,通过编号快速找到对应的选手信息。你会怎么做呢?
我们可以把这 89 名选手的信息放在数组里。编号为 1 的选手,我们放到数组中下标为 1 的位置;编号为 2 的选手,我们放到数组中下标为 2 的位置。以此类推,编号为 k 的选手放到数组中下标为 k 的位置。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(179)

  • 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
    25
    744
  • 五岳寻仙
    今天学习了散列表的原理,以及两种解决hash冲突的方法:开放地址法和链表法。
    课后思考题第一题,我觉得可以用hash表的链表法解决。访问次数作为slot,访问次数相同的URL放入同一个slot所对应的一条链表中,这样只需要扫一遍所有的URL就排好序了,时间复杂度为O(n)
    第二题跟老师讲的word拼写检查有点像,我觉得可以将一个字符串数组做成hash表,然后扫描另一个字符串数组,就能找到重复的字符串。制作和扫描hash表的算法复杂度都是O(n)
    2018-10-31
    1
    49
  • 姜威
    总结:
    一、散列表的由来?
    1.散列表来源于数组,它借助散列函数对数组这种数据结构进行扩展,利用的是数组支持按照下标随机访问元素的特性。
    2.需要存储在散列表中的数据我们称为键,将键转化为数组下标的方法称为散列函数,散列函数的计算结果称为散列值。
    3.将数据存储在散列值对应的数组下标位置。
    二、如何设计散列函数?
    总结3点设计散列函数的基本要求
    1.散列函数计算得到的散列值是一个非负整数。
    2.若key1=key2,则hash(key1)=hash(key2)
    3.若key≠key2,则hash(key1)≠hash(key2)
    正是由于第3点要求,所以产生了几乎无法避免的散列冲突问题。
    三、散列冲突的解放方法?
    1.常用的散列冲突解决方法有2类:开放寻址法(open addressing)和链表法(chaining)
    2.开放寻址法
    ①核心思想:如果出现散列冲突,就重新探测一个空闲位置,将其插入。
    ②线性探测法(Linear Probing):
    插入数据:当我们往散列表中插入数据时,如果某个数据经过散列函数之后,存储的位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。
    查找数据:我们通过散列函数求出要查找元素的键值对应的散列值,然后比较数组中下标为散列值的元素和要查找的元素是否相等,若相等,则说明就是我们要查找的元素;否则,就顺序往后依次查找。如果遍历到数组的空闲位置还未找到,就说明要查找的元素并没有在散列表中。
    删除数据:为了不让查找算法失效,可以将删除的元素特殊标记为deleted,当线性探测查找的时候,遇到标记为deleted的空间,并不是停下来,而是继续往下探测。
    结论:最坏时间复杂度为O(n)
    ③二次探测(Quadratic probing):线性探测每次探测的步长为1,即在数组中一个一个探测,而二次探测的步长变为原来的平方。
    ④双重散列(Double hashing):使用一组散列函数,直到找到空闲位置为止。
    ⑤线性探测法的性能描述:
    用“装载因子”来表示空位多少,公式:散列表装载因子=填入表中的个数/散列表的长度。
    装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。
    3.链表法(更常用)
    插入数据:当插入的时候,我们需要通过散列函数计算出对应的散列槽位,将其插入到对应的链表中即可,所以插入的时间复杂度为O(1)。
    查找或删除数据:当查找、删除一个元素时,通过散列函数计算对应的槽,然后遍历链表查找或删除。对于散列比较均匀的散列函数,链表的节点个数k=n/m,其中n表示散列表中数据的个数,m表示散列表中槽的个数,所以是时间复杂度为O(k)。
    四、思考
    1.Word文档中单词拼写检查功能是如何实现的?
    字符串占用内存大小为8字节,20万单词占用内存大小不超过20MB,所以用散列表存储20万英文词典单词,然后对每个编辑进文档的单词进行查找,若未找到,则提示拼写错误。
    2.假设我们有10万条URL访问日志,如何按照访问次数给URL排序?
    字符串占用内存大小为8字节,10万条URL访问日志占用内存不超过10MB,通过散列表统计url访问次数,然后用TreeMap存储散列表的元素值(作为key)和数组下标值(作为value)
    3.有两个字符串数组,每个数组大约有10万条字符串,如何快速找出两个数组中相同的字符串?
    分别将2个数组的字符串通过散列函数映射到散列表,散列表中的元素值为次数。注意,先存储的数组中的相同元素值不进行次数累加。最后,统计散列表中元素值大于等于2的散列值对应的字符串就是两个数组中相同的字符串。
    2018-10-31
    1
    39
  • leo
    Redis的字典是使用链式法来解决散列冲突的,并且使用了渐进式rehash的方式来进行哈希表的弹性扩容(https://cloud.tencent.com/developer/article/1353754,请大家斧正)。
    两道思考题使用哈希表都可以解决,第二道题也可以对字符串数组进行排序后使用双指针判断,但字符串的比较成本较高,如果是整数类型更加适用。另外,哈希表比较经典的应用还有bitmap和布隆过滤器,其中布隆过滤器也可以用于文本判重,但是有一定的误判概率,可以根据场景使用。
    2018-10-31
    27
  • 醉比
    看到链表那一块感觉是hashmap的实现原理呀
    2018-10-31
    24
  • 追风者
    关于100万URL排序问题?
    我看了半天置顶的回答,没太明白。
    url为key,出现次数count为value。数组的下标为hash(key)得到的值,保存的内容为count。
    排序阶段根据count排序,不是只是改变count的位置么,对应的地址没有改变啊。
    如果说散列表是链表法的形式,难道排序的时候也会改变链表的头指针地址?那再要查找对应url的访问次数不就不行了。
    2018-11-10
    3
    23
  • 黄金的太阳
    请教老师,当我在查找元素时候,在相同散列值的链表中遍历如何区分哪个是我要找的元素?毕竟查找时查询条件只包含KEY的信息吧

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

    2018-10-31
    8
    21
  • 他城之途
    关于课后习题,基于某种语言的sdk实现起来可能比较容易,显然老师问的是思想,下面是我的理解,望老师和大家指正。
    习题1,先分组累加次数再排序: 遍历10万数据,通过hash把相同url分组到同一个bucket下,如果bucket已存在,则取出已有次数+当前次数后再set进去,遍历完了整体再排序。
    习题2,显然不是循环嵌套循环,那样时间复杂度不可接受。应该分别独立遍历两个数组,通过hash把相同的字符串扔到同一个bucket, 完了之后统计bucket长度>1的就行了。
    2018-10-31
    1
    16
  • 这么写的闫
    当散列冲突,表中存储了多个相同散列值时,查询数据怎么确定查询到的是我想要的那个?
    这一点很疑惑,求指点

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

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

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

    2018-11-19
    1
    9
  • 万里晴空
    可以写代码进行分析讲解不,这样更能感受到
    2018-10-31
    9
  • 回家
    假设我们有 10 万条 URL 访问日志,如何按照访问次数给 URL 排序?
    1.访问次数作为key,URL和访问次数作为存储对象,存在散列表中。解决冲突的方法使用链表法,相当于实现了对URL根据访问次数进行了分组。
    2.将信息存储在散列表中的过程中,构造数组,数组元素是访问次数。在存入散列表的过程中,如果出现散列冲突,就不将该次数放入到数组中。
    3.使用快速排序对数组进行排序。排序后的数组相当于是排序后的URL,即利用次数可以索引到该访问次数对应的URL。
    2019-01-01
    1
    6
  • 唐朝农民
    Word 单词验证 是不是用 Trie 树更好,大神讲讲这个数据结构,尤其是编码这块

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

    2018-11-02
    6
  • Ionizing
    个人的疑问:
    1. 关于开放空间的散列冲突:既然存在散列冲突问题,插入时可以通过分配新的 key 来插入存在散列冲突的元素,那么在访问时又是如何解决散列冲突的呢?比如有两个键值对 {key1: val1}, {key2: val2} 它们的 key 在生成时是冲突的,key2 经过重新分配,现在访问 {key2: val2} 时应该如何通过hash函数得到正确的 key2 呢?假如删除 {key1: val1},现在要访问 {key2: val2} ,那么执行 hash(string) 后得到的 key1 并不存在,应该怎么实现对 {key2: val2} 的正确访问呢?
    2018-11-01
    6
  • 张三丰
    在查找的时候,一旦我们通过线性探测方法,找到一个空闲位置,我们就可以认定散列表中不存在这个数据。但是,如果这个空闲位置是我们后来删除的,就会导致原来的查找算法失效。本来存在的数据,会被认定为不存在。这个问题如何解决呢?

    这句话不理解,这不正是删除的效果么。。。设置为空,下次查找的时候当然不在了啊,已经删除了啊。。。
    2018-11-23
    2
    5
  • 肖小强
    老师,关于置顶的那个回答有些疑问。
    比如第一题的解答说到“url为key,出现次数为value”
    我的疑问是,hash(key)=VALUE,这个VALUE经过处理后不应该是一个随机的数组的下标吗?然后把出现次数value存入到这个位置中并不断更新。我对上面那句话的理解是hash(url)=value,所以为什么可以把出现次数作为value,value不应该是一个随机值吗?还是这个value本来就不是那个VALUE?

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

    2018-11-04
    5
  • ALAN
    老师,有个问题请教下。开放寻址法查询的时候,碰到散列表为空的位置后,就不继续往后找了吗?这样设计不合理吧,因为存储的时候,存数据的散列表的位置是随机的,空的位置后面也许存了数据呢?如果是继续找的话,那为什么删除数据后,要进行特殊标记,这样标记也没意义啊,反正碰到空的位置,还是会继续找,这样标不标记都无所谓啊?
    2018-11-02
    1
    5
  • Monday
    思考题1:
    1、先计算出每个URL访问次数
        思路最好是使用Java的HashMap<String,Integer>这个结果,key为URL,value为访问次数; 每次put之前先get一把,若不存在value为1,若存在value=value+1。若直接用hash(URL)获取散列值做为数组下标,如若出现哈希冲突,会使得URL的访问次数统计不正确,当然可以使用链表法来解决冲突,也就是Java中HashMap一样解决方法。
    2、再通过桶排序进行排序(使用访问次数做为桶编号)
    思考题2:
    假设两个数组为A和B,快速查找相同字符串的思路如下
    1)遍历A并将元素存入散列表HA中
    2)遍历B中每个元素并在散列表HA进行查找,查找得到表示相同元素

    谢谢!
    2018-10-31
    5
  • 小先生
    在查找的时候,一旦我们通过线性探测方法,找到一个空闲位置,我们就可以认定散列表中不存在这个数据。但是,如果这个空闲位置是我们后来删除的,就会导致原来的查找算法失效。本来存在的数据,会被认定为不存在。这个问题如何解决呢?

    有好多同学不明白这段话的意思。

    我举个例子看看能不能帮助大家理解。

    比如哈希表中的 0 1 2 三个位置分别存储了 3 个数据,然后我删除了 1 位置上的数据。
    这时候,我拿着数据 a 来进行查找了,根据散列函数计算出散列值在 0 这个位置。但是我把数据 a 和 0 位置上存储的数据比对后,发现不一致,就会前往下一个位置继续查找。然而 1 位置上已经被删除,按照规则来说,就可以断定哈希表中不能查找到我的数据。

    可如果 2 位置上恰好是我要的数据呢?这样子就会有问题。如果加了 delete 标记就不会出现这个问题啦
    2019-08-16
    1
    4
  • 吴彪
    为什么数组的存储空间有限,也会加大散列冲突的概率呢?hash函数得出来的散列值相同的概率应该是很低的,比如git hash-object,几乎不可能有碰撞,为啥在散列表里碰撞的可能性就这么大

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

    2018-10-31
    3
收起评论
99+
返回
顶部