华为面试官：为什么HashMap的加载因子是0.75？

<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=”华为面试官：为什么HashMap的加载因子是0.75？”> 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” alt=”华为面试官：为什么HashMap的加载因子是0.75？”>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” alt=”华为面试官：为什么HashMap的加载因子是0.75？”>