為什么HashMap的負載因子是0.75

網(wǎng)上亂七八糟的答案太多了，這里從直觀感受和數(shù)學方法上對這塊知識做了個整理安寺，數(shù)學方法基于stackoverflow上的答案弄慰，補充了些推導(dǎo)細節(jié)方便理解第美。（內(nèi)容比較精簡，后續(xù)有時間整理下放到個人博客下）

HashMap是用來快速查找內(nèi)容的一種數(shù)據(jù)結(jié)構(gòu)陆爽。使用n個桶存儲數(shù)據(jù)什往，數(shù)據(jù)具體存儲在哪個桶中是由Hash算法決定的，即對原始內(nèi)容執(zhí)行Hash后得出對應(yīng)桶的序號慌闭。

然后這種數(shù)據(jù)結(jié)構(gòu)會遇到一些問題别威，由于內(nèi)存空間有限，所以桶的數(shù)量也是有限制的驴剔。當桶的數(shù)量較小時就容易出現(xiàn)較多內(nèi)容放在同一個桶中的情況省古。HashMap中使用默認的0.75作為桶空間的閾值，如果超過這個大小就需要增加桶的數(shù)量丧失，以防止較多內(nèi)容聚集在相同的桶中豺妓。

關(guān)于為什么0.75就是經(jīng)常被拿來當做面試問題了。首先通過人腦直觀來考慮這個事情布讹，假設(shè)我現(xiàn)在有n個桶琳拭，那么數(shù)據(jù)放到多少我需要增加更多的桶呢。這個時候會出現(xiàn)直觀的數(shù)字0.5炒事，如果桶已經(jīng)裝滿一半了那么之后添加內(nèi)容分配到空桶的概率會低于分配到有內(nèi)容桶的概率臀栈，可想而知從這個點之后將會出現(xiàn)越來越多的內(nèi)容在相同的桶中。從這里來看這個0.5是個非常優(yōu)秀的數(shù)字它是一個趨勢的轉(zhuǎn)折點挠乳。

但是這個0.5和負載因子是不一樣的权薯，這個0.5我們是指已經(jīng)有一半的桶被占用了，而HashMap中的負載因子與我們存入的數(shù)據(jù)總數(shù)量相關(guān)睡扬，并且根據(jù)之前對這種數(shù)據(jù)結(jié)構(gòu)的了解盟蚣，數(shù)據(jù)會存在一定概率出現(xiàn)在一個桶中，所以當一半桶都被占用的時候我們實際存儲的數(shù)據(jù)數(shù)量是大于0.5n的卖怜。

這里假設(shè)對于新的內(nèi)容分配到各個桶的概率是相同的屎开，當前內(nèi)容數(shù)據(jù)大小為s。這里使用二項分布的概念马靠，當我們進行了s次插入操作（實驗）奄抽，那么序號0的桶是空桶的概率是多少呢。即：

$P(0) = \tbinom{s}{0}(\frac{1}{n})^0(1-\frac{1}{n})^s$