<section class=""><mpprofile class="js_uneditable" data-pluginname="mpprofile" data-id="Mzg3MzU2Njk3MA==" data-headimg="http://mmbiz.qpic.cn/mmbiz_png/k05w3WRD08Fx0Dyhez1FdVicdUibEh5GsH0OkXWoSjialialib9iaXWykUyu1tCibly2jd776xk3STXTGUosKTylhmaxw/0?wx_fmt=png" data-nickname="IT老哥" data-alias="" data-signature="老哥是通过自学进入大厂做资深Java工程师,每天分享技术干货,助你进大厂"> <div class="appmsg_card_context wx_profile_card js_wx_profile_card" data-id="Mzg3MzU2Njk3MA==" data-isban="0" data-index="0"> <div class="wx_profile_card_bd"> <div class="wx_profile weui-flex"> <div class="wx_profile_hd"> <img class="wx_profile_avatar" src="https://upload-images.jianshu.io/upload_images/22802755-603ee2dcab017ad9.png" alt="IT老哥"> </div> <div class="wx_profile_bd weui-flex weui-flex__item"> <div class="weui-flex__item"> <strong class="wx_profile_nickname"> IT老哥 </strong> <div class="wx_profile_desc">老哥是通过自学进入大厂做资深Java工程师,每天分享技术干货,助你进大厂</div> <div class="wx_profile_tips" id="js_profile_desc"> <span class="wx_profile_tips_meta" id="js_profile_article">70篇原创内容</span> </div> </div> <i class="weui-icon-arrow"></i> </div> </div> </div> <div class="wx_profile_card_ft">公众号</div> </div> </mpprofile></section><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">有很多东西之前在学的时候没怎么注意,笔者也是在重温HashMap的时候发现有很多可以去细究的问题,最终是会回归于数学的,如HashMap的加载因子为什么是0.75?</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">本文主要对以下内容进行介绍:</p><ul data-tool="mdnice编辑器" class="list-paddingleft-2" style="margin-top: 8px;margin-bottom: 8px;padding-left: 25px;max-width: 100%;color: rgb(0, 0, 0);font-family: PingFangSC-Light;font-size: 16px;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);overflow-wrap: break-word !important;"><li style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 5px;margin-bottom: 5px;max-width: 100%;line-height: 26px;color: rgb(1, 1, 1);font-size: 15px;box-sizing: border-box !important;overflow-wrap: break-word !important;">为什么HashMap需要加载因子?</section></li><li style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 5px;margin-bottom: 5px;max-width: 100%;line-height: 26px;color: rgb(1, 1, 1);font-size: 15px;box-sizing: border-box !important;overflow-wrap: break-word !important;">解决冲突有什么方法?</section></li><li style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 5px;margin-bottom: 5px;max-width: 100%;line-height: 26px;color: rgb(1, 1, 1);font-size: 15px;box-sizing: border-box !important;overflow-wrap: break-word !important;">为什么加载因子一定是0.75?而不是0.8,0.6?</section></li></ul><h2 data-tool="mdnice编辑器" style="margin-top: 30px;margin-right: 10px;margin-bottom: 5px;font-weight: bold;font-size: 22px;max-width: 100%;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="padding-left: 10px;max-width: 100%;font-family: STHeitiSC-Light;color: rgb(14, 136, 235);font-weight: bolder;display: inline-block;border-left: 5px solid rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;">为什么HashMap需要加载因子?</span><span style="padding-left: 10px;max-width: 100%;font-family: STHeitiSC-Light;color: rgb(14, 136, 235);font-weight: bolder;display: inline-block;border-left: 5px solid rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;"></span></h2><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">HashMap的底层是哈希表,是存储键值对的结构类型,它需要通过一定的计算才可以确定数据在哈希表中的存储位置:</p><pre data-tool="mdnice编辑器" style="margin-top: 10px;margin-bottom: 10px;max-width: 100%;color: rgb(0, 0, 0);font-size: 16px;text-align: left;background-color: rgb(255, 255, 255);box-sizing: border-box !important;overflow-wrap: break-word !important;"><code style="padding: 16px;max-width: 100%;overflow-x: auto;color: rgb(171, 178, 191);background: rgb(40, 44, 52);display: -webkit-box;font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;border-radius: 0px;font-size: 12px;box-sizing: border-box !important;overflow-wrap: break-word !important;">static final int <span style="max-width: 100%;color: rgb(230, 192, 123);line-height: 26px;box-sizing: border-box !important;overflow-wrap: break-word !important;">hash</span>(Object key) {<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> int h;<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> <span style="max-width: 100%;color: rgb(230, 192, 123);line-height: 26px;box-sizing: border-box !important;overflow-wrap: break-word !important;">return</span> (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">}<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">// AbstractMap<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">public int <span style="max-width: 100%;line-height: 26px;box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="max-width: 100%;color: rgb(97, 174, 238);line-height: 26px;box-sizing: border-box !important;overflow-wrap: break-word !important;">hashCode</span></span>() {<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> int h = 0;<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> Iterator<Entry<K,V>> i = entrySet().iterator();<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> <span style="max-width: 100%;color: rgb(198, 120, 221);line-height: 26px;box-sizing: border-box !important;overflow-wrap: break-word !important;">while</span> (i.hasNext())<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> h += i.next().hashCode();<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> <span style="max-width: 100%;color: rgb(230, 192, 123);line-height: 26px;box-sizing: border-box !important;overflow-wrap: break-word !important;">return</span> h;<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">}</code></pre><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">一般的数据结构,不是查询快就是插入快,HashMap就是一个插入慢、查询快的数据结构。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">但这种数据结构容易产生两种问题:① 如果空间利用率高,那么经过的哈希算法计算存储位置的时候,会发现很多存储位置已经有数据了(哈希冲突);② 如果为了避免发生哈希冲突,增大数组容量,就会导致空间利用率不高。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">而加载因子就是表示Hash表中元素的填满程度。</p><blockquote data-tool="mdnice编辑器" style="margin-top: 20px;margin-bottom: 20px;padding: 10px 10px 10px 20px;border-left-color: rgb(92, 157, 255);color: rgb(106, 115, 125);font-size: 0.9em;max-width: 100%;font-family: PingFangSC-Light;text-align: left;white-space: normal;overflow: auto;background: rgb(249, 249, 249);box-sizing: border-box !important;overflow-wrap: break-word !important;"><p style="padding-top: 3px;padding-bottom: 3px;max-width: 100%;min-height: 1em;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;line-height: 26px;color: rgb(153, 153, 153);box-sizing: border-box !important;overflow-wrap: break-word !important;">加载因子 = 填入表中的元素个数 / 散列表的长度</p></blockquote><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">加载因子越大,填满的元素越多,空间利用率越高,但发生冲突的机会变大了;</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">加载因子越小,填满的元素越少,冲突发生的机会减小,但空间浪费了更多了,而且还会提高扩容rehash操作的次数。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">冲突的机会越大,说明需要查找的数据还需要通过另一个途径查找,这样查找的成本就越高。因此,必须在“冲突的机会”与“空间利用率”之间,寻找一种平衡与折衷。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">所以我们也能知道,影响查找效率的因素主要有这几种:</p><ul data-tool="mdnice编辑器" class="list-paddingleft-2" style="margin-top: 8px;margin-bottom: 8px;padding-left: 25px;max-width: 100%;color: rgb(0, 0, 0);font-family: PingFangSC-Light;font-size: 16px;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);overflow-wrap: break-word !important;"><li style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 5px;margin-bottom: 5px;max-width: 100%;line-height: 26px;color: rgb(1, 1, 1);font-size: 15px;box-sizing: border-box !important;overflow-wrap: break-word !important;">散列函数是否可以将哈希表中的数据均匀地散列?</section></li><li style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 5px;margin-bottom: 5px;max-width: 100%;line-height: 26px;color: rgb(1, 1, 1);font-size: 15px;box-sizing: border-box !important;overflow-wrap: break-word !important;">怎么处理冲突?</section></li><li style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 5px;margin-bottom: 5px;max-width: 100%;line-height: 26px;color: rgb(1, 1, 1);font-size: 15px;box-sizing: border-box !important;overflow-wrap: break-word !important;">哈希表的加载因子怎么选择?</section></li></ul><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">本文主要对后两个问题进行介绍。</p><h2 data-tool="mdnice编辑器" style="margin-top: 30px;margin-right: 10px;margin-bottom: 5px;font-weight: bold;font-size: 22px;max-width: 100%;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="padding-left: 10px;max-width: 100%;font-family: STHeitiSC-Light;color: rgb(14, 136, 235);font-weight: bolder;display: inline-block;border-left: 5px solid rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;">解决冲突有什么方法?</span><span style="padding-left: 10px;max-width: 100%;font-family: STHeitiSC-Light;color: rgb(14, 136, 235);font-weight: bolder;display: inline-block;border-left: 5px solid rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;"></span></h2><h3 data-tool="mdnice编辑器" style="margin-top: 30px;margin-bottom: 15px;font-weight: bold;font-size: 18px;max-width: 100%;font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);color: rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;">1. 开放定址法</h3><pre data-tool="mdnice编辑器" style="margin-top: 10px;margin-bottom: 10px;max-width: 100%;color: rgb(0, 0, 0);font-size: 16px;text-align: left;background-color: rgb(255, 255, 255);box-sizing: border-box !important;overflow-wrap: break-word !important;"><code style="padding: 16px;max-width: 100%;overflow-x: auto;color: rgb(171, 178, 191);background: rgb(40, 44, 52);display: -webkit-box;font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;border-radius: 0px;font-size: 12px;box-sizing: border-box !important;overflow-wrap: break-word !important;">Hi = (H(key) + di) MOD m,其中i=1,2,…,k(k<=m-1)</code></pre><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">H(key)为哈希函数,m为哈希表表长,di为增量序列,i为已发生冲突的次数。其中,开放定址法根据步长不同可以分为3种:</p><h3 data-tool="mdnice编辑器" style="margin-top: 30px;margin-bottom: 15px;font-weight: bold;font-size: 18px;max-width: 100%;font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);color: rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;">1.1 线性探查法(Linear Probing):di = 1,2,3,…,m-1</h3><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">简单地说,就是以当前冲突位置为起点,步长为1循环查找,直到找到一个空的位置,如果循环完了都占不到位置,就说明容器已经满了。举个栗子,就像你在饭点去街上吃饭,挨家去看是否有位置一样。</p><h3 data-tool="mdnice编辑器" style="margin-top: 30px;margin-bottom: 15px;font-weight: bold;font-size: 18px;max-width: 100%;font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);color: rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;">1.2 平方探测法(Quadratic Probing):di = ±12, ±22,±32,…,±k2(k≤m/2)</h3><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">相对于线性探查法,这就相当于的步长为di = i2来循环查找,直到找到空的位置。以上面那个例子来看,现在你不是挨家去看有没有位置了,而是拿手机算去第i2家店,然后去问这家店有没有位置。</p><h3 data-tool="mdnice编辑器" style="margin-top: 30px;margin-bottom: 15px;font-weight: bold;font-size: 18px;max-width: 100%;font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);color: rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;">1.3 伪随机探测法:di = 伪随机数序列</h3><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">这个就是取随机数来作为步长。还是用上面的例子,这次就是完全按心情去选一家店问有没有位置了。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">但开放定址法有这些缺点:</p><ul data-tool="mdnice编辑器" class="list-paddingleft-2" style="margin-top: 8px;margin-bottom: 8px;padding-left: 25px;max-width: 100%;color: rgb(0, 0, 0);font-family: PingFangSC-Light;font-size: 16px;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);overflow-wrap: break-word !important;"><li style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 5px;margin-bottom: 5px;max-width: 100%;line-height: 26px;color: rgb(1, 1, 1);font-size: 15px;box-sizing: border-box !important;overflow-wrap: break-word !important;">这种方法建立起来的哈希表,当冲突多的时候数据容易堆集在一起,这时候对查找不友好;</section></li><li style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 5px;margin-bottom: 5px;max-width: 100%;line-height: 26px;color: rgb(1, 1, 1);font-size: 15px;box-sizing: border-box !important;overflow-wrap: break-word !important;">删除结点的时候不能简单将结点的空间置空,否则将截断在它填入散列表之后的同义词结点查找路径。因此如果要删除结点,只能在被删结点上添加删除标记,而不能真正删除结点;</section></li><li style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 5px;margin-bottom: 5px;max-width: 100%;line-height: 26px;color: rgb(1, 1, 1);font-size: 15px;box-sizing: border-box !important;overflow-wrap: break-word !important;">如果哈希表的空间已经满了,还需要建立一个溢出表,来存入多出来的元素。</section></li></ul><h3 data-tool="mdnice编辑器" style="margin-top: 30px;margin-bottom: 15px;font-weight: bold;font-size: 18px;max-width: 100%;font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);color: rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;">2. 再哈希法</h3><pre data-tool="mdnice编辑器" style="margin-top: 10px;margin-bottom: 10px;max-width: 100%;color: rgb(0, 0, 0);font-size: 16px;text-align: left;background-color: rgb(255, 255, 255);box-sizing: border-box !important;overflow-wrap: break-word !important;"><code style="padding: 16px;max-width: 100%;overflow-x: auto;color: rgb(171, 178, 191);background: rgb(40, 44, 52);display: -webkit-box;font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;border-radius: 0px;font-size: 12px;box-sizing: border-box !important;overflow-wrap: break-word !important;">Hi = RHi(key), 其中i=1,2,…,k</code></pre><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">RHi()函数是不同于H()的哈希函数,用于同义词发生地址冲突时,计算出另一个哈希函数地址,直到不发生冲突位置。这种方法不容易产生堆集,但是会增加计算时间。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">所以再哈希法的缺点是:增加了计算时间。</p><h3 data-tool="mdnice编辑器" style="margin-top: 30px;margin-bottom: 15px;font-weight: bold;font-size: 18px;max-width: 100%;font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);color: rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;">3. 建立一个公共溢出区</h3><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">假设哈希函数的值域为[0, m-1],设向量HashTable[0,…,m-1]为基本表,每个分量存放一个记录,另外还设置了向量OverTable[0,…,v]为溢出表。基本表中存储的是关键字的记录,一旦发生冲突,不管他们哈希函数得到的哈希地址是什么,都填入溢出表。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">但这个方法的缺点在于:查找冲突数据的时候,需要遍历溢出表才能得到数据。</p><h3 data-tool="mdnice编辑器" style="margin-top: 30px;margin-bottom: 15px;font-weight: bold;font-size: 18px;max-width: 100%;font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);color: rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;">4. 链地址法(拉链法)</h3><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">将冲突位置的元素构造成链表。在添加数据的时候,如果哈希地址与哈希表上的元素冲突,就放在这个位置的链表上。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">拉链法的优点:</p><ul data-tool="mdnice编辑器" class="list-paddingleft-2" style="margin-top: 8px;margin-bottom: 8px;padding-left: 25px;max-width: 100%;color: rgb(0, 0, 0);font-family: PingFangSC-Light;font-size: 16px;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);overflow-wrap: break-word !important;"><li style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 5px;margin-bottom: 5px;max-width: 100%;line-height: 26px;color: rgb(1, 1, 1);font-size: 15px;box-sizing: border-box !important;overflow-wrap: break-word !important;">处理冲突的方式简单,且无堆集现象,非同义词绝不会发生冲突,因此平均查找长度较短;</section></li><li style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 5px;margin-bottom: 5px;max-width: 100%;line-height: 26px;color: rgb(1, 1, 1);font-size: 15px;box-sizing: border-box !important;overflow-wrap: break-word !important;">由于拉链法中各链表上的结点空间是动态申请的,所以它更适合造表前无法确定表长的情况;</section></li><li style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"><section style="margin-top: 5px;margin-bottom: 5px;max-width: 100%;line-height: 26px;color: rgb(1, 1, 1);font-size: 15px;box-sizing: border-box !important;overflow-wrap: break-word !important;">删除结点操作易于实现,只要简单地删除链表上的相应的结点即可。</section></li></ul><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">拉链法的缺点:需要额外的存储空间。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">从HashMap的底层结构中我们可以看到,HashMap采用是数组+链表/红黑树的组合来作为底层结构,也就是开放地址法+链地址法的方式来实现HashMap。</p><p><img class="rich_pages img_loading" data-ratio="0.48856799037304455" data-s="300,640" data-type="png" data-w="831" data-src="https://mmbiz.qpic.cn/sz_mmbiz_png/HV4yTI6PjbI5XfTsYBP2JzOrpVfb0qhuCygWNN7AvrHxWzRtsJicM06ee7OA5wjDrU2Igd1hp9AVg8rGsOu4Y7w/640?wx_fmt=png" style="color: rgb(0, 0, 0); font-family: PingFangSC-Light; font-size: 16px; text-align: left; white-space: normal; background-color: rgb(255, 255, 255); box-sizing: border-box !important; overflow-wrap: break-word !important; visibility: visible !important; width: 677px !important; height: 331.783px !important;" _width="677px" src="https://upload-images.jianshu.io/upload_images/22802755-ed1b8db534ab62fa.png" crossorigin="anonymous" alt="图片"></p><h2 data-tool="mdnice编辑器" style="margin-top: 30px;margin-right: 10px;margin-bottom: 5px;font-weight: bold;font-size: 22px;max-width: 100%;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);box-sizing: border-box !important;overflow-wrap: break-word !important;"><span style="padding-left: 10px;max-width: 100%;font-family: STHeitiSC-Light;color: rgb(14, 136, 235);font-weight: bolder;display: inline-block;border-left: 5px solid rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;">为什么HashMap加载因子一定是0.75?而不是0.8,0.6?</span><span style="padding-left: 10px;max-width: 100%;font-family: STHeitiSC-Light;color: rgb(14, 136, 235);font-weight: bolder;display: inline-block;border-left: 5px solid rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;"></span></h2><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">从上文我们知道,HashMap的底层其实也是哈希表(散列表),而解决冲突的方式是链地址法。HashMap的初始容量大小默认是16,为了减少冲突发生的概率,当HashMap的数组长度到达一个临界值的时候,就会触发扩容,把所有元素rehash之后再放在扩容后的容器中,这是一个相当耗时的操作。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">而这个临界值就是由加载因子和当前容器的容量大小来确定的:</p><blockquote data-tool="mdnice编辑器" style="margin-top: 20px;margin-bottom: 20px;padding: 10px 10px 10px 20px;border-left-color: rgb(92, 157, 255);color: rgb(106, 115, 125);font-size: 0.9em;max-width: 100%;font-family: PingFangSC-Light;text-align: left;white-space: normal;overflow: auto;background: rgb(249, 249, 249);box-sizing: border-box !important;overflow-wrap: break-word !important;"><p style="padding-top: 3px;padding-bottom: 3px;max-width: 100%;min-height: 1em;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;line-height: 26px;color: rgb(153, 153, 153);box-sizing: border-box !important;overflow-wrap: break-word !important;">临界值 = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR</p></blockquote><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">即默认情况下是16x0.75=12时,就会触发扩容操作。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">那么为什么选择了0.75作为HashMap的加载因子呢?这个跟一个统计学里很重要的原理——泊松分布有关。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">泊松分布是统计学和概率学常见的离散概率分布,适用于描述单位时间内随机事件发生的次数的概率分布。有兴趣的读者可以看看维基百科或者阮一峰老师的这篇文章:<span style="max-width: 100%;font-weight: bold;color: rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;">泊松分布和指数分布:10分钟教程</span><sup style="max-width: 100%;line-height: 0;font-weight: bold;color: rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;">[1]</p><p style="max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;font-size: 16px;white-space: normal;background-color: rgb(255, 255, 255);text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;"><img class="rich_pages img_loading" data-ratio="0.2009132420091324" data-s="300,640" data-type="png" data-w="876" data-src="https://mmbiz.qpic.cn/sz_mmbiz_png/HV4yTI6PjbI5XfTsYBP2JzOrpVfb0qhuYHRqByckV8T8wpmUENfWnxRV94gFc5iaOTSxsM4ic82ZkrCz19KLFqtQ/640?wx_fmt=png" style="box-sizing: border-box !important; overflow-wrap: break-word !important; visibility: visible !important; width: 677px !important; height: 137.616px !important;" _width="677px" src="https://upload-images.jianshu.io/upload_images/22802755-b08963bbd59390be.png" crossorigin="anonymous" alt="图片"></p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">等号的左边,P 表示概率,N表示某种函数关系,t 表示时间,n 表示数量。等号的右边,λ 表示事件的频率。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">在HashMap的源码中有这么一段注释:</p><pre data-tool="mdnice编辑器" style="margin-top: 10px;margin-bottom: 10px;max-width: 100%;color: rgb(0, 0, 0);font-size: 16px;text-align: left;background-color: rgb(255, 255, 255);box-sizing: border-box !important;overflow-wrap: break-word !important;"><code style="padding: 16px;max-width: 100%;overflow-x: auto;color: rgb(171, 178, 191);background: rgb(40, 44, 52);display: -webkit-box;font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;border-radius: 0px;font-size: 12px;box-sizing: border-box !important;overflow-wrap: break-word !important;"> Ideally, under random hashCodes, the frequency of<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> nodes <span style="max-width: 100%;color: rgb(198, 120, 221);line-height: 26px;box-sizing: border-box !important;overflow-wrap: break-word !important;">in</span> bins follows a Poisson distribution<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> (http://en.wikipedia.org/wiki/Poisson_distribution) with a<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> parameter of about 0.5 on average <span style="max-width: 100%;color: rgb(198, 120, 221);line-height: 26px;box-sizing: border-box !important;overflow-wrap: break-word !important;">for</span> the default resizing<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> threshold of 0.75, although with a large variance because of<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> resizing granularity. Ignoring variance, the expected<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> occurrences of list size k are (exp(-0.5) pow(0.5, k) /<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> factorial(k)). The first values are:<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> 0: 0.60653066<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> 1: 0.30326533<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> 2: 0.07581633<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> 3: 0.01263606<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> 4: 0.00157952<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> 5: 0.00015795<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> 6: 0.00001316<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> 7: 0.00000094<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;"> 8: 0.00000006<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">* more: less than 1 <span style="max-width: 100%;color: rgb(198, 120, 221);line-height: 26px;box-sizing: border-box !important;overflow-wrap: break-word !important;">in</span> ten million</code></pre><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">在理想情况下,使用随机哈希码,在扩容阈值(加载因子)为0.75的情况下,节点出现在频率在Hash桶(表)中遵循参数平均为0.5的泊松分布。忽略方差,即X = λt,P(λt = k),其中λt = 0.5的情况,按公式:</p><p style="max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;font-size: 16px;white-space: normal;background-color: rgb(255, 255, 255);text-align: center;box-sizing: border-box !important;overflow-wrap: break-word !important;"><img class="rich_pages img_loading" data-ratio="0.1475" data-s="300,640" data-type="png" data-w="800" data-src="https://mmbiz.qpic.cn/sz_mmbiz_png/HV4yTI6PjbI5XfTsYBP2JzOrpVfb0qhutqjXeosicTicS7wqlBJl32Y34NxuHdoCicQPUwXbCgk3qboC9MYBF6RvA/640?wx_fmt=png" style="box-sizing: border-box !important; overflow-wrap: break-word !important; visibility: visible !important; width: 533.25px !important; height: 80.3594px !important;" _width="533.25px" src="https://upload-images.jianshu.io/upload_images/22802755-4b7afe0eaa53fdab.png" crossorigin="anonymous" alt="图片"></p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">计算结果如上述的列表所示,当一个bin中的链表长度达到8个元素的时候,概率为0.00000006,几乎是一个不可能事件。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">所以我们可以知道,其实常数0.5是作为参数代入泊松分布来计算的,而加载因子0.75是作为一个条件,当HashMap长度为length/size ≥ 0.75时就扩容,在这个条件下,冲突后的拉链长度和概率结果为:</p><pre data-tool="mdnice编辑器" style="margin-top: 10px;margin-bottom: 10px;max-width: 100%;color: rgb(0, 0, 0);font-size: 16px;text-align: left;background-color: rgb(255, 255, 255);box-sizing: border-box !important;overflow-wrap: break-word !important;"><code style="padding: 16px;max-width: 100%;overflow-x: auto;color: rgb(171, 178, 191);background: rgb(40, 44, 52);display: -webkit-box;font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;border-radius: 0px;font-size: 12px;box-sizing: border-box !important;overflow-wrap: break-word !important;">0: 0.60653066<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">1: 0.30326533<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">2: 0.07581633<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">3: 0.01263606<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">4: 0.00157952<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">5: 0.00015795<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">6: 0.00001316<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">7: 0.00000094<br style="max-width: 100%;box-sizing: border-box !important;overflow-wrap: break-word !important;">8: 0.00000006</code></pre><h3 data-tool="mdnice编辑器" style="margin-top: 30px;margin-bottom: 15px;font-weight: bold;font-size: 18px;max-width: 100%;font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);color: rgb(14, 136, 235);box-sizing: border-box !important;overflow-wrap: break-word !important;">那么为什么不可以是0.8或者0.6呢?</h3><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">HashMap中除了哈希算法之外,有两个参数影响了性能:初始容量和加载因子。初始容量是哈希表在创建时的容量,加载因子是哈希表在其容量自动扩容之前可以达到多满的一种度量。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">在维基百科来描述加载因子:</p><blockquote data-tool="mdnice编辑器" style="margin-top: 20px;margin-bottom: 20px;padding: 10px 10px 10px 20px;border-left-color: rgb(92, 157, 255);color: rgb(106, 115, 125);font-size: 0.9em;max-width: 100%;font-family: PingFangSC-Light;text-align: left;white-space: normal;overflow: auto;background: rgb(249, 249, 249);box-sizing: border-box !important;overflow-wrap: break-word !important;"><p style="padding-top: 3px;padding-bottom: 3px;max-width: 100%;min-height: 1em;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;line-height: 26px;color: rgb(153, 153, 153);box-sizing: border-box !important;overflow-wrap: break-word !important;">对于开放定址法,加载因子是特别重要因素,应严格限制在0.7-0.8以下。超过0.8,查表时的CPU缓存不命中(cache missing)按照指数曲线上升。因此,一些采用开放定址法的hash库,如Java的系统库限制了加载因子为0.75,超过此值将resize散列表。</p></blockquote><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少扩容rehash操作次数,所以,一般在使用HashMap时建议根据预估值设置初始容量,以便减少扩容操作。</p><p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;max-width: 100%;min-height: 1em;color: rgb(0, 0, 0);font-family: PingFangSC-Light;text-align: left;white-space: normal;background-color: rgb(255, 255, 255);line-height: 1.75;letter-spacing: 0.1em;font-size: 15px;word-spacing: 0.1em;box-sizing: border-box !important;overflow-wrap: break-word !important;">选择0.75作为默认的加载因子,完全是时间和空间成本上寻求的一种折衷选择。</p><p><span style="color: rgba(0, 0, 0, 0.498);font-family: -apple-system, BlinkMacSystemFont, "Helvetica Neue", "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei UI", "Microsoft YaHei", Arial, sans-serif;font-size: 11px;letter-spacing: 0.544px;background-color: rgb(255, 255, 255);">源于:8rr.co/8V9Q</span></p><p style="text-align: center;"><img class="rich_pages img_loading" data-ratio="0.4600484261501211" data-s="300,640" data-src="https://mmbiz.qpic.cn/mmbiz_png/k05w3WRD08Gxrkkv3vXbXuEMg6Tzf3V5bPvSqSkFibqDZZTYV2icULo4KTxGdPxYpMicBRoibUibbpmo46sGzvWgCCQ/640?wx_fmt=png" data-type="png" data-w="826" style="width: 677px !important; height: 312.533px !important;" _width="677px" src="https://upload-images.jianshu.io/upload_images/22802755-677da8da982f9c42.png" crossorigin="anonymous" alt="图片"></p>
华为面试官:为什么HashMap的加载因子是0.75?
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 有很多东西之前在学的时候没怎么注意,笔者也是在重温HashMap的时候发现有很多可以去细究的问题,最终是会回归于数...
- 为什么HashMap需要加载因子? HashMap的底层是哈希表,是存储键值对的结构类型,它需要通过一定的计算才可...