深度！HashMap的底層數據結構
一、HashMap基礎機構
HashMap 由數組和鏈表（或紅黑樹）組成。數組是 HashMap 的主體，鏈表和紅黑樹則是為了解決哈希沖突而存在的。數組中的每個元素都是一個單向鏈表的頭結點，每個鏈表都是由若干個 Node 節點組成的，每個節點都包含了鍵值對的信息，以及指向下一個節點的指針。當多個鍵映射到同一個位置時，它們會被存儲在同一個鏈表中（或者是同一個紅黑樹中）。當鏈表長度超過閾值（默認為 8）時，鏈表就會被轉換成紅黑樹，這樣可以提高查找效率。
在 JDK1.8 中，HashMap 還引入了一個新的概念，叫做負載因子(load factor)，它是指哈希表中鍵值對的數量與數組長度的比值。當鍵值對的數量超過了負載因子與數組長度的乘積時，就會觸發擴容操作，HashMap 會自動將數組長度擴大一倍，并將原來的鍵值對重新分配到新的數組中。這樣做的目的是為了保證散列表的性能，因為當負載因子過高時，散列表的性能會急劇下降。
二、HashMap的底層數據結構
解答：在jdk1.8以前，HashMa采用鏈表+數組，自Jdk1.8以后，HashMap采用鏈表+數組+紅黑樹。在下圖中橫鏈(0-15)表中表示數組，豎(1-8)表示鏈表，在數組長度超過8之后，hashmap將數組自動轉為紅黑樹。
HashMapJDK1.8鏈表和紅黑樹轉化
三、JDK1.8對hash算法和尋址算法如何優化的？
1、對Hash值算法的優化
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}有一個key的Hash_1值：
Hash_1: 1111 1111 1111 1111 1111 1010 0111 1100h >>> 16 // 表示對該hash值右移16位右移后的結果Hash_2為：
Hash_2: 0000 0000 0000 0000 1111 1111 1111 1111對上述Hash_1和Hash_2的兩個值進行異或
Hash_1: 1111 1111 1111 1111 1111 1010 0111 1100
Hash_2: 0000 0000 0000 0000 1111 1111 1111 1111
=====>: 1111 1111 1111 1111 0000 0101 1000 0011 =====> 轉為10進制int值，這個值就是這個key的hash值hash算法的優化：對每個hash值，在它的低16位中，讓高低16位進行異或，讓它的低16位同時保持了高低16位的特征，盡量避免一些hash值后續出現沖突，大家可能會進入數組的同一位置。
2、對尋址算法的優化
(p = tab[i = (n - 1) & hash]
// (n-1) & hash ==> 數組里的一個位置hash & (n-1) 效果是跟hash對n取模是一樣的，但是與運算的性能要比hash對n取模要高很多。數組的長度會一直是2的n次方，只要他保持數組長度是2的n次方。
- 尋址為什么不用取模？
對于上面尋址算法，由于計算機對比取模，與運算會更快。所以為了效率，HashMap 中規定了哈希表長度為 2 的 k 次方，而 2^k-1 轉為二進制就是 k 個連續的 1，那么 hash & (k 個連續的 1) 返回的就是 hash 的低 k 個位，該計算結果范圍剛好就是 0 到 2^k-1，即 0 到 length - 1，跟取模結果一樣。
也就是說，哈希表長度 length 為 2 的整次冪時， hash & (length - 1) 的計算結果跟 hash % length 一樣，而且效率還更好。
- 為什么不直接用 hashCode() 而是用它的高 16 位進行異或計算新 hash 值？#
int 類型占 32 位，可以表示 2^32 種數（范圍：-2^31 到 2^31-1），而哈希表長度一般不大，在 HashMap 中哈希表的初始化長度是 16（HashMap 中的 DEFAULT_INITIAL_CAPACITY），如果直接用 hashCode 來尋址，那么相當于只有低 4 位有效，其他高位不會有影響。這樣假如幾個 hashCode 分別是 210、220、2^30，那么尋址結果 index 就會一樣而發生沖突，所以哈希表就不均勻分布了。
尋址算法的優化：用與運算替代取模，提升性能。（由于計算機對比取模，與運算會更快）
四、HashMap是如何解決hash碰撞問題
hash沖突問題，鏈表+紅黑樹，O(n)和O(logN)。
hashmap采用的就是鏈地址法（拉鏈法），jdk1.7中，當沖突時，在沖突的地址上生成一個鏈表，將沖突的元素的key，通過equals進行比較，相同即覆蓋，不同則添加到鏈表上，此時如果鏈表過長，效率就會大大降低，查找和添加操作的時間復雜度都為O(n)；但是在jdk1.8中如果鏈表長度大于8，鏈表就會轉化為紅黑樹，時間復雜度也降為了O(logn)，性能得到了很大的優化。
HashMapJDK1.8鏈表和紅黑樹轉化
五、HashMap是如何進行擴容的
HashMap底層是一個數組，當這個數組滿了之后，他就會自動進行擴容，變成一個更大數組。
1、JDK1.7下的擴容機制
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}代碼中可以看到，如果原有table長度已經達到了上限，就不再擴容了。如果還未達到上限，則創建一個新的table，并調用transfer方法：
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next; //注釋1
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity); //注釋2
e.next = newTable[i]; //注釋3
newTable[i] = e; //注釋4
e = next; //注釋5
}
}
}transfer方法的作用是把原table的Node放到新的table中，使用的是頭插法，也就是說，新table中鏈表的順序和舊列表中是相反的，在HashMap線程不安全的情況下，這種頭插法可能會導致環狀節點。
2、JDK1.8下的擴容機制
源碼如下：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 記錄原來的數組長度
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold // 重新計算TREEIFY_THRESHOLD
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) { // 重新計算原來鏈表中的值的hash值在新表對應的hash值
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) // 如果元素e的下一個位置沒有值，則說明可以存放元素
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) // 如果已經是紅黑樹的節點，那就對其重新劃分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// loHead: 下標不變情況下的鏈表頭
// loTail: 下標不變情況下的鏈表尾
// hiHead: 下標改變情況下的鏈表頭
// hiTail: 下標改變情況下的鏈表尾
// 如果
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // 元素e的最新hash如果與原來的值與計算之后如果值為0，就說明是使用原來的index
// 尾插法插入元素e
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
// 與運算不等于0則說明使用新的index
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}正常情況下，計算節點在table中的下標的方法是：hash&(oldTable.length-1)，擴容之后，table長度翻倍，計算table下標的方法是hash&(newTable.length-1)，也就是hash&(oldTable.length*2-1)，于是我們有了這樣的結論：這新舊兩次計算下標的結果，要不然就相同，要不然就是新下標等于舊下標加上舊數組的長度。
數組長度為16時，有兩個keyA和keyB。
KeyA：
n-1: 0000 0000 0000 0000 0000 0000 0000 1111
hash1: 1111 1111 1111 1111 0000 1111 0000 0101
&結果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5
KeyB:
n-1: 0000 0000 0000 0000 0000 0000 0000 1111
hash1: 1111 1111 1111 1111 0000 1111 0001 0101
&結果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5在數組長度為16的時候，他們兩個hash值沖突會使用拉鏈發解決沖突。
當數組長度擴容到32之后，需要重新對每個hash值進行尋址，也就是每個hash值跟新的數組length-1 進行操作。
KeyA：
n-1: 0000 0000 0000 0000 0000 0000 000*1* 1111
hash1: 1111 1111 1111 1111 0000 1111 0000 0101
&結果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5
KeyB:
n-1: 0000 0000 0000 0000 0000 000*1* 0000 1111
hash1: 1111 1111 1111 1111 0000 1111 0001 0101
&結果: 0000 0000 0000 0000 0000 000*1* 0000 0101 = 21判斷二進制結果是否多出一個bit的1，如果沒有多，那就用原來的index，如果多出來了那就用index+oldCap，通過這個方式，避免了rehash的時候，用每個hash對新數組的length取模，取模性能不高，位運算性能比較高。
