HashMap實現原理
基本組成
HashMap由Entry數組組成，Entry下是鏈表（JDK1.8變成紅黑樹）。
HashMap是基於hashing的原理，當我們給put方法傳遞鍵和值時，我們先對鍵調用hashCode()方法，返回hashCode用於找到bucket位置來存儲Entry對象。
如果HashMap的大小超過了負載因子（load factor）定義的容量，怎麼辦？
默認個的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時，和其他集合類（如ArrayList等）一樣，將會創建原來的HashMap大小的兩倍的bucket數組，來重新調整map的大小，並將原來的對象放入新的bucket數組中，這個過程叫rehashing，因為它調用hash方法找到新的bucket位置。
put過程
1、先判斷key是不是為空，為空做插入操作；
2、對key做hash操作，更具hash結果定位數組下標，判斷該下標的entry是否存在，如果存在，遍歷鏈表查找key值相同的entry，並更新其value值，並返回舊值；如果不存在，執行第三步新增entry操作；
3、新增時，判斷數據（已插入entry的數量）長度是否大於等於12=16*0.75，如果是則執行resize操作；
if ((size >= threshold) && (null != table[bucketIndex]) {
resize(2 * table.length);
}
創建entry，插入鏈頭
你瞭解重新調整HashMap大小存在什麼問題嗎？
當重新調整HashMap大小的時候，確實存在條件競爭，因為如果2個線程都發現HashMap需要重新調整大小了，他們會同時試著調整大小。
在調整大小的過程中，存儲在鏈表中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap並不會將元素放在鏈表的尾部，而是放在頭部，這是為了避免尾部遍歷（tail traversing）。
如果條件競爭發生了，那麼就死循環了。（同時調整大小導致鏈環）
我們看下過程：
Entry的結構為：
transient Entry<K, V> table = (Entry<K, V)[]) EMPTY_TABLE;
static class Entry<K, V> implements Map.Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
int hash;
}
resize過程：
當（size >= threshold）才resize，其中
threshold = 16 * 0.75 = 12時resize
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void transfer(Entry[] newTable) {
int newCapacity = newTable.length;
for (Entry(K, V) e : table) {
while( null != e) {
Entry<K, V> next = e.next; //第一個線程執行到停止，第二個線程執行完後，第一個線程接著執行
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
並發執行時，從entry頭開始拷貝時
原：entry head 3->7 tail
新：entry head 7->3 tail
推薦閱讀：