查看原文
其他

神速Hash

逃生依旧 趣谈编程 2019-03-29

面试官: 聊聊HashMap的底层


理解HashMap底层,首先应该理解Hash函数,今天我们聊聊Hash函数出现冲突的解决办法(此故事为连载形式,若没看上篇,可点击此处神速Hash阅读




链地址法

次日清晨,大臣们按时上朝,接着讨论昨日的话题


“昨日Hash函数的选择我们已经有了具体的方案了,那就只剩下冲突的解决问题了”,王大臣率先发话


“要解决冲突其实也不难,既然会有多个元素被Hash到同一个位置,而这个位置只能存储一个元素,那么我让这个位置可以存储多个元素不就可以了吗?”,何大臣说道


“哦,怎么个弄法?”王大臣问道


“用链表啊,来一个元素加一个,让这个位置存储一个指针,指向一个链表,让所有相同位置的元素都放在这个链表中”,何大臣回答道,接着又画了一个图


“在存储的时候,如果多个元素被Hash到同一位置,那么就加入到该位置所指向的链表中,如果该位置没有元素,则为null(指向空)”,何大臣解释道


“那个 1 和 6 谁先存放进来呢?”,思维缜密的王大人问道


“这个当然是6了,因为这个插入链表的时候要采用‘头插’的方式,也就是插入链表的最前面(图中里数组最近的元素)”,何大人说道


"哦,这是为什么呢?",王大人追问道


“因为经常发生这样的事情:新加入的元素很可能被再次访问到,所以放到头的话,如果查找就不用再遍历链表了”,见多识广的何大人解释道


rehash


“这样解决冲突固然好,但是也有瓶颈啊”,寡言的李大臣又发言了


“哦,什么瓶颈?”,何大人问道


“你看啊,假设咱们的Hash函数设计的非常好,能够将元素均匀Hash(散列)开来,但是当我们实际存入的值越来越多的时候,这个链表也势必越来越长,那当我们进行查找的时候,势必就会遍历链表,效率也就越来越慢”,李大臣回应道,顺便画了一个图


“这样的话,随着链表的不断增长,查询某一个元素的时间也就增加了,如果链表长度远远大于数组长度,不就和用链表存储一样了吗?”,李大臣说道


“恩恩,对,李大臣说的极是,李大臣有何高见?”,何大臣问道


“现在只能扩大数组的长度大约为原来的两倍


然后选取一个相关的新的Hash函数(比如之前使用 key % m,现在只改变一下m的值)


将旧Hash表中所有的元素通过新的Hash函数计算出新的Hash值,并将其插入到新表中(仍然使用链表),这就叫rehash吧”,李大臣说完又画了一个图


“这里的数组就扩大了近两倍,由于要大小要选素数,那就选原数组大小两倍后的第一个素数7,旧Hash表和新Hash表采用了不同的Hash函数,但相关,只是m的取值变了”李大臣解释道


“哦,这样做确实是一种办法,但是问题随之而来,就是什么时候开始rehash”,何大臣说道


装载因子 α 


“我们可以定义这样一个变量 α = 所有元素个数/数组的大小,我们叫它装载因子吧,它代表着我们的Hash表(也就是数组)的装满程度,在这里也代表链表的平均长度


比如说,我们的数组大小为 5 ,我们给里面存入 3个元素,那么  α = 3/5 =0.6, 这个Hash表装满程度为60%,平均每条链有0.6个元素,当然 α 也可以等于和大于 1 ”,李大臣说道


“哦,引入这个装载因子有何用意?”,何大臣问道


“这个装载因子代表了Hash表的装满程度,这里也可以代表链表的平均长度,那么也就可以代表查询时的时间长短了


基于此,我们为了不让查询时间长,也就是查询性能低,我们可以设置一个临界 α 值,当随着存入元素导致 α 大于这个临界 α 值的时候


我们可以通过rehash来调整当前的 α 值,使之低于我们设定的 临界 α 值,从而使我们的查询性能保持在较好的范围之内”,李大臣答道


“比如说,我们设定 临界 α = 0.7,对于一个Hash表大小为5的Hash表而言


当存入存入第四个元素的时候,α 就超出了临界 α 值,我们可以将数组长度变为11进行rehash(因为11是原表两倍后的第一个素数),使得装载因子 α 小于 0.7”,李大臣举了一个例子并画了一个图


“通过rehash我们可以使得装载因子在一定范围内,那我们的查询性能也就得到了保证了”,李大臣说道


“哦,那这个 临界的 α 值应该选择多大呢?”何大臣追问道


“这个 临界 α 如果选的小了,那数组的空间利用率就会太低,就比如说数组大小为100,α = 0.01,那装满程度为1%,99%还没有被利用


如果 α 太大了,那冲突就会很多,比如说 数组大小为 5,α = 10, 那平均每条链有10个元素,装满程度为1000%


即使Hash函数设计的合理,基本上每次存放元素的时候就会冲突,所以鉴于两者之间我觉得 0.6 - 0.9 之间是一个不错的选择,不妨选0.75吧”,李大臣回答道


大家一致同意


最后的总结


“这两天辛苦众爱卿了,你们的方案非常好,我也听了听


我们这种用Hash函数将关键字和关键字地址建立起来的映射,对我们的查找非常有帮助


其中非常重要的关键点就是:哈希函数的选择、处理冲突的方法以及装载因子调整,接下来我们把这个点子应用到我国的查找行业,我相信一定会有很大的提高”,国王做了最后的总结




    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存