點擊上方?Java后端，選擇?設為星標

優質文章，及時送達

---

代碼中的注解多看幾遍，其中HashMap的擴容機制是要必懂知識！結合圖片一起理解！

什么是 HashMap?

HashMap 是基于哈希表的 Map 接口的非同步實現。此實現提供所有可選的映射操作，并允許使用 null 值和 null 鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。HashMap 的數據結構 在 Java 編程語言中，最基本的結構就是兩種，一個是數組，另外一個是模擬指針(引用)，所有的數據結構都可以用這兩個基本結構來構造的，HashMap 也不例外。HashMap 實際上是一個 “鏈表散列” 的數據結構，即數組和鏈表的結合體。文字描述永遠要配上圖才能更好的講解數據結構，HashMap 的結構圖如下。?從上圖中可以看出，HashMap 底層就是一個數組結構，數組中的每一項又是一個鏈表或者紅黑樹。當新建一個 HashMap 的時候，就會初始化一個數組。下面先通過大概看下 HashMap 的核心成員。public?class?HashMap<K,V> extends?AbstractMap<K,V>implements?Map<K,V>, Cloneable, Serializable?{// 默認容量，默認為16，必須是2的冪static?final?int?DEFAULT_INITIAL_CAPACITY = 1?<< 4;// 最大容量，值是2^30static?final?int?MAXIMUM_CAPACITY = 1?<< 30// 裝載因子，默認的裝載因子是0.75static?final?float?DEFAULT_LOAD_FACTOR = 0.75f;// 解決沖突的數據結構由鏈表轉換成樹的閾值，默認為8static?final?int?TREEIFY_THRESHOLD = 8;// 解決沖突的數據結構由樹轉換成鏈表的閾值，默認為6static?final?int?UNTREEIFY_THRESHOLD = 6;/* 當桶中的bin被樹化時最小的hash表容量。
?????* 如果沒有達到這個閾值，即hash表容量小于MIN_TREEIFY_CAPACITY，當桶中bin的數量太多時會執行resize擴容操作。
?????* 這個MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。
?????*/static?final?int?MIN_TREEIFY_CAPACITY = 64;static?class?Node<K,V> implements?Map.Entry<K,V> {//...
????}// 存儲數據的數組transient?Node[] table;// 遍歷的容器transient?Set> entrySet;// Map中KEY-VALUE的數量transient?int?size;/**
?????* 結構性變更的次數。
?????* 結構性變更是指map的元素數量的變化，比如rehash操作。
?????* 用于HashMap快速失敗操作，比如在遍歷時發生了結構性變更，就會拋出ConcurrentModificationException。
?????*/transient?int?modCount;// 下次resize的操作的size值。int?threshold;// 負載因子，resize后容量的大小會增加現有size * loadFactorfinal?float?loadFactor;
}

HashMap 的初始化

public?HashMap()?{this.loadFactor = DEFAULT_LOAD_FACTOR; // 其他值都是默認值
????}

通過源碼可以看出初始化時并沒有初始化數組 table，那只能在 put 操作時放入了，為什么要這樣做？估計是避免初始化了 HashMap 之后不使用反而占用內存吧，哈哈哈。

HashMap 的存儲操作

public?V put(K key, V value) {return?putVal(hash(key), key, value, false, true);
????}下面我們詳細講一下 HashMap 是如何確定數組索引的位置、進行 put 操作的詳細過程以及擴容機制 (resize)

hash 計算，確定數組索引位置

不管增加、刪除、查找鍵值對，定位到哈希桶數組的位置都是很關鍵的第一步。前面說過 HashMap 的數據結構是數組和鏈表的結合，所以我們當然希望這個 HashMap 里面的元素位置盡量分布均勻些，盡量使得每個位置上的元素數量只有一個，那么當我們用 hash 算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，不用遍歷鏈表，大大優化了查詢的效率。HashMap 定位數組索引位置，直接決定了 hash 方法的離散性能。看下源碼的實現:static?final?int?hash(Object key)?{ //jdk1.8int?h;// h = key.hashCode() 為第一步 取hashCode值// h ^ (h >>> 16) 為第二步 高位參與運算return?(key == null) ? 0?: (h = key.hashCode()) ^ (h >>> 16);
}

通過 hashCode() 的高 16 位異或低 16 位實現的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、質量來考慮的，這么做可以在數組 table 的 length 比較小的時候，也能保證考慮到高低 Bit 都參與到 Hash 的計算中，同時不會有太大的開銷。

大家都知道上面代碼里的 key.hashCode() 函數調用的是 key 鍵值類型自帶的哈希函數，返回 int 型散列值。理論上散列值是一個 int 型，如果直接拿散列值作為下標訪問 HashMap 主數組的話，考慮到 2 進制 32 位帶符號的 int 表值范圍從?2147483648 到 2147483648。前后加起來大概 40 億的映射空間。

只要哈希函數映射得比較均勻松散，一般應用是很難出現碰撞的。但問題是一個 40 億長度的數組，內存是放不下的。你想，HashMap 擴容之前的數組初始大小才 16。所以這個散列值是不能直接拿來用的。用之前還要先做對數組的長度取模運算，得到的余數才能用來訪問數組下標。源碼中模運算是在這個 indexFor( ) 函數里完成。

bucketIndex = indexFor(hash, table.length);//indexFor的代碼也很簡單，就是把散列值和數組長度做一個"與"操作，static?int?indexFor(int?h, int?length)?{return?h & (length-1);
}

順便說一下，這也正好解釋了為什么 HashMap 的數組長度要取 2 的整次冪。因為這樣(數組長度?1)正好相當于一個 “低位掩碼”?！芭c” 操作的結果就是散列值的高位全部歸零，只保留低位值，用來做數組下標訪問。以初始長度 16 為例，16?1=15。2 進制表示是 00000000 0000000000001111。和某散列值做 “與” 操作如下，結果就是截取了最低的四位值。

10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
??00000000 00000000 00000101 //高位全部歸零，只保留末四位但這時候問題就來了，這樣就算我的散列值分布再松散，要是只取最后幾位的話，碰撞也會很嚴重。更要命的是如果散列本身做得不好，分布上成等差數列的漏洞，恰好使最后幾個低位呈現規律性重復，就無比蛋疼。這時候 “擾動函數” 的價值就出來了，說到這大家應該都明白了，看下圖。?右位移 16 位，正好是 32bit 的一半，自己的高半區和低半區做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機性。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來。

putVal 方法

HashMap 的 put 方法執行過程可以通過下圖來理解，自己有興趣可以去對比源碼更清楚地研究學習。?源碼以及解釋如下:// 真正的put操作final V putVal(int?hash, K key, V value, boolean onlyIfAbsent,
???????????????????boolean evict) {
????????Node[] tab; Node p; int?n, i;// 如果table沒有初始化，或者初始化的大小為0，進行resize操作if?((tab = table) == null?|| (n = tab.length) == 0)
????????????n = (tab = resize()).length;// 如果hash值對應的桶內沒有數據，直接生成結點并且把結點放入桶中if?((p = tab[i = (n - 1) & hash]) == null)
????????????tab[i] = newNode(hash, key, value, null);// 如果hash值對應的桶內有數據解決沖突，再放入桶中else?{
????????????Node e; K k;//判斷put的元素和已經存在的元素是相同(hash一致，并且equals返回true)if?(p.hash == hash &&
????????????????((k = p.key) == key || (key != null?&& key.equals(k))))
????????????????e = p;// put的元素和已經存在的元素是不相同(hash一致，并且equals返回true)// 如果桶內元素的類型是TreeNode，也就是解決hash解決沖突用的樹型結構，把元素放入樹種else?if?(p instanceof TreeNode)
????????????????e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);else?{// 桶內元素的類型不是TreeNode，而是鏈表時，把數據放入鏈表的最后一個元素上for?(int?binCount = 0; ; ++binCount) {if?((e = p.next) == null) {
????????????????????????p.next = newNode(hash, key, value, null);// 如果鏈表的長度大于轉換為樹的閾值(TREEIFY_THRESHOLD)，將存儲元素的數據結構變更為樹if?(binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
????????????????????????????treeifyBin(tab, hash);break;
????????????????????}// 如果查已經存在key，停止遍歷if?(e.hash == hash &&
????????????????????????((k = e.key) == key || (key != null?&& key.equals(k))))break;
????????????????????p = e;
????????????????}
????????????}// 已經存在元素時if?(e != null) { // existing mapping for key
????????????????V oldValue = e.value;if?(!onlyIfAbsent || oldValue == null)
????????????????????e.value?= value;
????????????????afterNodeAccess(e);return?oldValue;
????????????}
????????}
????????++modCount;// 如果K-V數量大于閾值，進行resize操作if?(++size > threshold)
????????????resize();
????????afterNodeInsertion(evict);return?null;
????}擴容機制HashMap 的擴容機制用的很巧妙，以最小的性能來完成擴容。擴容后的容量就變成了變成了之前容量的 2 倍，初始容量為 16，所以經過 rehash 之后，元素的位置要么是在原位置，要么是在原位置再向高下標移動上次容量次數的位置，也就是說如果上次容量是 16，下次擴容后容量變成了 16+16，如果一個元素在下標為 7 的位置，下次擴容時，要不還在 7 的位置，要不在 7+16 的位置。我們下面來解釋一下 Java8 的擴容機制是怎么做到的？n 為 table 的長度，圖(a)表示擴容前的 key1 和 key2 兩種 key 確定索引位置的示例，圖(b)表示擴容后 key1 和 key2 兩種 key 確定索引位置的示例，其中 hash1 是 key1 對應的哈希與高位運算結果。?元素在重新計算 hash 之后，因為 n 變為 2 倍，那么 n-1 的 mask 范圍在高位多 1bit(紅色)，因此新的 index 就會發生這樣的變化：?因此，我們在擴充 HashMap 的時候，不需要像 JDK1.7 的實現那樣重新計算 hash，只需要看看原來的 hash 值新增的那個 bit 是 1 還是 0 就好了，是 0 的話索引沒變，是 1 的話索引變成 “原索引 + oldCap”，可以看看下圖為 16 擴充為 32 的 resize 示意圖：?而 hash 值的高位是否為 1，只需要和擴容后的長度做與操作就可以了，因為擴容后的長度為 2 的次冪，所以高位必為 1，低位必為 0，如 10000 這種形式，源碼中有 e.hash & oldCap 來做到這個邏輯。這個設計確實非常的巧妙，既省去了重新計算 hash 值的時間，而且同時，由于新增的 1bit 是 0 還是 1 可以認為是隨機的，因此 resize 的過程，均勻的把之前的沖突的節點分散到新的 bucket 了。這一塊就是 JDK1.8 新增的優化點。有一點注意區別，JDK1.7 中 rehash 的時候，舊鏈表遷移新鏈表的時候，如果在新表的數組索引位置相同，則鏈表元素會倒置，但是從上圖可以看出，JDK1.8 不會倒置。下面是 JDK1.8 的 resize 源碼，寫的很贊，如下:final?Node[] resize() {
????????Node[] oldTab = table;int?oldCap = (oldTab == null) ? 0?: oldTab.length;int?oldThr = threshold;int?newCap, newThr = 0;// 計算新的容量值和下一次要擴展的容量if?(oldCap > 0) {// 超過最大值就不再擴充了，就只好隨你碰撞去吧if?(oldCap >= MAXIMUM_CAPACITY) {
????????????????threshold = Integer.MAX_VALUE;return?oldTab;
????????????}// 沒超過最大值，就擴充為原來的2倍else?if?((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
?????????????????????oldCap >= DEFAULT_INITIAL_CAPACITY)
????????????????newThr = oldThr << 1; // double threshold
????????}else?if?(oldThr > 0) // initial capacity was placed in threshold
????????????newCap = oldThr;else?{ // zero initial threshold signifies using defaults
????????????newCap = DEFAULT_INITIAL_CAPACITY;
????????????newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
????????}// 計算新的resize上限if?(newThr == 0) {float?ft = (float)newCap * loadFactor;
????????????newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
??????????????????????(int)ft : Integer.MAX_VALUE);
????????}
????????threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})
????????????Node[] newTab = (Node[])new?Node[newCap];
????????table = newTab;if?(oldTab != null) {// 把每個bucket都移動到新的buckets中for?(int?j = 0; j < oldCap; ++j) {
????????????????Node e;//如果位置上沒有元素，直接為nullif?((e = oldTab[j]) != null) {
????????????????????oldTab[j] = null;//如果只有一個元素，新的hash計算后放入新的數組中if?(e.next == null)
????????????????????????newTab[e.hash & (newCap - 1)] = e;//如果是樹狀結構，使用紅黑樹保存else?if?(e instanceof?TreeNode)
????????????????????????((TreeNode)e).split(this, newTab, j, oldCap);//如果是鏈表形式else?{ // preserve order
????????????????????????Node loHead = null, loTail = null;
????????????????????????Node hiHead = null, hiTail = null;
????????????????????????Node next;do?{
????????????????????????????next = e.next;//hash碰撞后高位為0，放入低Hash值的鏈表中if?((e.hash & oldCap) == 0) {if?(loTail == null)
????????????????????????????????????loHead = e;else
????????????????????????????????????loTail.next = e;
????????????????????????????????loTail = e;
????????????????????????????}//hash碰撞后高位為1，放入高Hash值的鏈表中else?{if?(hiTail == null)
????????????????????????????????????hiHead = e;else
????????????????????????????????????hiTail.next = e;
????????????????????????????????hiTail = e;
????????????????????????????}
????????????????????????} while?((e = next) != null);// 低hash值的鏈表放入數組的原始位置if?(loTail != null) {
????????????????????????????loTail.next = null;
????????????????????????????newTab[j] = loHead;
????????????????????????}// 高hash值的鏈表放入數組的原始位置 + 原始容量if?(hiTail != null) {
????????????????????????????hiTail.next = null;
????????????????????????????newTab[j + oldCap] = hiHead;
????????????????????????}
????????????????????}
????????????????}
????????????}
????????}return?newTab;
????}作者：feigeswjtu鏈接：https://github.com/feigeswjtu

-?END -

最近整理一份面試資料《Java技術棧學習手冊》，覆蓋了Java技術、面試題精選、Spring全家桶、Nginx、SSM、微服務、數據庫、數據結構、架構等等。獲取方式：點“?在看，關注公眾號?Java后端?并回復?777?領取，更多內容陸續奉上。推薦閱讀?1.?21 屆校招薪資曝光：嚴重倒掛老員工！2.?Redis 五大數據類型使用場景3.?Linux 命令速查手冊4.?討論：Service層需要接口嗎？

5.?好用：強大的 IDEA 代碼生成器

喜歡文章，點個在看?

總結

以上是生活随笔為你收集整理的hashmap扩容机制_图文并茂：HashMap经典详解！的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。