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

精选留言(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