一萬三千字的HashMap面試必問知識點詳解-有解無憂

概論
- Hasmap 的繼承關系
- hashmap 的原理
  - 解決Hash沖突的方法
    - 開放定址法
    - 再哈希法
    - 鏈地址法
    - 建立公共溢位區
  - hashmap 最終的形態
- Hashmap 的回傳值
HashMap 的關鍵內部元素
- 存盤容器 table;
- size 元素個數
- Node
- TreeNode
- modCount
- 閾值 threshold
- 實際存盤元素個數 size
debug 原始碼插入元素的程序
- 呼叫put()方法
- 呼叫 putval()
  - 呼叫hash() 方法
- 進入 putval()
  - 判斷陣列是否為空,需不需要呼叫resize 方法
    - table 為空首次初始化
    - table 不為空不是首次初始化
  - 判斷當前位置是否有元素
    - 1 沒有直接放入當前位置
    - 2 有將當前節點記做p
      - 判斷直接覆寫(判斷是否是同一個key)
      - 判斷插入紅黑樹
      - 判斷插入鏈表
      - 最后回傳oldValue 完成新值替換
  - 最后判斷是否需要擴容回傳null 值
- 單獨講解resize 方法
  - 第一部分初始化新陣列
  - 第二部分資料遷移
  - 第三部分回傳新的陣列
- 單獨講解樹化treeifyBin方法
獲取元素的程序
總結
- resize 方法總結
  - resize(擴容) 的上限
  - resize 方法只有三種情況下呼叫
  - resize 的回傳值
- key 的判斷
- 樹化
- for 回圈遍歷鏈表而不是while
- 你覺得Hashmap 還有什么可以改進的地方嗎，歡迎討論
番外篇
- hash 方法的實作方式
- 鏈表法導致的鏈表過深問題為什么不用二叉查找樹代替
- jdk8中對HashMap做了哪些改變
- Hashmap 的容量大小為什么要求是2n

概論

HashMap 是無論在作業還是面試中都非常常見常考的資料結構，比如 Leetcode 第一題 Two Sum 的某種變種的最優解就是需要用到 HashMap 的，高頻考題 LRU Cache 是需要用到 LinkedHashMap 的，HashMap 用起來很簡單，所以今天我們來從原始碼的角度梳理一下Hashmap
隨著JDK（Java Developmet Kit）版本的更新，JDK1.8對HashMap底層的實作進行了優化，例如引入紅黑樹的資料結構和擴容的優化等，
HashMap：它根據鍵的hashCode值存盤資料，大多數情況下可以直接定位到它的值，因而具有很快的訪問速度，但遍歷順序卻是不確定的，
HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null，
HashMap非執行緒安全，即任一時刻可以有多個執行緒同時寫HashMap，可能會導致資料的不一致，如果需要滿足執行緒安全，可以用 Collections的synchronizedMap方法使HashMap具有執行緒安全的能力，或者使用ConcurrentHashMap，

Hasmap 的繼承關系

hashmap 的原理

對于 HashMap 中的每個 key，首先通過 hash function 計算出一個 hash 值,這個hash值經過取模運算就代表了在 buckets 里的編號 buckets 實際上是用陣列來實作的，所以把這個hash值模上陣列的長度得到它在陣列的 index，就這樣把它放在了陣列里，
如果果不同的元素算出了相同的哈希值，那么這就是哈希碰撞，即多個 key 對應了同一個桶，這個時候就是解決hash沖突的時候了，展示真正技術的時候到了，
隨著插入的元素越來越多，發生碰撞的概率就越大，某個桶中的鏈表就會越來越長，直到達到一個閾值，HashMap就受不了了，為了提升性能，會將超過閾值的鏈表轉換形態，轉換成紅黑樹的結構，這個閾值是 8 ，也就是單個桶內的鏈表節點數大于 8 ，就會將鏈表有可能變身為紅黑樹，

解決Hash沖突的方法

開放定址法

這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希地址p=H(key）出現沖突時，以p為基礎，產生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中，這種方法有一個通用的再散列函式形式：

Hi=（H（key）+di）% m i=1，2，…，n

其中H(key）為哈希函式，m 為表長，di稱為增量序列，增量序列的取值方式不同，相應的再散列方式也不同，主要有三種線性探測再散列，二次探測再散列，偽隨機探測再散列

再哈希法

這種方法是同時構造多個不同的哈希函式

Hi=RH1（key） i=1，2，…，k

當哈希地址Hi=RH1（key）發生沖突時，再計算Hi=RH2（key）……，直到沖突不再產生，這種方法不易產生聚集，但增加了計算時間

鏈地址法

這種方法的基本思想是將所有哈希地址為i的元素構成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指標存在哈希表的第i個單元中，因而查找、插入和洗掉主要在同義詞鏈中進行，

鏈地址法適用于經常進行插入和洗掉的情況，

建立公共溢位區

這種方法的基本思想是：將哈希表分為基本表和溢位表兩部分，凡是和基本表發生沖突的元素，一律填入溢位表，

hashmap 最終的形態

一頓操作猛如虎，搞得原本還是很單純的hashmap 變得這么復雜，難倒了無數英雄好漢，由于鏈表長度程序，會導致查詢變慢，所以鏈表慢慢最后演化出了紅黑樹的形態

HashMap主體上就是一個陣列結構，每一個索引位置英文叫做一個 bin，我們這里先管它叫做桶，比如你定義一個長度為 8 的 HashMap，那就可以說這是一個由 8 個桶組成的陣列，

當我們像陣列中插入資料的時候，大多數時候存的都是一個一個 Node 型別的元素，Node 是 HashMap中定義的靜態內部類

Hashmap 的回傳值

很多人以為Hashmap 是沒有回傳值的，或者也沒有關注過Hashmap 的回傳值，其實在你呼叫Hashmap的put(key,value) 方法的時候，它會將當前key 已經有的值回傳，然后把你的新值放到對應key 的位置上

public class JavaHashMap {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<String, String>();
        String oldValue = https://www.cnblogs.com/data-magnifier/archive/2020/11/28/map.put("java大資料", "資料倉庫");
        System.out.println(oldValue);
        oldValue = https://www.cnblogs.com/data-magnifier/archive/2020/11/28/map.put("java大資料", "實時數倉");
        System.out.println(oldValue);
    }
}

運行結果如下，因為一開始是沒有值的，所以回傳null,后面有值了，put 的時候就回傳了舊的值

這里有一個問題需要注意一下，因為Map的Key,Value 的型別都是參考型別，所以在沒有值的情況下一定回傳的是null，而不是0 等初始值，

HashMap 的關鍵內部元素

存盤容器 table;

因為HashMap內部是用一個陣列來保存內容的，它的定義如下

transient Node<K,V>[] table

如果哈希桶陣列很大，即使較差的Hash演算法也會比較分散，如果哈希桶陣列陣列很小，即使好的Hash演算法也會出現較多碰撞，所以就需要在空間成本和時間成本之間權衡，其實就是在根據實際情況確定哈希桶陣列的大小，并在此基礎上設計好的hash演算法減少Hash碰撞，那么通過什么方式來控制map使得Hash碰撞的概率又小，哈希桶陣列（Node[] table）占用空間又少呢？答案就是好的Hash演算法和擴容機制，

在HashMap中，哈希桶陣列table的長度length大小必須為2的n次方(一定是合數)，這是一種非常規的設計，常規的設計是把桶的大小設計為素數，相對來說素數導致沖突的概率要小于合數

size 元素個數

size這個欄位其實很好理解，就是HashMap中實際存在的鍵值對數量，注意和table的長度length、容納最大鍵值對數量threshold的區別

Node

 static class Node<K,V> implements Map.Entry<K,V> {
     final int hash;
     final K key;
     V value;
     Node<K,V> next;

     Node(int hash, K key, V value, Node<K,V> next) {
         this.hash = hash;
         this.key = key;
         this.value = https://www.cnblogs.com/data-magnifier/archive/2020/11/28/value;
         this.next = next;
     }
}

Node是HashMap的一個靜態內部類，實作了Map.Entry介面，本質是就是一個映射(鍵值對),主要包括 hash、key、value 和 next 的屬性，
我們使用 put 方法像其中加鍵值對的時候，就會轉換成 Node 型別，其實就是newNode(hash, key, value, null);

TreeNode

當桶內鏈表到達 8 的時候，會將鏈表轉換成紅黑樹，就是 TreeNode型別，它也是 HashMap中定義的靜態內部類，

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
}

說起TreeNode ，就不得不說其他三個相關引數 TREEIFY_THRESHOLD=8 和 UNTREEIFY_THRESHOLD=6 以及 MIN_TREEIFY_CAPACITY=64

TREEIFY_THRESHOLD=8 指的是鏈表的長度大于8 的時候進行樹化， UNTREEIFY_THRESHOLD=6 說的是當元素被洗掉鏈表的長度小于6 的時候進行退化，由紅黑樹退化成鏈表

MIN_TREEIFY_CAPACITY=64 意思是陣列中元素的個數必須大于等于64之后才能進行樹化

modCount

modCount欄位主要用來記錄HashMap內部結構發生變化的次數，主要用于迭代的快速失敗，強調一點，內部結構發生變化指的是結構發生變化，例如put新鍵值對，但是某個key對應的value值被覆寫不屬于結構變化，

閾值 threshold

它是加在因子乘以初始值大小，后續擴容的時候和陣列大小一樣，2倍進行擴容

threshold = (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)

實際存盤元素個數 size

size 默認大小是0 ，它指的是陣列存盤的元素個數，而不是整個hashmap 的元素個數，對于下面這張圖就是3 而不是11

transient int size;

debug 原始碼插入元素的程序

public class JavaHashMap {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<String, String>();
        String oldValue = https://www.cnblogs.com/data-magnifier/archive/2020/11/28/map.put("java大資料", "資料倉庫");
    }
}

呼叫put()方法

這個方法沒什么好說的，是hashmap 提供給用戶呼叫的方法，很簡單

呼叫 putval()

Put 方法實際上呼叫的實 putval() 方法

可以看出在進入putval() 方法之間，需要借助hash 方法先計算出key 的hash 值，然后將key 的hash值和key同時傳入

呼叫hash() 方法

這個key的hashCode()方法得到其hashCode 值（該方法適用于每個Java物件），然后再通過Hash演算法的后兩步運算（高位運算和取模運算，下文有介紹）來定位該鍵值對的存盤位置，有時兩個key會定位到相同的位置，表示發生了Hash碰撞，當然Hash演算法計算結果越分散均勻，Hash碰撞的概率就越小，map的存取效率就會越高，
在JDK1.8的實作中，優化了高位運算的演算法，通過hashCode()的高16位異或低16位實作的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、質量來考慮的，這么做可以在陣列table的length比較小的時候，也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷，

進入 putval()

進入putval 方法之后，整體資料流程如下，下面會詳細介紹每一步

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 判斷是否需要初始化陣列
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
    		// 當前位置為空，則直接插入，同時意味著不走else 最后直接回傳null
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            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 1st
                        treeifyBin(tab, hash);
                    break;
                }
                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 = https://www.cnblogs.com/data-magnifier/archive/2020/11/28/e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 可以看出只有當前key 的位置為空的時候才判斷時候需要reszie 已經回傳 null 其他情況下都走了else 的環節
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

判斷陣列是否為空,需不需要呼叫resize 方法

第一次呼叫，這里table 是null,所以會走resize 方法

resize 方法本身也是比較復雜的，因為這里是第一次呼叫，所以這里進行了簡化

    final Node<K,V>[] resize() {
        Node<K,V>[] 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;
            }
            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);
        }
        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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
           // 因為 oldTab 為null 所以不會進來這個if 判斷，所以將這里的代碼省略了
        }
        return newTab;
    }

table 為空首次初始化

如果是的話，初始化陣列大小和threashold

newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

初始化之后，將新創建的陣列回傳，在回傳之前完成了對變數table 的賦值

table 不為空不是首次初始化

如果不是的話就用當前陣列的資訊初始化新陣列的大小

最后完成table 的初始化，回傳table ，這里其實還有資料遷移，但是為了保證文章的結構，所以將resize 方法的詳細講解單獨提了出來

table = newTab;

判斷當前位置是否有元素

1 沒有直接放入當前位置

“

2 有將當前節點記做p

“

當前節點記做p 然后進入else 回圈

else {
    Node<K,V> e; K k;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        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 1st
                    treeifyBin(tab, hash);
                break;
            }
            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 = https://www.cnblogs.com/data-magnifier/archive/2020/11/28/e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
 }

判斷直接覆寫(判斷是否是同一個key)

判斷新的key 和老的key 是否相同，這里同時要求了hash 值和實際的值是相等的情況下然后直接完成了e=p 的賦值，其實也就是完成了替換，因為key 是相同的，

如果不是同一個key 的話這里就要將當前元素插入鏈表或者紅黑樹了，因為是不同的key 了

判斷插入紅黑樹

如果當前元素是一個 TreeNode 則將當前元素放入紅黑樹，然后

判斷插入鏈表

如果不是同一key并且當前元素型別不是TreeNode 則將當前元素插入鏈表(因為key對應的位置已經有元素了，其實可以認為是鏈表的頭元素)
可以看出采用的是尾插法，回圈程序中當下一個節點是null的時候則進行插入，插入完畢之后判斷是否需要樹化

JDK 1.7 之前使用頭插法、JDK 1.8 使用尾插法
其實主要是根據（e=p.next)==null 進行判斷進入哪一個if ,因為每個 if 都含有break 陳述句，所以只能進入一個然后就退出回圈了
```
   if ((e = p.next) == null) {
       p.next = newNode(hash, key, value, null);
       if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
           treeifyBin(tab, hash);
       break;
   }
```
1、這段代碼也是上圖中的第一個if這段代碼的意思就是在遍歷鏈表的程序中，一直都沒有遇到和待插入key 相同的key(第二個if) 然后當前要插入的元素插入到了鏈表的尾部(當前if 陳述句)

第二個if 的意思如果有發生key沖突則停止后續這個節點會被相同的key覆寫

2、插入之后判斷判斷區域變數binCount 時候大于7(TREEIFY_THRESHOLD-1),這里需要注意的是binCount 是從0開始的，所以實際的意思是判斷鏈表的長度在插入新元素之前是否大于等于8，如果是的話則進行樹化

3、并且這個時候變數e 的值是null ，因為是插入到鏈表的尾部的，所以這個時候key 是沒有對應的oldValue 的，所以e是null 在最后面的判斷回傳中，也回傳的是null

4、關于樹化，首先這是發生在插入鏈表的時刻,并且是插入鏈表尾部的時候，因為判斷程序是在第一個if 中，為了保證文章的結構關于樹化放在下面講
```
if (e.hash == hash &&
    ((k = e.key) == key || (key != null && key.equals(k))))
    break;
// 這個賦值很有意思，它完成了你可以使用for 回圈完成鏈表遍歷的核心功能    
p = e;
```
1、這一段代碼的意思是在遍歷的程序中（e=p.next)!=null 的的時候，也就是在回圈鏈表的程序中，判斷是否有和當前key 相等的key，相等的話e 就是要覆寫的元素，如果不相等的話就繼續回圈，知道找到這樣的e 或者是將鏈表回圈結束，然后將元素插入到鏈表的尾部(第一個if)

2、因為是當key 存在的時候則跳出回圈，所以鏈表的長度沒有發生變化，所以這里沒有判斷是否需要樹化

最后回傳oldValue 完成新值替換

if (e != null) { // existing mapping for key
    V oldValue = https://www.cnblogs.com/data-magnifier/archive/2020/11/28/e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

這個時候e 就指向原來p 的位置了，因為e=p，然后用新的value 覆寫掉了oldValue 完成了插入，最后將 oldValue 回傳，

最后判斷是否需要擴容回傳null 值

其實能走到這一步，是那就說明放入元素的時候，key 對應的位置是沒有元素的，所以相當于陣列中添加了一個新的元素，所以這里有判斷是否需要resize 和回傳空值，

 ++modCount;
 if (++size > threshold)
     resize();
 afterNodeInsertion(evict);
 return null;

單獨講解resize 方法

首選需要記住resize 方法是會回傳擴容后的陣列的

第一部分初始化新陣列

這一部分不論是不是首次呼叫resize 方法，都會有的，但是資料遷移部分在首次呼叫的時候是沒有的

Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 判斷是oldCap 是否大于0 因為可能是首次resize，如果不是的話 oldCap
if (oldCap > 0) {
	 // 到達擴容上限
    if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    // 這里是正常的擴容
    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;
//第一次呼叫resize 方法，然后使用默認值進行初始化
else {
		// zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

如果陣列的大小大于等于MAXIMUM_CAPACITY之后，則 threshold = Integer.MAX_VALUE; 然后不擴容直接回傳當前陣列，所以可以看出hashmap 的擴容上限就是MAXIMUM_CAPACITY（2³⁰）
如果陣列的大小在擴容之后小于MAXIMUM_CAPACITY 并且原始大小大于DEFAULT_INITIAL_CAPACITY（16）則進行擴容(DEFAULT_INITIAL_CAPACITY 的大小限制是為了防止該方法的呼叫是在樹化方法里呼叫的，這個時候陣列大大小可能小于DEFAULT_INITIAL_CAPACITY)
新的陣列創建好之后，就可以根據老的陣列是否有值決定是否進行資料遷移

第二部分資料遷移

oldTab 也就是老的陣列不為空的時候進行遷移

 if (oldTab != null) {
 			// 遍歷oldTable，拿到每一個元素準備放入大新的陣列中去
      for (int j = 0; j < oldCap; ++j) {
          Node<K,V> e;
          if ((e = oldTab[j]) != null) {
              oldTab[j] = null;
              // 當前元素只是單個元素，不是鏈表
              if (e.next == null)
                  // 重新計算每個元素在陣列中的位置
                  newTab[e.hash & (newCap - 1)] = e;
              // 判斷當前元素是否是樹   
              else if (e instanceof TreeNode)
                  ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
              // 當前元素是鏈表，則遍歷鏈表    
              else { // preserve order
                  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;
                          else
                              loTail.next = e;
                          loTail = e;
                      }
                      else {
                          if (hiTail == null)
                              hiHead = e;
                          else
                              hiTail.next = e;
                          hiTail = e;
                      }
                  } while ((e = next) != null);
                  if (loTail != null) {
                      loTail.next = null;
                      newTab[j] = loHead;
                  }
                  if (hiTail != null) {
                      hiTail.next = null;
                      newTab[j + oldCap] = hiHead;
                  }
              }
          }
      }
  }

判斷當前元素的next 是否為空，是則直接放入，其實就是只有一個元素，說明這是一個最正常的節點，不是桶內鏈表，也不是紅黑樹，這樣的節點會重新計算索引位置，然后插入，
是的話，判斷是不是TreeNode,不是的話則直接遍歷鏈表進行拷貝，保證鏈表的順序不變，
是的話則呼叫 TreeNode.split() 方法，如果是一顆紅黑樹，則使用 split方法處理，原理就是將紅黑樹拆分成兩個 TreeNode 鏈表，然后判斷每個鏈表的長度是否小于等于 6，如果是就將 TreeNode 轉換成桶內鏈表，否則再轉換成紅黑樹，
完成資料的拷貝，回傳新的陣列

第三部分回傳新的陣列

 return newTab;

只要沒有到達擴容上限，這一部分是肯定會走的，至于走不走資料遷移，需要潘丹是不是首次resize()

單獨講解樹化treeifyBin方法

 for (int binCount = 0; ; ++binCount) {
     if ((e = p.next) == null) {
         p.next = newNode(hash, key, value, null);
         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
             treeifyBin(tab, hash);
         break;
     }
     if (e.hash == hash &&
         ((k = e.key) == key || (key != null && key.equals(k))))
         break;
     p = e;
 }

首先判斷是符滿足鏈表長度大于8(binCount 是否大于等于7) ,需要注意的是插入到鏈表的尾部導致鏈表的長度發生了變化的情況下，才判斷是否需要樹化
然后進入treeifyBin 方法中，進入樹化方法之后又判斷了,Hashmap 的大小是否大于64，如果不是的話，只是呼叫了resize 方法，讓陣列擴容，而不是樹化

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

獲取元素的程序

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
 * Implements Map.get and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

總結

resize 方法總結

resize(擴容) 的上限

resize 不是無限的，當到達resize 的上限，也就是2³⁰ 之后，不再擴容

resize 方法只有三種情況下呼叫

- 第一種 是在**首次插入元素的時候完成陣列的初始化**
- 第二種 是在元素插入**完成后**判斷是否需要陣列擴容，如果是的話則呼叫
- 第三種 是在元素插入鏈表尾部之后，進入樹化方法之后，如果不樹化則進行resize

resize 的回傳值

第一種情況下回傳老的陣列也就是沒有resize 因為已經達到resize 的上限了
第二種情況下回傳一個空的陣列也就是第一次呼叫resize方法
第三章情況下回傳一個擴容后的陣列完成了資料遷移后的陣列

key 的判斷

第一次判斷是當前位置有元素的時候，如果兩個key 相等則準備覆寫值
第二次判斷是遍歷鏈表的時候，決定能否覆寫鏈表中間key 相等的值而不是鏈表的尾部

樹化

樹化是發生在元素插入鏈表之后，并且這里是插入到鏈表的尾部導致鏈表的長度發生了變化的情況下(也就是走的for回圈里的第一個if 陳述句)，而不是替換了鏈表里面的某一元素(也就是走的for回圈里的第二個if 陳述句)
```
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}
```
其實這代碼上面有一段注釋的，這里也帖一下,在table 太小的情況下，使用resize 否則替換指的位置鏈表上的全部Nodes（其實就是替換成紅黑樹）
```
 /**
  * Replaces all linked nodes in bin at index for given hash unless
  * table is too small, in which case resizes instead.
  */
```
其實這里有一個隱含的意義，就是陣列不大的時候，希望通過resize 的方法降低hash 沖突的概率，從而避免鏈表過長降低查詢時間，但是當陣列比較大的時候reszie 成本太高，則通過將鏈表轉化成紅黑樹來降低查詢時間

for 回圈遍歷鏈表而不是while

這是源代碼里面的一段，上面也解釋過了，這里使用for 回圈遍歷鏈表，利用for 回圈的index 進行計數，這里進行了刪減

for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
    		doSomething();
        break;
    
    p = e;
}

你覺得Hashmap 還有什么可以改進的地方嗎，歡迎討論

雖然java 源代碼的山很高，如果你想跨越，至少你得有登山的勇氣，這里我給出自己的一點點愚見，希望各位不吝指教

番外篇

這里如果你不感興趣可以不閱讀??

hash 方法的實作方式

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

JDK 1.8 中，是通過 hashCode() 的高 16 位異或低 16 位實作的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度，功效和質量來考慮的，減少系統的開銷，也不會造成因為高位沒有參與下標的計算，從而引起的碰撞

為什么要用異或運算子？ 保證了物件的 hashCode 的 32 位值只要有一位發生改變，整個 hash() 回傳值就會改變，盡可能的減少碰撞，

鏈表法導致的鏈表過深問題為什么不用二叉查找樹代替

之所以選擇紅黑樹是為了解決二叉查找樹的缺陷，二叉查找樹在特殊情況下會變成一條線性結構（這就跟原來使用鏈表結構一樣了，造成很深的問題），遍歷查找會非常慢，

而紅黑樹在插入新資料后可能需要通過左旋，右旋、變色這些操作來保持平衡，引入紅黑樹就是為了查找資料快，解決鏈表查詢深度的問題，我們知道紅黑樹屬于平衡二叉樹，但是為了保持“平衡”是需要付出代價的，但是該代價所損耗的資源要比遍歷線性鏈表要少，所以當長度大于8的時候，會使用紅黑樹，如果鏈表長度很短的話，根本不需要引入紅黑樹，引入反而會慢，

jdk8中對HashMap做了哪些改變

在java 1.8中，如果鏈表的長度超過了8，那么鏈表將轉換為紅黑樹，（桶的數量必須大于64，小于64的時候只會擴容）

發生hash碰撞時，java 1.7 會在鏈表的頭部插入，而java 1.8會在鏈表的尾部插入

在java 1.8中，Entry被Node替代(換了一個馬甲)

Hashmap 的容量大小為什么要求是2ⁿ

這里首選要說明一個前提，那就是元素在陣列中的位置的計算方式是 tab[i = (n - 1) & hash] 也就是通過對陣列大小求模得到的，因為我們知道hash 的計算方式是 hashCode() 的高 16 位異或低 16 位實作的，32 位值只要有一位發生改變，整個 hash() 回傳值就會改變，也就是說我們的hash 值發生沖突的概率是比較小的，也就是說hash 值是比較隨機的

所以更多的沖突是發生在取模的時候，所以這個時候只要保證了我們的取模運算 (n - 1) & hash，盡量能保證hash 值的特性也就是隨機性，因為我們知道與運算的特點是,兩位同時為“1”，結果才為“1”，否則為0

所以這個時候我們只要 (n - 1) 讓的二進制表示都是一串1，例如"011111" 就可以了，因為安位與1 結果是不變的，也就是可以延續hash 值的散列性

其實到這里就差不多了，然后我們看2ⁿ 的表示特點，然后就知道為什么要就hashmap 的大小是 2ⁿ了, 2ⁿ次方的二進制表示大家肯定都很清楚，2的6次方，就是從右向左 6 個 0，然后第 7 位是 1

其實這下我們就知道為什么了，因為只有陣列的長度是2的次方了，n-1 的二進制才能盡可能多的是1

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/228078.html

標籤：其他

上一篇：一萬三千字的HashMap面試必問知識點詳解

下一篇：15 面向物件基本概念

一萬三千字的HashMap面試必問知識點詳解

概論