HashMap原始碼分析（JDK7）-有解無憂

上一節分析了JDK8中HashMap的結構和主要方法，這節就對比一下JDK7中的HashMap的實作

1.put & addEntry

`-`put()

根據key計算hash值，然后根據hash得到具體槽點位置
遍歷當前槽點的鏈表
- 如果發現相同key直接覆寫，回傳oldValue
- 沒有相同key的節點，就將新節點尾插（addEntry）

public V put(K key, V value)
{
    ......
    // 計算Hash值
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    // 遍歷當前槽點的鏈表
    // 注：jdk7中還沒有紅黑樹，因此解決哈希碰撞就只有拉鏈
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 如果該key已存在，則替換掉舊的value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    // 該key不存在，需要增加一個結點
    addEntry(hash, key, value, i);
    return null;
}

`--`addEntry()

當key不存在時，呼叫addEntry()方法添加新節點

void addEntry(int hash, K key, V value, int bucketIndex)
{
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    // 查看當前的size是否超過了閾值threshold，如果超過，需要resize
    if (size++ >= threshold)
        resize(2 * table.length); // 直接傳入擴容后的大小，2*len
}

2.resize & transfer

`-`resize()

判斷能否擴容，并創建新陣列

// 傳入新的容量  
void resize(int newCapacity) {   
    // 參考擴容前的Entry陣列  
    Entry[] oldTable = table;    
    int oldCapacity = oldTable.length;  
    // 擴容前的陣列大小如果已經達到最大(2^30)了 
    if (oldCapacity == MAXIMUM_CAPACITY) {  
        //修改閾值為int的最大值(2^31-1)，這樣以后就不會擴容了 
        threshold = Integer.MAX_VALUE;  
        return;  
    }  
    
	// 初始化一個新的Entry陣列
    Entry[] newTable = new Entry[newCapacity];  
    //！！將資料轉移到新的Entry陣列里，這里包含最重要的重新定位
    transfer(newTable);    
    // 將當前執行緒創建的新陣列置為Map的陣列
    table = newTable; 
    // 修改閾值  
    threshold = (int) (newCapacity * loadFactor);
}

`--`transfer(真正擴容)

擴容策略：

將原陣列的所有結點重新計算位置
保存原鏈表：e保存當前節點，next記錄下一個結點（e.next)
- 新槽點頭插（注：put時是尾插）
  - 連接：e.next = newTab[i]
  - 下移：newTab[i] = e
- 后移處理下一個結點：e = next

void transfer(Entry[] newTable) {  
    // src參考了舊的Entry陣列  
    Entry[] src = table;                    
    int newCapacity = newTable.length; 
    // 遍歷舊的Entry陣列  
    for (int j = 0; j < src.length; j++) { 
        Entry<K, V> e = src[j];             
        if (e != null) {  
            // 釋放舊Entry陣列的物件參考
            src[j] = null;  
            do {  
                // next用來保存當前節點之后的節點
                Entry<K, V> next = e.next;  
                //！！重新計算每個元素在陣列中的位置 
                int i = indexFor(e.hash, newCapacity);  
                // 新槽點頭插
                e.next = newTable[i]; //標記[1]  
                //將元素放在陣列上  
                newTable[i] = e; 
                // 原鏈表節點后移
                e = next;              
            } while (e != null);  
        }  
    }  
}

3.擴容時死鎖問題分析

產生死鎖的前提
- 多個執行緒同時都要擴容
  - 兩個執行緒都已經在自己的堆疊空間建立了陣列
  - 且一個執行緒剛好執行到：保存完e，與next，然后掛起
- e與next在擴容后還在一個槽位

do {
  Entry<K,V> next = e.next; // 執行緒一執行至此被掛起，執行執行緒二
  int i = indexFor(e.hash, newCapacity);
  e.next = newTable[i];
  newTable[i] = e;
  e = next;
} while (e != null);

死鎖產生原因
三次回圈后成環，新槽點上的兩個節點 A.next = B && B.next = A
程序圖解
- 執行緒一記錄執行狀態，掛起
- 執行緒二正常完成擴容，擴容后e next仍在同一個槽點，且逆序排列；執行緒一記錄的e next不變
- 執行緒一恢復運行，第一次回圈：先將e（A）插入到槽點（3）；然后e=next（B）
- 執行緒一繼續運行，第二次回圈：next=e.next(A)，將e（B）頭插到槽點（3），e=next（A）
- 執行緒一死鎖產生，第三次回圈：next=e.next=null，將e（A）再頭插到槽點（3），形成環