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)。展开作者回复: 👍 这条留言可以顶上去了 其他同学都看看吧
33 821
2018-10-31今天学习了散列表的原理，以及两种解决hash冲突的方法：开放地址法和链表法。
课后思考题第一题，我觉得可以用hash表的链表法解决。访问次数作为slot，访问次数相同的URL放入同一个slot所对应的一条链表中，这样只需要扫一遍所有的URL就排好序了，时间复杂度为O(n)
第二题跟老师讲的word拼写检查有点像，我觉得可以将一个字符串数组做成hash表，然后扫描另一个字符串数组，就能找到重复的字符串。制作和扫描hash表的算法复杂度都是O(n) 1 51
2018-10-31总结：
一、散列表的由来？
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的散列值对应的字符串就是两个数组中相同的字符串。展开 1 43- 2018-10-31Redis的字典是使用链式法来解决散列冲突的，并且使用了渐进式rehash的方式来进行哈希表的弹性扩容（https://cloud.tencent.com/developer/article/1353754，请大家斧正）。
两道思考题使用哈希表都可以解决，第二道题也可以对字符串数组进行排序后使用双指针判断，但字符串的比较成本较高，如果是整数类型更加适用。另外，哈希表比较经典的应用还有bitmap和布隆过滤器，其中布隆过滤器也可以用于文本判重，但是有一定的误判概率，可以根据场景使用。 28 
2018-10-31看到链表那一块感觉是hashmap的实现原理呀 28
2018-11-10关于100万URL排序问题？
我看了半天置顶的回答，没太明白。
url为key，出现次数count为value。数组的下标为hash(key)得到的值，保存的内容为count。
排序阶段根据count排序，不是只是改变count的位置么，对应的地址没有改变啊。
如果说散列表是链表法的形式，难道排序的时候也会改变链表的头指针地址？那再要查找对应url的访问次数不就不行了。 4 23
2018-10-31请教老师，当我在查找元素时候，在相同散列值的链表中遍历如何区分哪个是我要找的元素？毕竟查找时查询条件只包含KEY的信息吧作者回复: 相同散列值 但是key不同的 可以再对比key
10 22
2018-10-31关于课后习题，基于某种语言的sdk实现起来可能比较容易，显然老师问的是思想，下面是我的理解，望老师和大家指正。
习题1，先分组累加次数再排序: 遍历10万数据，通过hash把相同url分组到同一个bucket下，如果bucket已存在，则取出已有次数+当前次数后再set进去，遍历完了整体再排序。
习题2，显然不是循环嵌套循环，那样时间复杂度不可接受。应该分别独立遍历两个数组，通过hash把相同的字符串扔到同一个bucket, 完了之后统计bucket长度＞1的就行了。 1 16
2018-11-05当散列冲突，表中存储了多个相同散列值时，查询数据怎么确定查询到的是我想要的那个？
这一点很疑惑，求指点作者回复: 再全量对比 因为散列表中存储的不仅仅是哈希值 还有全量的数据信息
11
2018-11-19有个疑问，如果在冲突的位置的下一个空闲位置存储数据，文中提到，根据key算出的位置存储的值和要查询的数据进行对比，确定是否是要查询的数据，如果我已经知道了要查询的数据，应该就不用查询了吧，这个地方不大理解。作者回复: 表述的不准确 我的意思是散列表中存储对象 对象包含key和附属字段 根据key构建散列表 查询的时候也是根据key 但是同一个散列值可能对应多个key 在查询的时候不能仅仅通过key的散列值 还要对比key
1 10
2018-10-31可以写代码进行分析讲解不，这样更能感受到 9
2019-01-01假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？
1.访问次数作为key，URL和访问次数作为存储对象，存在散列表中。解决冲突的方法使用链表法，相当于实现了对URL根据访问次数进行了分组。
2.将信息存储在散列表中的过程中，构造数组，数组元素是访问次数。在存入散列表的过程中，如果出现散列冲突，就不将该次数放入到数组中。
3.使用快速排序对数组进行排序。排序后的数组相当于是排序后的URL，即利用次数可以索引到该访问次数对应的URL。 1 6- 2018-11-02Word 单词验证 是不是用 Trie 树更好，大神讲讲这个数据结构，尤其是编码这块
作者回复: 马上就要讲了 别急
6 
2018-11-01个人的疑问：
1. 关于开放空间的散列冲突：既然存在散列冲突问题，插入时可以通过分配新的 key 来插入存在散列冲突的元素，那么在访问时又是如何解决散列冲突的呢？比如有两个键值对 {key1: val1}, {key2: val2} 它们的 key 在生成时是冲突的，key2 经过重新分配，现在访问 {key2: val2} 时应该如何通过hash函数得到正确的 key2 呢？假如删除 {key1: val1}，现在要访问 {key2: val2} ，那么执行 hash(string) 后得到的 key1 并不存在，应该怎么实现对 {key2: val2} 的正确访问呢？ 6
2018-11-23在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。这个问题如何解决呢？
这句话不理解，这不正是删除的效果么。。。设置为空，下次查找的时候当然不在了啊，已经删除了啊。。。 3 5
2018-11-04老师，关于置顶的那个回答有些疑问。
比如第一题的解答说到“url为key，出现次数为value”
我的疑问是，hash(key)=VALUE，这个VALUE经过处理后不应该是一个随机的数组的下标吗？然后把出现次数value存入到这个位置中并不断更新。我对上面那句话的理解是hash(url)=value，所以为什么可以把出现次数作为value，value不应该是一个随机值吗？还是这个value本来就不是那个VALUE？作者回复: value并不是hash函数的值。更好的表述应该是声明一个count字段
5
2018-11-02老师，有个问题请教下。开放寻址法查询的时候，碰到散列表为空的位置后，就不继续往后找了吗？这样设计不合理吧，因为存储的时候，存数据的散列表的位置是随机的，空的位置后面也许存了数据呢？如果是继续找的话，那为什么删除数据后，要进行特殊标记，这样标记也没意义啊，反正碰到空的位置，还是会继续找，这样标不标记都无所谓啊？ 2 5
2018-10-31思考题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进行查找，查找得到表示相同元素
谢谢！展开 5
2019-08-16在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。这个问题如何解决呢？
有好多同学不明白这段话的意思。
我举个例子看看能不能帮助大家理解。
比如哈希表中的 0 1 2 三个位置分别存储了 3 个数据，然后我删除了 1 位置上的数据。
这时候，我拿着数据 a 来进行查找了，根据散列函数计算出散列值在 0 这个位置。但是我把数据 a 和 0 位置上存储的数据比对后，发现不一致，就会前往下一个位置继续查找。然而 1 位置上已经被删除，按照规则来说，就可以断定哈希表中不能查找到我的数据。
可如果 2 位置上恰好是我要的数据呢？这样子就会有问题。如果加了 delete 标记就不会出现这个问题啦展开 1 4
2018-10-31为什么数组的存储空间有限，也会加大散列冲突的概率呢？hash函数得出来的散列值相同的概率应该是很低的，比如git hash-object，几乎不可能有碰撞，为啥在散列表里碰撞的可能性就这么大作者回复: 我们还要把散列值转化为数组下标的 单纯散列值是没法直接拿来当下标的
4