HashMap 源碼解析

2019-11-08 02:20:04

字體：大中小

來源：轉載

供稿：網友

變量和常量

// 默認的初始化容量，十進制數為 16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16// 極限容量，也就是說 table 數組再大也不能超過這個容量static final int MAXIMUM_CAPACITY = 1 << 30;// 默認的負載因子：0.75（關系到 HashMap 本身的性能）static final float DEFAULT_LOAD_FACTOR = 0.75f;// 一個空的 Entry 數組，在 table 數組沒有進行初始化擴容之前一直就是這個空數組static final Entry<?,?>[] EMPTY_TABLE = {};// HashMap 的存儲結構就是這個 table 數組，長度為 2 的 n 次方數;// 數組中存儲的元素是一個個 Entry 對象，而 Entry 對象又實現了鏈表結構;// 所以說 HashMap 的數據結構是數組 + 鏈表，具體請看【存儲結構】章節transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;// HashMap 存儲的元素多少transient int size;// 閥值，一般來說為實際容量 * 負載因子int threshold;// 實際的負載因子final float loadFactor;// 修改次數，用于快速失敗，具體請看（快速失?。┱鹿漷ransient int modCount;

構造方法

public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; threshold = initialCapacity; init();// 此方法是空的}public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);}public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);}public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); inflateTable(threshold); putAllForCreate(m);}

（1）. 前三個構造方法，無非就是設置一下初始化容量和負載因子，不多說；（2）. 而第四個構造方法：

設置初始化容量和負載因子；inflateTable(…) 初始化數組并擴充容量；將 map 對象塞進空的 HashMap 中。

inflateTable(…)

// 對 table 數組進行擴容PRivate void inflateTable(int toSize) { // Find a power of 2 >= toSize int capacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; initHashSeedAsNeeded(capacity);}private static int roundUpToPowerOf2(int number) { // assert number >= 0 : "number must be non-negative"; return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;}

（1）. 一直往前推，很容易得知傳進來的 toSize 參數就是初始化容量；（2）. roundUpToPowerOf2(toSize) 方法得到返回值是一個比 toSize 大的最小的 2 的 n 次方數 capacity，capacity 就是實際容量；

若 toSize 為 15，則 capacity 為 16；若 toSize 為 17，則 capacity 為 32。

因此可以看出：table 數組的長度一定是 2 的 n 次方數；

（3）. 計算得出，閥值 = 實際容量*負載因子（capacity*loadFactor）。（4）. new 出一個真實容量為 capacity 的 Entry 數組。

hash 函數

final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);}

首先我們要明確一點，hash 算法有什么目的，說簡單了就是為了快。

hash 算法是為了減少查找過程中的比較次數；查找的最理想情況就是一次找到，當然這種情況往往是通過犧牲存儲空間實現的，實際應用之中并不可取，但是可以看出 hash 算法在查找方面的高效性。

通常情況下，有 hash 函數的地方也能見到 indexFor 函數的身影。

static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1);}

h & (length -1) 得到這個元素應該存儲在數組的哪個索引處。

Q：h & (length -1) 得到值永遠在數組的索引值范圍內，不會出現數組下標越界的情況，為什么呢 ? A：因為數組的長度是 2 的 n 次方數，所以 length -1 位最大的 n 位二進制數，即所有位都是 1：

當 h > length -1 時，h 的高位忽略，得到的數最大也就是 length -1；當 h <= length -1 時，若有高位則忽略所有高位，得到的數也不可能超過 length -1。

Q：hash 函數并不是簡簡單單的求下哈希碼，而是在這個基礎上又做了多次位操作，這樣做有何目的呢 ? A：如果 hashCode 值都大于 length，而且這些 hashCode 的低位變化不大，就會出現很多沖突。舉個例子：

假設數組的初始化容量為 16（10000），則 length -1 位 15（1111）；有幾個對象的 hashCode 分別為 1 1001 0010、1 1101 0010、11 1011 0010，進行位與運算的結果是一致的（都為 0010），即發生了沖突；而對 hashCode 進行位操作得到 1 1000 1000、1 1100 1100、11 1000 1110，進行位與運算分別得到 1000、1100、1110，減少了沖突。

因此，發生沖突的原因是 16 限制了只能用低位來計算，高位直接被舍棄無法參與計算，所以需要進行位操作使高位對低位造成影響改變低位的值，從而變相地使高位也參與運算。

put 操作（包含 update）

先看一下單個元素的 put 操作：

public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key); 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.record access(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null;}

（1）. 如果數組為空，先對其進行初始化并擴容；（2）. 如果 key==null，使用 putForNullKey 操作（下面有代碼）：

遍歷 table[0] 位置的鏈表，若遇到 key==null 的節點，就替換 value；若遇不到，就將這個元素插入鏈表的鏈首。

由此可見，如果有key==null 的元素肯定存儲在table[0] 位置的鏈表中。

private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null;}

（3）. 如果 key不為 null，hash 之后進行定位得到數組下標 x，對 table[x] 遍歷所有進行比較，如果找得到就進行替換，找不到就插入鏈首。

再看下 putAll 操作：

public void putAll(Map<? extends K, ? extends V> m) { int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0) return; if (table == EMPTY_TABLE) { inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold)); } if (numKeysToBeAdded > threshold) { int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); if (targetCapacity > MAXIMUM_CAPACITY) targetCapacity = MAXIMUM_CAPACITY; int newCapacity = table.length; while (newCapacity < targetCapacity) newCapacity <<= 1; if (newCapacity > table.length) resize(newCapacity); } for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) put(e.getKey(), e.getValue());}

（1）. 若 map 長度為0，到此為止；（2）. 若 table 為空，進行數組初始化并擴容；（3）. 若 map 的元素個數大于閥值，進行擴容，擴充后的容量和目標容量進行比較，若還是如此繼續擴容，直到容量滿足條件為止（條件就是數組容量不小于目標容量），擴容為向左移一位變為兩倍。（4）. 剩下的就是遍歷 map 一個一個元素 put，不多說。

resize 擴容

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, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}/** * Transfers all entries from current table to newTable. */void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } }}

resize 會改變 HashMap 的存儲結構，對元素進行重新映射，是非常耗性能的操作。所以最好一開始就能確定新容量的取值（這一點在 putAll 中有很好的體現）

Q：HashMap 使用數組 + 鏈表的存儲結構，理論上可以無限存儲數據，為什么要對數組進行擴容呢？ A：進行擴容能夠優化存儲結構，提高 HashMap 的性能；如果不進行擴容，鏈表長度就會慢慢變得很長，查找的時候很大概率遍歷到鏈表深處，就失去的 hash 查找的優勢。

HashMap.Entry

先上代碼。

static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; /** * 構造方法，創建一個 Entry 節點 */ Entry(int h, K k, V v, Entry<K,V> n) { // key，value，next 指針，hash 碼 value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } // 設置新的 value，返回舊的 value public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } // 判斷兩個節點是否相等 public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public final int hashCode() { return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); } public final String toString() { return getKey() + "=" + getValue(); } /** * This method is invoked whenever the value in an entry is * overwritten by an invocation of put(k,v) for a key k that's already * in the HashMap. */ void recordAccess(HashMap<K,V> m) { } /** * This method is invoked whenever the entry is * removed from the table. */ void recordRemoval(HashMap<K,V> m) { }}

Entry 實現了單向鏈表的功能。

所以，HashMap 的數據結構就是數組 + 鏈表：元素本身是存儲在 Entry 中的，這些 Entry 構成許多條鏈表，而所有鏈表的鏈首構成了 table 數組。數組的下標就是 indexFor 計算出的索引，但是不同元素會出現計算出索引相同的情況，這就是沖突了，解決這個沖突的辦法是具有相同索引的元素會以單向鏈表的方式存在。

下圖為 Hashmap 的存儲結構：

這里寫圖片描述

找到一個網站有助于理解 HashMap 的結構以及增刪改查操作：

https://www.cs.usfca.edu/~galles/visualization/OpenHash.html

get 操作

public V get(Object key) { // 若key == null，就會調 getForNullKey()，得到并且返回 value，否則返回 null。 // 若key != null，就會尋找該 Entry，得到并且返回 value，否則返回 null。 if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue();}// 1. 數組長度為0，找不到，返回 null。// 2. 遍歷數組和鏈表尋找，找到返回 value，否則返回 null。private V getForNullKey() { if (size == 0) { return null; } for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null;}// 根據 key 值尋找 Entry// 1. 數組長度為0，找不到，返回 null。// 2. 根據 key 值獲得 hash 碼，再根據 hash 碼得到應該存儲在數組的哪個位置。// 3. 在數組的該位置從鏈首開始遍歷尋找，找到返回 value，否則就返回 null。final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } int hash = (key == null) ? 0 : hash(key); 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 != null && key.equals(k)))) return e; } return null;}

remove 操作

public V remove(Object key) { Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.value);}// 如果元素個數為0，直接返回 null// 元素個數不為0，根據 key 獲得 hash碼，根據 hash 碼定位數組下標。// 得到數組在該位置的 Entry，遍歷如果找到這個 key，就刪除并且返回該元素，找不到就返回 null。final Entry<K,V> removeEntryForKey(Object key) { if (size == 0) { return null; } int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; while (e != null) { Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e;}

快速失敗

與 ArrayList 等集合的快速失敗原理一樣。

先舉個例子：

public class Test { HashMap<Integer, Integer> map = new HashMap<>(); public static void main(String[] args) { Test test = new Test(); test.putAndPrint(); test.remove_1(); } public void remove_2() { try { // 暫停10秒。目的是保證迭代器正在迭代過程中。 Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); } Iterator<Integer> iterator = map.keySet().iterator(); iterator.remove(); } public void remove_1() { try { // 暫停10秒。目的是保證迭代器正在迭代過程中。 Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); } map.remove(1000); } public void putAndPrint() { T1 t1 = new T1(); Thread thread = new Thread(t1); thread.start(); } class T1 implements Runnable { @Override public void run() { for (int i = 0; i < 1000000; i++) { map.put(i, i); } Iterator<Integer> iterator = map.keySet().iterator(); for (;iterator.hasNext();) { try { Thread.sleep(100); } catch (InterruptedException e) { e.printStackTrace(); } Integer integer = (Integer) iterator.next(); System.out.println(integer); } } }}

輸出為：

這里寫圖片描述

我們可以分析一下，另起了一個線程向 map 中 put 1000000個元素（這個時間可以忽略），生成迭代器，每隔大約 0.1 秒輸出一個元素。同時，主線程在 sleep 一秒鐘后對 map 進行了 remove 操作，此時迭代器正在迭代過程中。 map.remove 中有操作 modCount++，因此迭代器在 nextEntry 方法中發現 modCount != expectedModCount 為 false 拋出異常。

同理若把 main 方法中的test.remove_11()，改為test.remove_2()，也會拋出這個異常，因為 HashIterator 的 remove 方法同樣調的 map 的 remove 方法。