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

基于Hash的原理。

2 什么是哈希？

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

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

“

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

Java 中所有的對象都有 Hash 方法，Java中的所有對象都繼承 Object 類中定義的 hashCode() 函數(shù)的默認實現(xiàn)。此函數(shù)通常通過將對象的內(nèi)部地址轉(zhuǎn)換為整數(shù)來生成哈希碼，從而為所有不同的對象生成不同的哈希碼。

3 HashMap 中的 Node 類

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

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

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

當然，Node 類具有存儲為屬性的鍵和值的映射。?

key 已被標記為 final，另外還有兩個字段：next 和 hash。

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

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

鍵值對在 HashMap 中是以 Node 內(nèi)部類的數(shù)組存放的， 如下所示：

transient?Node[]?table;

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

該數(shù)組的長度始終是 2 的次冪， 通過以下的函數(shù)實現(xiàn)該過程

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

其原理是將傳入?yún)?shù) (cap) 的低二進制全部變?yōu)?1， 最后加 1 即可獲得對應(yīng)的大于 cap 的 2 的次冪作為數(shù)組長度。

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

在此有涉及到 HashMap 的 hash 函數(shù)及數(shù)組下標的計算， 鍵(key)所計算出來的哈希碼有可能是大于數(shù)組的容量的， 那怎么辦？

可以通過簡單的求余運算來獲得， 但此方法效率太低。HashMap 中通過以下的方法保證 hash 的值計算后都小于數(shù)組的容量。

(n?-?1)?&?hash

這也正好解釋了為什么需要 2 的次冪作為數(shù)組的容量。由于 n 是 2 的次冪， 因此， n - 1 類似于一個低位掩碼。?

通過與操作， 高位的hash值全部歸零，保證低位才有效， 從而保證獲得的值都小于 n。同時， 在下一次 resize() 操作時， 重新計算每個 Node 的數(shù)組下標將會因此變得很簡單， 具體的后文講解。?

以默認的初始值 16 為例：

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

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

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

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

此方法保證了高16位不變， 低16位根據(jù)異或后的結(jié)果改變。計算后的數(shù)組下標將會從原先的 5 變?yōu)?0。

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

5 哈希碰撞及其處理

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

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

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

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

static?final?int?TREEIFY_THRESHOLD?=?8;

static?final?int?UNTREEIFY_THRESHOLD?=?6;

6 HashMap 的初始化

public?HashMap();
public?HashMap(int?initialCapacity);
public?HashMap(Map?m);
public?HashMap(int?initialCapacity,?float?loadFactor);?

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

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

通過該函數(shù)進行了容量和負載因子的初始化，如果是調(diào)用的其他的構(gòu)造函數(shù)， 則相應(yīng)的負載因子和容量會使用默認值（默認負載因子=0.75， 默認容量=16）。

在此時， 還沒有進行存儲容器 table 的初始化， 該初始化要延遲到第一次使用時進行。HashMap 面試 21 問！面試的推薦你看下。關(guān)注公眾號Java技術(shù)?；貜兔嬖嚝@取更多面試資料。

7 HashMap 中哈希表的初始化或動態(tài)擴容

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

transient?Node[]?table;

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

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

7.1 擴容發(fā)生的條件

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

threshold?=?loadFactor?*?capacity

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

threshold?=?loadFactor?*?capacity?=?0.75?*?16?=?12

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

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

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

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

index?=?(table.length?-?1)?&?hash

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

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

7.3 步驟

1. 先判斷是初始化還是擴容， 兩者在計算 newCap和newThr 時會不一樣

2. 計算擴容后的容量，臨界值。

3. 將hashMap的臨界值修改為擴容后的臨界值

4. 根據(jù)擴容后的容量新建數(shù)組，然后將hashMap的table的引用指向新數(shù)組。

5. 將舊數(shù)組的元素復制到table中。在該過程中， 涉及到幾種情況， 需要分開進行處理（只存有一個元素， 一般鏈表， 紅黑樹）

具體的看代碼吧

final?Node[]?resize()?{
????????//新建oldTab數(shù)組保存擴容前的數(shù)組table
????????Node[]?oldTab?=?table;
????????//獲取原來數(shù)組的長度
????????int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;
????????//原來數(shù)組擴容的臨界值
????????int?oldThr?=?threshold;
????????int?newCap,?newThr?=?0;
????????//如果擴容前的容量?>?0
????????if?(oldCap?>?0)?{
????????????//如果原來的數(shù)組長度大于最大值(2^30)
????????????if?(oldCap?>=?MAXIMUM_CAPACITY)?{
????????????????//擴容臨界值提高到正無窮
????????????????threshold?=?Integer.MAX_VALUE;
????????????????//無法進行擴容，返回原來的數(shù)組
????????????????return?oldTab;
????????????????//如果現(xiàn)在容量的兩倍小于MAXIMUM_CAPACITY且現(xiàn)在的容量大于DEFAULT_INITIAL_CAPACITY
????????????}?else?if?((newCap?=?oldCap?<????????????????????oldCap?>=?DEFAULT_INITIAL_CAPACITY)
????????????????//臨界值變?yōu)樵瓉淼?倍
????????????????newThr?=?oldThr?<????????}?else?if?(oldThr?>?0)?//如果舊容量?<=?0，而且舊臨界值?>?0
????????????//數(shù)組的新容量設(shè)置為老數(shù)組擴容的臨界值
????????????newCap?=?oldThr;
????????else?{?//如果舊容量?<=?0，且舊臨界值?<=?0，新容量擴充為默認初始化容量，新臨界值為DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY
????????????newCap?=?DEFAULT_INITIAL_CAPACITY;//新數(shù)組初始容量設(shè)置為默認值
????????????newThr?=?(int)?(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);//計算默認容量下的閾值
????????}
????????//?計算新的resize上限
????????if?(newThr?==?0)?{//在當上面的條件判斷中，只有是初始化時(oldCap=0,?oldThr?>?0)時，newThr?==?0
????????????//ft為臨時臨界值，下面會確定這個臨界值是否合法，如果合法，那就是真正的臨界值
????????????float?ft?=?(float)?newCap?*?loadFactor;
????????????//當新容量float)MAXIMUM_CAPACITY，新的臨界值為ft，否則為Integer.MAX_VALUE
????????????newThr?=?(newCap?float)?MAXIMUM_CAPACITY??
????????????????????(int)?ft?:?Integer.MAX_VALUE);
????????}
????????//將擴容后hashMap的臨界值設(shè)置為newThr
????????threshold?=?newThr;
????????//創(chuàng)建新的table，初始化容量為newCap
????????@SuppressWarnings({"rawtypes",?"unchecked"})
????????Node[]?newTab?=?(Node[])?new?Node[newCap];
????????//修改hashMap的table為新建的newTab
????????table?=?newTab;
????????//如果舊table不為空，將舊table中的元素復制到新的table中
????????if?(oldTab?!=?null)?{
????????????//遍歷舊哈希表的每個桶，將舊哈希表中的桶復制到新的哈希表中
????????????for?(int?j?=?0;?j?????????????????Node?e;
????????????????//如果舊桶不為null，使用e記錄舊桶
????????????????if?((e?=?oldTab[j])?!=?null)?{
????????????????????//將舊桶置為null
????????????????????oldTab[j]?=?null;
????????????????????//如果舊桶中只有一個node
????????????????????if?(e.next?==?null)
????????????????????????//將e也就是oldTab[j]放入newTab中e.hash?&?(newCap?-?1)的位置
????????????????????????newTab[e.hash?&?(newCap?-?1)]?=?e;
????????????????????????//如果舊桶中的結(jié)構(gòu)為紅黑樹
????????????????????else?if?(e?instanceof?TreeNode)
????????????????????????//將樹中的node分離
????????????????????????((TreeNode)?e).split(this,?newTab,?j,?oldCap);
????????????????????else?{??//如果舊桶中的結(jié)構(gòu)為鏈表,鏈表重排，jdk1.8做的一系列優(yōu)化
????????????????????????Node?loHead?=?null,?loTail?=?null;
????????????????????????Node?hiHead?=?null,?hiTail?=?null;
????????????????????????Node?next;
????????????????????????//遍歷整個鏈表中的節(jié)點
????????????????????????do?{
????????????????????????????next?=?e.next;
????????????????????????????//?原索引
????????????????????????????if?((e.hash?&?oldCap)?==?0)?{
????????????????????????????????if?(loTail?==?null)
????????????????????????????????????loHead?=?e;
????????????????????????????????else
????????????????????????????????????loTail.next?=?e;
????????????????????????????????loTail?=?e;
????????????????????????????}?else?{//?原索引+oldCap
????????????????????????????????if?(hiTail?==?null)
????????????????????????????????????hiHead?=?e;
????????????????????????????????else
????????????????????????????????????hiTail.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 設(shè)計的非常優(yōu)秀， 但是應(yīng)該盡可能少的避免 resize(), 該過程會很耗費時間。

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

8 HashMap.put() 函數(shù)內(nèi)部是如何工作的？

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

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

源碼如下：

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

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

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

/**
?*?返回指定的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?e;
????//根據(jù)key及其hash值查詢node節(jié)點，如果存在，則返回該節(jié)點的value值
????return?(e?=?getNode(hash(key),?key))?==?null???null?:?e.value;
}

其最終是調(diào)用了 getNode 函數(shù)。其邏輯如下

源碼如下：

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