18 | 散列表（上）：Word文档中的单词拼写检查功能是如何实现的？
该思维导图由 AI 生成，仅供参考
散列思想
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
散列表（Hash Table）是一种利用数组支持按照下标随机访问数据的数据结构，通过散列函数将元素的键值映射为数组下标，实现快速查找。本文介绍了散列表的基本原理和实现方式，包括散列函数设计、散列冲突的解决方法（开放寻址法和链表法）等。开放寻址法通过重新探测空闲位置解决冲突，而链表法则将相同散列值的元素放入同一链表中。文章还提到了装载因子的概念，以及散列表在实际应用中的案例，如单词拼写检查功能的实现。读者通过本文可以快速了解散列表的基本原理和实现方式，以及散列函数设计和散列冲突解决的相关知识。
《数据结构与算法之美》，新⼈⾸单¥68
全部留言(289)
- 最新
- 精选
Smallfly1. 假设我们有 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-311181669
黄金的太阳请教老师，当我在查找元素时候，在相同散列值的链表中遍历如何区分哪个是我要找的元素？毕竟查找时查询条件只包含KEY的信息吧作者回复: 相同散列值 但是key不同的 可以再对比key
2018-10-311340
王荣慧有个疑问，如果在冲突的位置的下一个空闲位置存储数据，文中提到，根据key算出的位置存储的值和要查询的数据进行对比，确定是否是要查询的数据，如果我已经知道了要查询的数据，应该就不用查询了吧，这个地方不大理解。作者回复: 表述的不准确 我的意思是散列表中存储对象 对象包含key和附属字段 根据key构建散列表 查询的时候也是根据key 但是同一个散列值可能对应多个key 在查询的时候不能仅仅通过key的散列值 还要对比key
2018-11-19435
这么写的闫当散列冲突，表中存储了多个相同散列值时，查询数据怎么确定查询到的是我想要的那个？ 这一点很疑惑，求指点作者回复: 再全量对比 因为散列表中存储的不仅仅是哈希值 还有全量的数据信息
2018-11-05330
吴彪为什么数组的存储空间有限，也会加大散列冲突的概率呢？hash函数得出来的散列值相同的概率应该是很低的，比如git hash-object，几乎不可能有碰撞，为啥在散列表里碰撞的可能性就这么大作者回复: 我们还要把散列值转化为数组下标的 单纯散列值是没法直接拿来当下标的
2018-10-31211
之城既然说散列表使用了数组的随机访问的优势，那么它如何保证hash函数计算后的hash值集中地位于内存中的一块连续区域，而不是七零八落散落在内存各处呢？对，我问的就是散列函数是怎么回事。😄作者回复: 通过取模的方式，限定在了0~n范围内
2019-07-2110
肖小强老师，关于置顶的那个回答有些疑问。 比如第一题的解答说到“url为key，出现次数为value” 我的疑问是，hash(key)=VALUE，这个VALUE经过处理后不应该是一个随机的数组的下标吗？然后把出现次数value存入到这个位置中并不断更新。我对上面那句话的理解是hash(url)=value，所以为什么可以把出现次数作为value，value不应该是一个随机值吗？还是这个value本来就不是那个VALUE？作者回复: value并不是hash函数的值。更好的表述应该是声明一个count字段
2018-11-0429- 唐朝农民Word 单词验证 是不是用 Trie 树更好，大神讲讲这个数据结构，尤其是编码这块
作者回复: 马上就要讲了 别急
2018-11-028 
Angus没有理解为什么散列冲突产生的具体原因是什么，所以后面讲到为何空闲位置减少发生散列冲突的几率就增加了，这块有点疑惑。作者回复: 因为散列表中槽的个数一般都小于要放入的数据的个数，根据鸽巢原理，总会有冲突的情况。
2019-09-2327
Gavin黄炯鹏开放寻址法查找那里，我希望通过key得到y的值，我都不知道y是多少，只有key，所以与y比较的究竟是什么？作者回复: 比如：你希望在一堆订单order中快速地根据id来查询订单数据，你可以把订单组织成散列表结构。散列表中存储订单的id和指向订单本身的地址。 你去查询的时候，也是按照id来查询的。只不过在散列表中，会先将id映射成hash值。
2019-04-123
