HashMap實現(xiàn)原理
基本組成
HashMap 由Entry數(shù)組組成，Entry下是鏈表（jdk1.8變成紅黑樹）。
HashMap是基于hashing的原理蓖谢，當(dāng)我們給put()方法傳遞鍵和值時珍语，我們先對鍵調(diào)用hashCode()方法，返回的hashCode用于找到bucket位置來儲存Entry對象擦秽。
如果HashMap的大小超過了負(fù)載因子(load factor)定義的容量，怎么辦漩勤？
默認(rèn)的負(fù)載因子大小為0.75感挥，也就是說，當(dāng)一個map填滿了75%的bucket時候越败，和其它集合類(如ArrayList等)一樣触幼，將會創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組，來重新調(diào)整map的大小究飞，并將原來的對象放入新的bucket數(shù)組中置谦。這個過程叫作rehashing堂鲤，因為它調(diào)用hash方法找到新的bucket位置。
put過程：
- 先判斷key是不是為空媒峡，為空做插入操作瘟栖；
- 對key做hash操作，跟據(jù)hash結(jié)果定位數(shù)組下標(biāo)谅阿，判斷該下標(biāo)的entry是否存在半哟，如果存在，遍歷鏈表查找key值相同的entry签餐，并更新其value值镜沽，并返回舊值;如果不存在執(zhí)行第3步新增entry操作；
- 新增時贱田，判斷數(shù)據(jù)（已插入entry的數(shù)量）長度是否大于等于12=16*0.75缅茉，如果是則resize操作婚瓜。
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
}
創(chuàng)建entry票灰，插入鏈頭
你了解重新調(diào)整HashMap大小存在什么問題嗎？
當(dāng)重新調(diào)整HashMap大小的時候佑淀，確實存在條件競爭耗拓，因為如果兩個線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了拇颅，它們會同時試著調(diào)整大小。
在調(diào)整大小的過程中乔询，存儲在鏈表中的元素的次序會反過來樟插，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部竿刁，而是放在頭部黄锤，這是為了避免尾部遍歷(tail traversing)。
如果條件競爭發(fā)生了食拜，那么就死循環(huán)了鸵熟。(同時調(diào)整理大小導(dǎo)致鏈環(huán)）
我們看下過程：
Entry的結(jié)構(gòu)為：
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過程：
當(dāng) ((size >= threshold) 才resize
其中
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
即：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;//第一個線程執(zhí)行到停止，第二個線程執(zhí)行完后负甸，第一個線程接著執(zhí)行
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];//此處理發(fā)生循環(huán)：原table為3->7 ,e=3 當(dāng)?shù)诙€線程執(zhí)行完后流强，newTable[i]=7->3 第一個線程執(zhí)行此行時， 3 ->（7->3) 此時產(chǎn)生環(huán)
newTable[i] = e;
e = next;
}
}
}
并發(fā)執(zhí)行時呻待，從entry頭開始拷貝時
原：entry head 3 ->7 tail
新：entry head 7 ->3 tail
