HashMap剖析之內部結構
前言
本文是基於 Java 8
的 HashMap
進行分析,主要是介紹 HashMap
中的成員變數和類變數的用途,以及分析 HashMap
的資料結構。
變數分析
在 HashMap
中存在多個成員變數和類變數,搞清楚它們的用途有助於我們更深入瞭解 HashMap
,下面是它們的介紹:
/** * 預設的初始容量,必須為2的次冪 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 總所周知是16 /** * 最大容量 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 預設的負載因子 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 將連結串列轉化為紅黑樹的閾值,當連結串列節點數大於或等於該閾值-1則轉化為紅黑樹 */ static final int TREEIFY_THRESHOLD = 8; /** * 將紅黑樹轉化為連結串列的閾值,當紅黑樹的節點小於該閾值時轉化為連結串列 */ static final int UNTREEIFY_THRESHOLD = 6; /** * 允許進行連結串列轉化為紅黑樹的閾值,只有散列表大小大於或等於該值才能進行紅黑樹轉化 */ static final int MIN_TREEIFY_CAPACITY = 64; /** * HashMap中儲存資料的陣列,也稱為散列表。 * 建議保持長度為2的次冪 */ transient Node<K,V>[] table; /** * 快取entrySet()方法的值 */ transient Set<Map.Entry<K,V>> entrySet; /** * Map中鍵值對的個數 */ transient int size; /** * HashMap資料結構被改變的次數,一般是指散列表的長度改變、Node連結串列增加或者減少節點 * 這個引數是用於快速失敗機制 */ transient int modCount; /** * 下一次觸發調整大小(resize()方法)的閾值,一般為容量乘以負載因子 */ int threshold; /** * 散列表的負載因子,用於計算擴容的閾值 */ final float loadFactor;
資料結構
HashMap
使用 拉鍊法 解決雜湊表中存在的 雜湊衝突 問題,所以 HashMap
底層是用以 Node
組成的 連結串列 為元素的 陣列 table
來儲存鍵值對,每個 Node
就是一個鍵值對物件。 table
稱呼為散列表。
而 table
對應的是 散列表 ,是因為無論是儲存還是讀取鍵值對的時候,都會對 key
進行 hash%table.length
運算來進行散列表的命中,然後操作命中的索引對應的 Node
連結串列(還是會比較 key
和 hash
)。
以上為 Java 8
之前版本的 HashMap
的實現,而 Java 8
進行了優化:就是當連結串列節點數超過閾值 TREEIFY_THRESHOLD(8)
時,則會將 連結串列 轉化為 紅黑樹 。
如果只是使用文字描述的話會很難理解,所以下面會通過一幅圖展示: