為什么java Hashmap 中的加載因子是默認(rèn)為0.75

前幾天在一個(gè)群里看到有人討論hashmap中的加載因子為什么是默認(rèn)0.75。

HashMap源碼中的加載因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

當(dāng)時(shí)想到的是應(yīng)該是“哈希沖突”和“空間利用率”矛盾的一個(gè)折衷。
跟數(shù)據(jù)結(jié)構(gòu)要么查詢快要么插入快一個(gè)道理，hashmap就是一個(gè)插入慢、查詢快的數(shù)據(jù)結(jié)構(gòu)。

加載因子是表示Hsah表中元素的填滿的程度。
加載因子越大,填滿的元素越多,空間利用率越高，但沖突的機(jī)會加大了。
反之,加載因子越小,填滿的元素越少,沖突的機(jī)會減小,但空間浪費(fèi)多了。

沖突的機(jī)會越大,則查找的成本越高。反之,查找的成本越小。

因此,必須在 "沖突的機(jī)會"與"空間利用率"之間尋找一種平衡與折衷。

但是為什么一定是0.75？而不是0.8，0.6###

本著不嫌事大的精神繼續(xù)深挖，在此之前先簡單補(bǔ)充點(diǎn)本文需要的基礎(chǔ)知識：

1.沖突定義：假設(shè)哈希表的地址集為［0，ｎ），沖突是指由關(guān)鍵字得到的哈希地址為j（0<=j<=n-1）的位置上已經(jīng)有記錄。在關(guān)鍵字得到的哈希地址上已經(jīng)有記錄，那么就稱之為沖突

2.處理沖突：就是為該關(guān)鍵字的記錄扎到另一個(gè)“空”的哈希地址。即在處理哈希地址的沖突時(shí)，若得到的另一個(gè)哈希地址H1仍然發(fā)生沖突，則再求下一個(gè)地址H2，若H2仍然沖突，再求的H3，直至Hk不發(fā)生沖突為止，則Hk為記錄在表中的地址。

處理沖突的幾種方法：#

一、 開放定址法

Hi=(H(key) + di) MOD m i=1,2,...k(k<=m-1)其中H(key)為哈希函數(shù)；m為哈希表表長；di為增量序列。

開放定址法根據(jù)步長不同可以分為３種：

1）線性探查法(Linear Probing)：di=1,2,3,...,m-1
　 簡單地說就是以當(dāng)前沖突位置為起點(diǎn)，步長為１循環(huán)查找，直到找到一個(gè)空的位置就把元素插進(jìn)去，循環(huán)完了都找不到說明容器滿了。就像你去一條街上的店里吃飯，問了第一家被告知滿座，然后挨著一家家去問是否有位置一樣。

2）線性補(bǔ)償探測法：di=Ｑ　下一個(gè)位置滿足 Hi=(H(key) + Ｑ) mod m i=1,2,...k(k<=m-1) ，要求 Q 與 m 是互質(zhì)的，以便能探測到哈希表中的所有單元。
繼續(xù)用上面的例子，現(xiàn)在你不是挨著一家家去問了，拿出計(jì)算器算了一下，然后隔Ｑ家問一次有沒有位置。

3）偽隨機(jī)探測再散列：di=偽隨機(jī)數(shù)序列。還是那個(gè)例子，這是完全根據(jù)心情去選一家店來問了

缺點(diǎn)：

  • 這種方法建立起來的hash表當(dāng)沖突多的時(shí)候數(shù)據(jù)容易堆聚在一起，這時(shí)候?qū)Σ檎也挥押茫?/li>
  • 刪除結(jié)點(diǎn)不能簡單地將被刪結(jié) 點(diǎn)的空間置為空，否則將截?cái)嘣谒筇钊松⒘斜淼耐x詞結(jié)點(diǎn)的查找路徑。因此在 用開放地址法處理沖突的散列表上執(zhí)行刪除操作，只能在被刪結(jié)點(diǎn)上做刪除標(biāo)記，而不能真正刪除結(jié)點(diǎn)
  • 當(dāng)空間滿了，還要建立一個(gè)溢出表來存多出來的元素。

二、再哈希法

Hi = RHi（key），i=1,2,...k
RHi均是不同的哈希函數(shù)，即在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)地址，直到不發(fā)生沖突為止。這種方法不易產(chǎn)生聚集，但是增加了計(jì)算時(shí)間。

缺點(diǎn)：增加了計(jì)算時(shí)間。

三、建立一個(gè)公共溢出區(qū)

假設(shè)哈希函數(shù)的值域?yàn)閇0,m-1]，則設(shè)向量HashTable[0...m-1]為基本表，每個(gè)分量存放一個(gè)記錄，另設(shè)立向量OverTable[0....v]為溢出表。所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管他們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。

簡單地說就是搞個(gè)新表存沖突的元素。

四、鏈地址法（拉鏈法）

將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中，也就是把沖突位置的元素構(gòu)造成鏈表。

拉鏈法的優(yōu)點(diǎn):

  • 拉鏈法處理沖突簡單，且無堆積現(xiàn)象，即非同義詞決不會發(fā)生沖突，因此平均查找長度較短；
  • 由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動態(tài)申請的，故它更適合于造表前無法確定表長的情況；
  • 在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)。只要簡單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可。

拉鏈法的缺點(diǎn)：

  • 指針需要額外的空間，故當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)，開放定址法較為節(jié)省空間，而若將節(jié)省的指針空間用來擴(kuò)大散列表的規(guī)模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度

Java中HashMap的數(shù)據(jù)結(jié)構(gòu)#

HashMap實(shí)際上是一個(gè)“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體。

HashMap數(shù)據(jù)結(jié)構(gòu)，來源于網(wǎng)絡(luò)

看圖就可以知道Java中的hashMap使用了拉鏈法處理沖突。
HashMap有一個(gè)初始容量大小，默認(rèn)是16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

為了減少沖突的概率，當(dāng)hashMap的數(shù)組長度到了一個(gè)臨界值就會觸發(fā)擴(kuò)容，把所有元素rehash再放到擴(kuò)容后的容器中，這是一個(gè)非常耗時(shí)的操作。

而這個(gè)臨界值由【加載因子】和當(dāng)前容器的容量大小來確定：DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR ，即默認(rèn)情況下是16x0.75=12時(shí)，就會觸發(fā)擴(kuò)容操作。

所以使用hash容器時(shí)盡量預(yù)估自己的數(shù)據(jù)量來設(shè)置初始值。具體代碼實(shí)現(xiàn)自行去研究HashMap的源碼。

基礎(chǔ)知識補(bǔ)充完畢，回到正題，為什么加載因子要默認(rèn)是0.75？
從hashmap源碼注釋里找到了這一段

Ideally, under random hashCodes, the frequency of

  • nodes in bins follows a Poisson distribution
  • (http://en.wikipedia.org/wiki/Poisson_distribution) with a
  • parameter of about 0.5 on average for the default resizing
  • threshold of 0.75, although with a large variance because of
  • resizing granularity. Ignoring variance, the expected
  • occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
  • factorial(k)). The first values are:
  • 0: 0.60653066
  • 1: 0.30326533
  • 2: 0.07581633
  • 3: 0.01263606
  • 4: 0.00157952
  • 5: 0.00015795
  • 6: 0.00001316
  • 7: 0.00000094
  • 8: 0.00000006
  • more: less than 1 in ten million

注意wiki鏈接中的關(guān)鍵字：Poisson_distribution
泊淞分布啊

簡單翻譯一下就是在理想情況下,使用隨機(jī)哈希碼,節(jié)點(diǎn)出現(xiàn)的頻率在hash桶中遵循泊松分布，同時(shí)給出了桶中元素個(gè)數(shù)和概率的對照表。

從上面的表中可以看到當(dāng)桶中元素到達(dá)8個(gè)的時(shí)候，概率已經(jīng)變得非常小，也就是說用0.75作為加載因子，每個(gè)碰撞位置的鏈表長度超過８個(gè)是幾乎不可能的。

好了，再深挖就要挖到統(tǒng)計(jì)學(xué)那邊去了，就此打住，重申一下使用hash容器請盡量指定初始容量，且是2的冪次方。

關(guān)于泊淞分布的知識請看

http://www.ruanyifeng.com/blog/2015/06/poisson-distribution.html#comment-356111

歡迎討論，這個(gè)周末的任務(wù)完成了，可以放心去浪了─=≡Σ((( つ??ω??)つ超人

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • HashMap 是 Java 面試必考的知識點(diǎn)，面試官從這個(gè)小知識點(diǎn)就可以了解我們對 Java 基礎(chǔ)的掌握程度。網(wǎng)...
    野狗子嗷嗷嗷閱讀 6,806評論 9贊 107
  • Java8張圖 11、字符串不變性 12、equals()方法、hashCode()方法的區(qū)別 13、...
    Miley_MOJIE閱讀 3,895評論 0贊 11
  • 前言 這次我和大家一起學(xué)習(xí)HashMap，HashMap我們在工作中經(jīng)常會使用，而且面試中也很頻繁會問到，因?yàn)樗?..
    liangzzz閱讀 8,113評論 7贊 102
  • 一、基本數(shù)據(jù)類型 注釋 單行注釋：// 區(qū)域注釋：/* */ 文檔注釋：/** */ 數(shù)值 對于byte類型而言...
    龍貓小爺閱讀 4,442評論 0贊 16
  • 小時(shí)候，因?yàn)榧依锔F，也比較重男輕女。我便早早地學(xué)會了懂事，每次與弟弟發(fā)生沖突，母親總會教訓(xùn)道：你是姐姐，年齡比弟弟...
    風(fēng)花星月閱讀 711評論 3贊 10

友情鏈接更多精彩內(nèi)容