HashMap 基本實現(xiàn)（JDK 8 之前）

HashMap 通常會用一個指針數組（假設為 table[]）來做分散所有的 key，當一個 key 被加入時，會通過 Hash 算法通過 key 算出這個數組的下標 i，然后就把這個 <key, value> 插到 table[i] 中，如果有兩個不同的 key 被算在了同一個 i，那么就叫沖突，又叫碰撞，這樣會在 table[i] 上形成一個鏈表

如果 table[] 的尺寸很小，比如只有 2 個，如果要放進 10 個 keys 的話，那么碰撞非常頻繁，于是一個 O(1) 的查找算法，就變成了鏈表遍歷，性能變成了 O(n)，這是 Hash 表的缺陷

所以，Hash 表的尺寸和容量非常的重要。一般來說，Hash 表這個容器當有數據要插入時，都會檢查容量有沒有超過設定的 threshold，如果超過，需要增大 Hash 表的尺寸，但是這樣一來，整個 Hash 表里的元素都需要被重算一遍。這叫 rehash，這個成本相當的大

HashMap 的 rehash 源代碼

Put 一個 Key, Value 對到 Hash 表中：

public V put(K key, V value) {
    ......
    // 計算 Hash 值
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    // 如果該 key 已被插入，則替換掉舊的 value（鏈接操作）
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        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;
}

檢查容量是否超標

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);
}

新建一個更大尺寸的 hash 表，然后把數據從老的 Hash 表中遷移到新的 Hash 表中

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    ......
    // 創(chuàng)建一個新的 Hash Table
    Entry[] newTable = new Entry[newCapacity];
    // 將 Old Hash Table 上的數據遷移到 New Hash Table 上
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

遷移的源代碼

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    //下面這段代碼的意思是：
    //  從OldTable里摘一個元素出來，然后放到NewTable中
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            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);
        }
    }
}

該方法實現(xiàn)的機制就是將每個鏈表轉化到新鏈表，并且鏈表中的位置發(fā)生反轉，而這在多線程情況下是很容易造成鏈表回路，從而發(fā)生 get() 死循環(huán)。所以只要保證建新鏈時還是按照原來的順序的話就不會產生循環(huán)（JDK 8 的改進）

正常的 ReHash 的過程

• 假設我們的 hash 算法就是簡單的用 key mod 一下表的大小（也就是數組的長度）
• 最上面的是 old hash 表，其中的 Hash 表的 size = 2，所以 key = 3, 7, 5，在 mod 2 以后都沖突在 table[1] 這里了
• 接下來的三個步驟是 Hash 表 resize 成 4，然后所有的 <key, value> 重新 rehash 的過程

并發(fā)下的 Rehash

1）假設有兩個線程

do {
    Entry<K,V> next = e.next; //  假設線程一執(zhí)行到這里就被調度掛起了
    int i = indexFor(e.hash, newCapacity);
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
} while (e != null);

而線程二執(zhí)行完成了。于是有下面的這個樣子

注意，因為 Thread1 的 e 指向了 key(3)，而 next 指向了 key(7)，其在線程二 rehash 后，指向了線程二重組后的鏈表?？梢钥吹芥湵淼捻樞虮环崔D

2）線程一被調度回來執(zhí)行

• 先是執(zhí)行 newTalbe[i] = e;
• 然后是 e = next，導致了 e 指向了 key(7)
• 而下一次循環(huán)的 next = e.next 導致了 next 指向了 key(3)

3）線程一接著工作。把 key(7) 摘下來，放到 newTable[i] 的第一個，然后把 e 和 next 往下移

4）環(huán)形鏈接出現(xiàn)
e.next = newTable[i] 導致 key(3).next 指向了 key(7)
此時的 key(7).next 已經指向了 key(3)， 環(huán)形鏈表就這樣出現(xiàn)了

JDK 8 的改進

JDK 8 中采用的是位桶 + 鏈表/紅黑樹的方式，當某個位桶的鏈表的長度超過 8 的時候，這個鏈表就將轉換成紅黑樹

HashMap 不會因為多線程 put 導致死循環(huán)（JDK 8 用 head 和 tail 來保證鏈表的順序和之前一樣；JDK 7 rehash 會倒置鏈表元素），但是還會有數據丟失等弊端（并發(fā)本身的問題）。因此多線程情況下還是建議使用 ConcurrentHashMap

為什么線程不安全

HashMap 在并發(fā)時可能出現(xiàn)的問題主要是兩方面：

• 如果多個線程同時使用 put 方法添加元素，而且假設正好存在兩個 put 的 key 發(fā)生了碰撞（根據 hash 值計算的 bucket 一樣），那么根據 HashMap 的實現(xiàn)，這兩個 key 會添加到數組的同一個位置，這樣最終就會發(fā)生其中一個線程 put 的數據被覆蓋

• 如果多個線程同時檢測到元素個數超過數組大小 * loadFactor，這樣就會發(fā)生多個線程同時對 Node 數組進行擴容，都在重新計算元素位置以及復制數據，但是最終只有一個線程擴容后的數組會賦給 table，也就是說其他線程的都會丟失，并且各自線程 put 的數據也丟失