HashMap 的資料結構
目錄
content
HashMap 的資料結構:
PS:這裡的《紅黑樹》與連結串列都是鏈式結構。
HashMap 內部維護了一個數組,陣列中存放連結串列的鏈首或紅黑樹的樹根。
當連結串列長度超過 8 時,連結串列就轉換為紅黑樹,利用紅黑樹快速增刪改查的特點提高 HashMap 的效能;在紅黑樹結點數量小於 6 時,紅黑樹轉變為連結串列。
下面分別為上面兩種資料結構的圖示:
【定位演算法】
增加、查詢、刪除等操作都需要先定位到 table 陣列的某個索引處。
定位演算法為三步:取 key 的 hashCode 值、高位運算、取模運算得到索引位置。(程式碼如下)
static final int hash(Object key) { int h; // h = key.hashCode() 第一步 取 hashCode 值 // h ^ (h >>> 16)第二步 高位參與運算 Java8 優化了高位演算法,優化原理忽略 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } // java7 中這是一個單獨的方法,java8 沒有了這個方法但是原理依舊 static int indexFor(int h, int length) { return h & (length-1); // hash(key) & (length-1)第三步 取模 }
取模運算 h & (length -1)
的結果最大值為 length -1,不會出現陣列下標越界的情況。
為什麼要做高位運算?
如果 hashCode 值都大於 length,而且這些 hashCode 的低位變化不大,就會出現很多衝突,舉個例子:
- 假設陣列的初始化容量為 16(10000),則 length -1 位 15(1111)。
- 假設有幾個物件的 hashCode 分別為 1100 10010、1110 10010、11101 10010,如果不做高位運算,直接使用它們做取模運算的結果將是一致的。
如果所有元素中多數元素屬於這種情況,將會導致元素分佈不均勻,而對 hashCode 進行高位運算能解決這個問題,使高位對低位造成影響改變低位的值,從而變相地使高位也參與運算。
append
【Q】負載因子與效能的關係
負載因子預設值為 0.75
,意味著當陣列實際填充量佔比達到 3/4
時就該擴容了。
負載因子越大,擴容次數必然越少,陣列的長度越小,減少了空間開銷;這就會導致 hash 碰撞越多,增加查詢成本。
預設值 0.75
在時間和空間成本上尋求一種折衷。
【Q】為什麼要擴容
因為隨著元素量的增大,hash 碰撞的概率越來越大,雖然使用鏈地址法能夠解決儲存問題,但是長長的連結串列會讓 HashMap 失去快速檢索的優勢,而擴容能解決這個問題。