HashMap 基本實現(xiàn)（JDK 8 之前）
HashMap 通常會用一個指針數(shù)組（假設(shè)為 table[]）來做分散所有的 key膘婶，當(dāng)一個 key 被加入時悬襟，會通過 Hash 算法通過 key 算出這個數(shù)組的下標(biāo) i，然后就把這個 <key, value> 插到 table[i] 中脊岳，如果有兩個不同的 key 被算在了同一個 i，那么就叫沖突割捅，又叫碰撞，這樣會在 table[i] 上形成一個鏈表
如果 table[] 的尺寸很小亿驾，比如只有 2 個，如果要放進(jìn) 10 個 keys 的話莫瞬，那么碰撞非常頻繁，于是一個 O(1) 的查找算法乏悄，就變成了鏈表遍歷恳不，性能變成了 O(n)，這是 Hash 表的缺陷
所以烟勋，Hash 表的尺寸和容量非常的重要。一般來說卵惦，Hash 表這個容器當(dāng)有數(shù)據(jù)要插入時，都會檢查容量有沒有超過設(shè)定的 threshold沮尿，如果超過，需要增大 Hash 表的尺寸畜疾，但是這樣一來，整個 Hash 表里的元素都需要被重算一遍啡捶。這叫 rehash，這個成本相當(dāng)?shù)拇?/p>
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 不存在，需要增加一個結(jié)點
addEntry(hash, key, value, i);
return null;
}
檢查容量是否超標(biāo)
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);
//查看當(dāng)前的 size 是否超過了設(shè)定的閾值 threshold墨榄，如果超過，需要 resize
if (size++ >= threshold)
resize(2 * table.length);
}
新建一個更大尺寸的 hash 表渠概，然后把數(shù)據(jù)從老的 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 上的數(shù)據(jù)遷移到 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)的機(jī)制就是將每個鏈表轉(zhuǎn)化到新鏈表贮喧，并且鏈表中的位置發(fā)生反轉(zhuǎn)，而這在多線程情況下是很容易造成鏈表回路箱沦，從而發(fā)生 get() 死循環(huán)。所以只要保證建新鏈時還是按照原來的順序的話就不會產(chǎn)生循環(huán)（JDK 8 的改進(jìn)）
正常的 ReHash 的過程
- 假設(shè)我們的 hash 算法就是簡單的用 key mod 一下表的大形叫巍（也就是數(shù)組的長度）
- 最上面的是 old hash 表，其中的 Hash 表的 size = 2疆前，所以 key = 3, 7, 5，在 mod 2 以后都沖突在 table[1] 這里了
- 接下來的三個步驟是 Hash 表 resize 成 4竹椒，然后所有的 <key, value> 重新 rehash 的過程
并發(fā)下的 Rehash
1）假設(shè)有兩個線程
do {
Entry<K,V> next = e.next; // 假設(shè)線程一執(zhí)行到這里就被調(diào)度掛起了
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 后锨能，指向了線程二重組后的鏈表≈酚觯可以看到鏈表的順序被反轉(zhuǎn)
2）線程一被調(diào)度回來執(zhí)行
- 先是執(zhí)行 newTalbe[i] = e;
- 然后是 e = next，導(dǎo)致了 e 指向了 key(7)
- 而下一次循環(huán)的 next = e.next 導(dǎo)致了 next 指向了 key(3)
3）線程一接著工作傲隶。把 key(7) 摘下來，放到 newTable[i] 的第一個跺株，然后把 e 和 next 往下移
4）環(huán)形鏈接出現(xiàn)
e.next = newTable[i] 導(dǎo)致 key(3).next 指向了 key(7)
此時的 key(7).next 已經(jīng)指向了 key(3)， 環(huán)形鏈表就這樣出現(xiàn)了
JDK 8 的改進(jìn)
JDK 8 中采用的是位桶 + 鏈表/紅黑樹的方式乒省，當(dāng)某個位桶的鏈表的長度超過 8 的時候，這個鏈表就將轉(zhuǎn)換成紅黑樹
HashMap 不會因為多線程 put 導(dǎo)致死循環(huán)（JDK 8 用 head 和 tail 來保證鏈表的順序和之前一樣袖扛；JDK 7 rehash 會倒置鏈表元素）十籍，但是還會有數(shù)據(jù)丟失等弊端（并發(fā)本身的問題）唇礁。因此多線程情況下還是建議使用 ConcurrentHashMap
為什么線程不安全
HashMap 在并發(fā)時可能出現(xiàn)的問題主要是兩方面：
如果多個線程同時使用 put 方法添加元素，而且假設(shè)正好存在兩個 put 的 key 發(fā)生了碰撞（根據(jù) hash 值計算的 bucket 一樣）盏筐，那么根據(jù) HashMap 的實現(xiàn)，這兩個 key 會添加到數(shù)組的同一個位置琢融，這樣最終就會發(fā)生其中一個線程 put 的數(shù)據(jù)被覆蓋
如果多個線程同時檢測到元素個數(shù)超過數(shù)組大小 * loadFactor，這樣就會發(fā)生多個線程同時對 Node 數(shù)組進(jìn)行擴(kuò)容漾抬，都在重新計算元素位置以及復(fù)制數(shù)據(jù)，但是最終只有一個線程擴(kuò)容后的數(shù)組會賦給 table纳令，也就是說其他線程的都會丟失她混，并且各自線程 put 的數(shù)據(jù)也丟失
