• Smallfly
    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
  • leo
    2018-10-31
    Redis的字典是使用链式法来解决散列冲突的,并且使用了渐进式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-02
    Word 单词验证 是不是用 Trie 树更好,大神讲讲这个数据结构,尤其是编码这块

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

    
     6
  • Ionizing
    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
  • ALAN
    2018-11-02
    老师,有个问题请教下。开放寻址法查询的时候,碰到散列表为空的位置后,就不继续往后找了吗?这样设计不合理吧,因为存储的时候,存数据的散列表的位置是随机的,空的位置后面也许存了数据呢?如果是继续找的话,那为什么删除数据后,要进行特殊标记,这样标记也没意义啊,反正碰到空的位置,还是会继续找,这样标不标记都无所谓啊?
     2
     5
  • Monday
    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
我们在线,来聊聊吧