HashMap
HashMap原理？
Hash是一個用于存儲key-value鍵值對的集合，每個鍵值對也叫Entry，這些Entry分散存儲在一個數(shù)組當中，每個元素初始值都是Null，常用方法有put,get
put原理？
put(1,"A")
1）計算數(shù)組下標index=Hash(1)=hashcode(1)&(capacity-1)
2）插入數(shù)組talbe[index].value="A"
3）如果table[index]這個位置已經(jīng)有值了，用鏈表來解決(Java8改用紅黑樹實現(xiàn)了)
table[index]->next.value="A"
get原理？
get(1, "A")
1）計算數(shù)組下標index=Hash(1)
2）從數(shù)組中獲取數(shù)據(jù)table[index]
3）如果這個index存在沖突，需要遍歷該處鏈表，比對key
HashMap初始長度？
默認初始長度是16，每次自動擴展或是手動初始化時必須是2的冪。為什么呢？
根據(jù)key計算數(shù)組下標用到一個Hash函數(shù)，要保證通過Hash函數(shù)得到的數(shù)組下標均勻分布，這樣HashMap在put,get時才會更高效。計算數(shù)組下標的公式是：
index = hashcode(key) & (capacity-1)
# capacity是hashmap中數(shù)組的長度，假設使用默認長度
key hashcode(key) capacity-1 index
1 49(0011 0001) 1111 1
a 97(110 0001) 1111 1
book 3029737(00101110001110101110 1001) 1111 9
apple 93029210(010110001011100000110101 1010) 1111 10
# 保證HashMap數(shù)組長度是2的冪可保證capacity-1的二進制全是1，
# 如果hash函數(shù)是均勻的話，得到的index也是均勻的
如何擴容？
1）判斷是否擴容
# 滿足下列條件就需要擴容了
HashMap.Size >= Capacity * LoadFactor
# HashMap.Size表示HashMap中含有的元素個數(shù)
# Capacity表示HashMap中數(shù)組的長度
# LoadFactor表示負載因子，默認值為0.75f
2）Resize
創(chuàng)建一個空數(shù)組，長度為原數(shù)組的2倍。
Capacity = 2 * Capaicty
3）Rehash
數(shù)組長度變了，所以每個元素的數(shù)組下標也有可能會變，所以需要重新計算并添加到新的數(shù)組中。
非線程安全
并發(fā)下的Rehash可能產(chǎn)生條件競爭導致環(huán)形鏈接。具體分析看參考鏈接。
看參考文章中的分析能說出來，但是自己寫還是寫不出來。
與Java8的HashMap有什么不同
存在哈希沖突的情況，比如兩個哈希值取模后落在同一個index，或者兩條不同的key有相同的哈希值。
JDK7的做法是建一條鏈表，后插入的元素在上面，一個個地執(zhí)行上面的判斷。
而JDK8則在鏈表長度達到8，而且桶數(shù)量達到64時，建一棵紅黑樹，解決嚴重沖突時的性能問題。
參考
疫苗：JAVA HASHMAP的死循環(huán) - 酷殼
HashMap完全解讀-HollisChuang's Blog
