3分鐘輕鬆理解單執行緒下的HashMap工作原理

語言: CN / TW / HK

HashMap主要是用來處理鍵值對資料。隨著JDK版本的更新,JDK1.8對HashMap對底層也做了一些優化。今天我帶大家一起來結合原始碼,深入淺出HashMap工作原理。   l

HashMap是基於雜湊表對Map介面的實現類,它的特點是訪問資料的速度快,並不是按順序來遍歷。 HashMap提供所有可選的對映操作,但不能保證對映順序不變,並且允許使用空值和空鍵。HashMap也並不是執行緒安全的,當存在多個執行緒同時寫入時,可能會導致資料不一致的情況。

1、HashMap中的關鍵屬性

要透徹理解HashMap原理,首先需要對以下幾個關鍵屬性有一個基本的認識。

我們看到,HashMap的原始碼片段:

第一個屬性  loadFactor,它是負載因子,預設值是0.75,表示擴容前 。

第二個屬性  threshold 它是記錄HashMap所能容納的鍵值對的臨界值,它的計算規則是負載因子  乘以 陣列長度。

第三個屬性 size,它用來記錄HashMap實際存在的鍵值對的數量。

第四個屬性 modCount,它用來記錄HashMap內部結構發生變化的次數。

第五個是常量屬性DEFAULT_INITIAL_CAPACITY ,它規定 的預設容量是16。

2、HashMap的儲存結構

HashMap採用的是 的儲存結構。HashMap的陣列部分稱為Hash桶,陣列元素儲存在一個叫做table的屬性中。當連結串列長度大於等於8時,連結串列資料將會以紅黑樹的形式進行儲存,當長度降到6時,又會轉成連結串列形式儲存。

每個Node節點,儲存了用來定位陣列索引位置的hash值、Key、Value和連結串列指向的下一個Node節點。而Node類是HashMap的內部類,它實現了Map.Entry介面,它的本質其實可以簡單的理解成就是一個鍵值對。來看一下原始碼。

3、HashMap的工作原理

當我們向HashMap中插入資料時,首先要確定Node在陣列中的位置。那如何確定Node的儲存位置呢?以新增Key為字串“e”的物件為例:

HashMap首先呼叫hashCode()方法,獲取Key的hashCode值為h。然後對h值進行高位運算;將h右移16位取得h的高16位,與 進行異或運算,最後得到h的值與 ( table.length - 1 )進行與運算獲得該物件的保留位,最後計算出下標。當然,這是最官方的描述。有的小夥伴可能已經迷糊了。其實,這段運算過程,簡單地理解成求模取餘法。

就是用hash值和陣列的長度減1,取模,最後得到陣列的下標,這樣可以保證陣列下標不越界。只不過,位運算是二進位制運算,效率更高。

最後,來看一段動畫演示,假設有“a”、“b”、“d”、“r”,“t”,“e”的Key。通過計算得到的下標分別為  1  、2  、 4 、2  、4  、5\

它們的插入順序如動畫所示。

如果我們再次插入 "a",“g”,“i”,null 四個Key,來看HashMap的內部變化。

當插入第二個以a為Key的物件時,會將新值賦值給a的值。當插入的物件大小超過臨界值時,HashMap將新建一個桶陣列並重新賦值(當然,JDK1.7和1.8重新賦值的方式略有不同)

這個時候,HashMap鍵的輸出順序為 null、a、b、r、d、t、e、g、i

HashMap的工作原理,你搞懂了嗎?

需要1v1單獨模擬面試,以及需要做職業規劃的同學可S我【666】或【Tom】還有10萬+字面試文件已經整理成PDF可免費領取! 我是被程式設計耽誤的文藝Tom,