1 HashMap在JAVA中的怎么工作的？

基于Hash的原理

2 什么是哈希？

最簡單形式的 hash，是一種在對任何變量/對象的屬性應用任何公式/算法后， 為其分配唯一代碼的方法。

一個真正的hash方法必須遵循下面的原則

哈希函數每次在相同或相等的對象上應用哈希函數時, 應每次返回相同的哈希碼。換句話說, 兩個相等的對象必須一致地生成相同的哈希碼。

Java 中所有的對象都有 Hash 方法

Java中的所有對象都繼承?Object?類中定義的?hashCode()?函數的默認實現。 此函數通常通過將對象的內部地址轉換為整數來生成哈希碼，從而為所有不同的對象生成不同的哈希碼。

3 HashMap 中的 Node 類

Map的定義是： 將鍵映射到值的對象。

因此，HashMap?中必須有一些機制來存儲這個鍵值對。 答案是肯定的。 HHashMap?有一個內部類?Node，如下所示：

    static class Node<K,V> implements Map.Entry<K,V> {final int hash;// 記錄hash值， 以便重hash時不需要再重新計算final K key; V value;Node<K,V> next;...// 其余的代碼}

當然，Node?類具有存儲為屬性的鍵和值的映射。 key 已被標記為 final，另外還有兩個字段：next 和 hash。

在下面中， 我們將會理解這些屬性的必須性。

4 鍵值對在 HashMap 中是如何存儲的

鍵值對在?HashMap?中是以?Node?內部類的數組存放的， 如下所示：

transient Node<K,V>[] table;

哈希碼計算出來之后， 會轉換成該數組的下標， 在該下標中存儲對應哈希碼的鍵值對， 在此先不詳細講解hash碰撞的情況。

該數組的長度始終是 2 的次冪， 通過以下的函數實現該過程

static final int tableSizeFor(int cap) {int n = cap - 1;// 如果不做該操作， 則如傳入的 cap 是 2 的整數冪， 則返回值是預想的 2 倍n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

其原理是將傳入參數 (cap) 的低二進制全部變為 1， 最后加 1 即可獲得對應的大于 cap 的 2 的次冪作為數組長度。

為什么要使用 2 的次冪作為數組的容量呢？

在此有涉及到?HashMap?的 hash 函數及數組下標的計算， 鍵(key)所計算出來的哈希碼有可能是大于數組的容量的， 那怎么辦？ 可以通過簡單的求余運算來獲得， 但此方法效率太低。HashMap?中通過以下的方法保證 hash 的值計算后都小于數組的容量。

(n - 1) & hash

這也正好解釋了為什么需要 2 的次冪作為數組的容量。 由于 n 是 2 的次冪， 因此， n - 1 類似于一個低位掩碼。 通過與操作， 高位的hash值全部歸零，保證低位才有效， 從而保證獲得的值都小于 n。 同時， 在下一次 resize() 操作時， 重新計算每個 Node 的數組下標將會因此變得很簡單， 具體的后文講解。 以默認的初始值 16 為例

    01010011 00100101 01010100 00100101
&   00000000 00000000 00000000 00001111
----------------------------------00000000 00000000 00000000 00000101    //高位全部歸零，只保留末四位// 保證了計算出的值小于數組的長度 n

但是， 使用了該功能之后， 由于只取了低位， 因此 hash 碰撞會也會相應的變得很嚴重。 這時候就需要使用 「擾動函數」

    static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

該函數通過將哈希碼的高 16 位的右移后與原哈希碼進行異或而得到， 以以上的例子為例

此方法保證了高16位不變， 低16位根據異或后的結果改變。計算后的數組下標將會從原先的 5 變為 0。

使用了 「擾動函數」 之后， hash 碰撞的概率將會下降。 有人專門做過類似的測試， 雖然使用該 「擾動函數」 并沒有獲得最大概率的避免 hash 碰撞， 但考慮其計算性能和碰撞的概率， JDK 中使用了該方法， 且只 hash 一次。

5 哈希碰撞及其處理

在理想的情況下， 哈希函數將每一個 key 都映射到一個唯一的 bucket， 然而， 這是不可能的。 哪怕是設計在良好的哈希函數， 也會產生哈希沖突。

前人研究了很多哈希沖突的解決方法， 在維基百科中， 總結出了四大類

在 Java 的?HashMap?中， 采用了第一種 Separate chaining 方法(大多數翻譯為拉鏈法)+鏈表和紅黑樹來解決沖突。

在?HashMap?中， 哈希碰撞之后會通過?Node?類內部的成員變量?Node<K,V> next;?來形成一個鏈表(節點小于8)或紅黑樹（節點大于8， 在小于6時會從新轉換為鏈表）， 從而達到解決沖突的目的。

static final int TREEIFY_THRESHOLD = 8;static final int UNTREEIFY_THRESHOLD = 6;

6 HashMap 的初始化

 public HashMap();public HashMap(int initialCapacity);public HashMap(Map<? extends K, ? extends V> m);public HashMap(int initialCapacity, float loadFactor); 

HashMap?中有四個構造函數， 大多是初始化容量和負載因子的操作。以?public HashMap(int initialCapacity, float loadFactor)?為例

public HashMap(int initialCapacity, float loadFactor) {// 初始化的容量不能小于0if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);// 初始化容量不大于最大容量if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;// 負載因子不能小于 0if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);
}

通過該函數進行了容量和負載因子的初始化，如果是調用的其他的構造函數， 則相應的負載因子和容量會使用默認值（默認負載因子=0.75， 默認容量=16）。在此時， 還沒有進行存儲容器 table 的初始化， 該初始化要延遲到第一次使用時進行。

7 HashMap 中哈希表的初始化或動態擴容

所謂的哈希表， 指的就是下面這個類型為內部類Node的 table 變量。

transient Node<K,V>[] table;

作為數組， 其在初始化時就需要指定長度。在實際使用過程中， 我們存儲的數量可能會大于該長度，因此?HashMap?中定義了一個閾值參數(threshold)， 在存儲的容量達到指定的閾值時， 需要進行擴容。

我個人認為初始化也是動態擴容的一種， 只不過其擴容是容量從 0 擴展到構造函數中的數值（默認16）。 而且不需要進行元素的重hash.

7.1 擴容發生的條件

初始化的話只要數值為空或者數組長度為 0 就會進行。 而擴容是在元素的數量大于閾值（threshold）時就會觸發。

threshold = loadFactor * capacity

比如?HashMap?中默認的 loadFactor=0.75, capacity=16, 則

threshold = loadFactor * capacity = 0.75 * 16 = 12

那么在元素數量大于 12 時， 就會進行擴容。 擴容后的 capacity 和 threshold 也會隨之而改變。

負載因子影響觸發的閾值， 因此， 它的值較小的時候，?HashMap?中的 hash 碰撞就很少， 此時存取的性能都很高， 對應的缺點是需要較多的內存； 而它的值較大時，?HashMap?中的 hash 碰撞就很多， 此時存取的性能相對較低， 對應優點是需要較少的內存； 不建議更改該默認值， 如果要更改， 建議進行相應的測試之后確定。

7.2 再談容量為2的整數次冪和數組索引計算

前面說過了數組的容量為 2 的整次冪， 同時， 數組的下標通過下面的代碼進行計算

index = (table.length - 1) & hash

該方法除了可以很快的計算出數組的索引之外， 在擴容之后， 進行重 hash 時也會很巧妙的就可以算出新的 hash 值。 由于數組擴容之后， 容量是現在的 2 倍， 擴容之后 n-1 的有效位會比原來多一位， 而多的這一位與原容量二進制在同一個位置。 示例

這樣就可以很快的計算出新的索引啦

7.3 步驟

1. 先判斷是初始化還是擴容， 兩者在計算 newCap和newThr 時會不一樣
2. 計算擴容后的容量，臨界值。
3. 將hashMap的臨界值修改為擴容后的臨界值
4. 根據擴容后的容量新建數組，然后將hashMap的table的引用指向新數組。
5. 將舊數組的元素復制到table中。在該過程中， 涉及到幾種情況， 需要分開進行處理（只存有一個元素， 一般鏈表， 紅黑樹）

具體的看代碼吧

final Node<K, V>[] resize() {//新建oldTab數組保存擴容前的數組tableNode<K, V>[] oldTab = table;//獲取原來數組的長度int oldCap = (oldTab == null) ? 0 : oldTab.length;//原來數組擴容的臨界值int oldThr = threshold;int newCap, newThr = 0;//如果擴容前的容量 > 0if (oldCap > 0) {//如果原來的數組長度大于最大值(2^30)if (oldCap >= MAXIMUM_CAPACITY) {//擴容臨界值提高到正無窮threshold = Integer.MAX_VALUE;//無法進行擴容，返回原來的數組return oldTab;//如果現在容量的兩倍小于MAXIMUM_CAPACITY且現在的容量大于DEFAULT_INITIAL_CAPACITY} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)//臨界值變為原來的2倍newThr = oldThr << 1;} else if (oldThr > 0) //如果舊容量 <= 0，而且舊臨界值 > 0//數組的新容量設置為老數組擴容的臨界值newCap = oldThr;else { //如果舊容量 <= 0，且舊臨界值 <= 0，新容量擴充為默認初始化容量，新臨界值為DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITYnewCap = DEFAULT_INITIAL_CAPACITY;//新數組初始容量設置為默認值newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//計算默認容量下的閾值}// 計算新的resize上限if (newThr == 0) {//在當上面的條件判斷中，只有是初始化時(oldCap=0, oldThr > 0)時，newThr == 0//ft為臨時臨界值，下面會確定這個臨界值是否合法，如果合法，那就是真正的臨界值float ft = (float) newCap * loadFactor;//當新容量< MAXIMUM_CAPACITY且ft < (float)MAXIMUM_CAPACITY，新的臨界值為ft，否則為Integer.MAX_VALUEnewThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?(int) ft : Integer.MAX_VALUE);}//將擴容后hashMap的臨界值設置為newThrthreshold = newThr;//創建新的table，初始化容量為newCap@SuppressWarnings({"rawtypes", "unchecked"})Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];//修改hashMap的table為新建的newTabtable = newTab;//如果舊table不為空，將舊table中的元素復制到新的table中if (oldTab != null) {//遍歷舊哈希表的每個桶，將舊哈希表中的桶復制到新的哈希表中for (int j = 0; j < oldCap; ++j) {Node<K, V> e;//如果舊桶不為null，使用e記錄舊桶if ((e = oldTab[j]) != null) {//將舊桶置為nulloldTab[j] = null;//如果舊桶中只有一個nodeif (e.next == null)//將e也就是oldTab[j]放入newTab中e.hash & (newCap - 1)的位置newTab[e.hash & (newCap - 1)] = e;//如果舊桶中的結構為紅黑樹else if (e instanceof TreeNode)//將樹中的node分離((TreeNode<K, V>) e).split(this, newTab, j, oldCap);else {  //如果舊桶中的結構為鏈表,鏈表重排，jdk1.8做的一系列優化Node<K, V> loHead = null, loTail = null;Node<K, V> hiHead = null, hiTail = null;Node<K, V> next;//遍歷整個鏈表中的節點do {next = e.next;// 原索引if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;} else {// 原索引+oldCapif (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 原索引放到bucket里if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 原索引+oldCap放到bucket里if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

7.4 注意事項

雖然 HashMap 設計的非常優秀， 但是應該盡可能少的避免 resize(), 該過程會很耗費時間。

同時， 由于 hashmap 不能自動的縮小容量。 因此， 如果你的 hashmap 容量很大， 但執行了很多 remove 操作時， 容量并不會減少。 如果你覺得需要減少容量， 請重新創建一個 hashmap。

8 HashMap.put() 函數內部是如何工作的？

在使用多次?HashMap?之后， 大體也能說出其添加元素的原理：計算每一個key的哈希值， 通過一定的計算之后算出其在哈希表中的位置，將鍵值對放入該位置，如果有哈希碰撞則進行哈希碰撞處理。

而其工作時的原理如下（圖是我很早之前保存的， 忘了出處了）

源碼如下：

    /* @param hash         指定參數key的哈希值* @param key          指定參數key* @param value        指定參數value* @param onlyIfAbsent 如果為true，即使指定參數key在map中已經存在，也不會替換value* @param evict        如果為false，數組table在創建模式中* @return 如果value被替換，則返回舊的value，否則返回null。當然，可能key對應的value就是null。*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K, V>[] tab;Node<K, V> p;int n, i;//如果哈希表為空，調用resize()創建一個哈希表，并用變量n記錄哈希表長度if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;/*** 如果指定參數hash在表中沒有對應的桶，即為沒有碰撞* Hash函數，(n - 1) & hash 計算key將被放置的槽位* (n - 1) & hash 本質上是hash % n，位運算更快*/if ((p = tab[i = (n - 1) & hash]) == null)//直接將鍵值對插入到map中即可tab[i] = newNode(hash, key, value, null);else {// 桶中已經存在元素Node<K, V> e;K k;// 比較桶中第一個元素(數組中的結點)的hash值相等，key相等if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// 將第一個元素賦值給e，用e來記錄e = p;// 當前桶中無該鍵值對，且桶是紅黑樹結構，按照紅黑樹結構插入else if (p instanceof TreeNode)e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);// 當前桶中無該鍵值對，且桶是鏈表結構，按照鏈表結構插入到尾部else {for (int binCount = 0; ; ++binCount) {// 遍歷到鏈表尾部if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);// 檢查鏈表長度是否達到閾值，達到將該槽位節點組織形式轉為紅黑樹if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 鏈表節點的<key, value>與put操作<key, value>相同時，不做重復操作，跳出循環if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 找到或新建一個key和hashCode與插入元素相等的鍵值對，進行put操作if (e != null) { // existing mapping for key// 記錄e的valueV oldValue = e.value;/*** onlyIfAbsent為false或舊值為null時，允許替換舊值* 否則無需替換*/if (!onlyIfAbsent || oldValue == null)e.value = value;// 訪問后回調afterNodeAccess(e);// 返回舊值return oldValue;}}// 更新結構化修改信息++modCount;// 鍵值對數目超過閾值時，進行rehashif (++size > threshold)resize();// 插入后回調afterNodeInsertion(evict);return null;}

在此過程中， 會涉及到哈希碰撞的解決。

9 HashMap.get() 方法內部是如何工作的？

    /*** 返回指定的key映射的value，如果value為null，則返回null* get可以分為三個步驟：* 1.通過hash(Object key)方法計算key的哈希值hash。* 2.通過getNode( int hash, Object key)方法獲取node。* 3.如果node為null，返回null，否則返回node.value。** @see #put(Object, Object)*/public V get(Object key) {Node<K, V> e;//根據key及其hash值查詢node節點，如果存在，則返回該節點的value值return (e = getNode(hash(key), key)) == null ? null : e.value;
}

其最終是調用了?getNode?函數。 其邏輯如下

源碼如下：

    /*** @param hash 指定參數key的哈希值* @param key  指定參數key* @return 返回node，如果沒有則返回null*/final Node<K, V> getNode(int hash, Object key) {Node<K, V>[] tab;Node<K, V> first, e;int n;K k;//如果哈希表不為空，而且key對應的桶上不為空if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//如果桶中的第一個節點就和指定參數hash和key匹配上了if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))//返回桶中的第一個節點return first;//如果桶中的第一個節點沒有匹配上，而且有后續節點if ((e = first.next) != null) {//如果當前的桶采用紅黑樹，則調用紅黑樹的get方法去獲取節點if (first instanceof TreeNode)return ((TreeNode<K, V>) first).getTreeNode(hash, key);//如果當前的桶不采用紅黑樹，即桶中節點結構為鏈式結構do {//遍歷鏈表，直到key匹配if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}//如果哈希表為空，或者沒有找到節點，返回nullreturn null;
}

作者：阿進的寫字臺

出處：https://www.cnblogs.com/homejim/

本文版權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。