Java面試必問之Hashmap底層實現原理(JDK1.7)
- 2020 年 3 月 5 日
- 筆記
1. 前言
Hashmap可以說是Java面試必問的，一般的面試題會問:
- Hashmap有哪些特性？
- Hashmap底層實現原理(getputresize)
- Hashmap怎麼解決hash衝突？
- Hashmap是執行緒安全的嗎？
- …
今天就從源碼角度一探究竟。筆者的源碼是OpenJDK1.7
2. 構造方法
首先看構造方法的源碼
// 默認初始容量 static final int DEFAULT_INITIAL_CAPACITY = 16; // 默認負載因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 數組, 該數據不參與序列化 transient Entry[] table; public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // 初始容量16，擴容因子0.75，擴容臨界值12 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); // 基礎結構為Entry數組 table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }由以上源碼可知，Hashmap的初始容量默認是16, 底層存儲結構是數組(到這裡只能看出是數組, 其實還有鏈表，下邊看源碼解釋)。基本存儲單元是Entry，那Entry是什麼呢?我們接著看Entry相關源碼，
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; // 鏈表後置節點 final int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; // 頭插法: newEntry.next=e key = k; hash = h; } ... }由Entry源碼可知，Entry是鏈表結構。綜上所述，可以得出:
Hashmap底層是基於數組和鏈表實現的
3. Hashmap中put()過程
我已經將put過程繪製了流程圖幫助大家理解
先上put源碼
public V put(K key, V value) { if (key == null) return putForNullKey(value); // 根據key計算hash int hash = hash(key.hashCode()); // 計算元素在數組中的位置 int i = indexFor(hash, table.length); // 遍歷鏈表，如果相同覆蓋 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; // 頭插法插入元素 addEntry(hash, key, value, i); return null; }上圖中多次提到頭插法，啥是 頭插法 呢？接下來看 addEntry 方法
void addEntry(int hash, K key, V value, int bucketIndex) { // 取出原bucket鏈表 Entry<K,V> e = table[bucketIndex]; // 頭插法 table[bucketIndex] = new Entry<>(hash, key, value, e); // 判斷是否需要擴容 if (size++ >= threshold) // 擴容好容量為原來的2倍 resize(2 * table.length); }結合Entry類的構造方法，每次插入新元素的時候，將bucket原鏈表取出，新元素的next指向原鏈表,這就是 頭插法 。為了更加清晰的表示Hashmap存儲結構，再繪製一張存儲結構圖。
4. Hashmap中get()過程
get()邏輯相對比較簡單，如圖所示
我們來對應下get()源碼
public V get(Object key) { // 獲取key為null的值 if (key == null) return getForNullKey(); // 根據key獲取hash int hash = hash(key.hashCode()); // 遍歷鏈表，直到找到元素 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }5. Hashmap中resize()過程
只要是新插入元素，即執行addEntry()方法，在插入完成後，都會判斷是否需要擴容。從addEntry()方法可知，擴容後的容量為原來的2倍。
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // 新建數組 Entry[] newTable = new Entry[newCapacity]; // 數據遷移 transfer(newTable); // table指向新的數組 table = newTable; // 新的擴容臨界值 threshold = (int)(newCapacity * loadFactor); }這裡有個transfer()方法沒講，別著急，擴容時執行緒安全的問題出現在這個方法中，接下來講解數組複製過程。
6. Hashmap擴容安全問題
大家都知道結果: 多執行緒擴容有可能會形成環形鏈表，這裡用圖給大家模擬下擴容過程。
首先看下單執行緒擴容的頭插法
然後看下多執行緒可能會出現的問題
以下是源碼，你仔細品一品
void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { // 釋放舊Entry數組的對象引用 src[j] = null; do { Entry<K,V> next = e.next; // 重新根據新的數組長度計算位置(同一個bucket上元素hash相等，所以擴容後必然還在一個鏈表上) int i = indexFor(e.hash, newCapacity); // 頭插法(同一位置上新元素總會被放在鏈表的頭部位置),將newTable[i]的引用賦給了e.next e.next = newTable[i]; // 將元素放在數組上 newTable[i] = e; // 訪問下一個元素 e = next; } while (e != null); } } }7. Hashmap尋找bucket位置
static int indexFor(int h, int length) { // 根據hash與數組長度mod運算 return h & (length-1); }由源碼可知, jdk根據key的hash值和數組長度做mod運算，這裡用位運算代替mod。
hash運算值是一個int整形值，在java中int佔4個位元組，32位，下邊通過圖示來說明位運算。
8. AD
如果您覺得還行，請關注公眾號【當我遇上你】, 您的支援是我輸出的最大動力。
同時，歡迎大家一起交流學習。
