深度！HashMap的底層數(shù)據(jù)結(jié)構(gòu)
一、HashMap基礎(chǔ)機(jī)構(gòu)
HashMap 由數(shù)組和鏈表（或紅黑樹）組成。數(shù)組是 HashMap 的主體，鏈表和紅黑樹則是為了解決哈希沖突而存在的。數(shù)組中的每個元素都是一個單向鏈表的頭結(jié)點，每個鏈表都是由若干個 Node 節(jié)點組成的，每個節(jié)點都包含了鍵值對的信息，以及指向下一個節(jié)點的指針。當(dāng)多個鍵映射到同一個位置時，它們會被存儲在同一個鏈表中（或者是同一個紅黑樹中）。當(dāng)鏈表長度超過閾值（默認(rèn)為 8）時，鏈表就會被轉(zhuǎn)換成紅黑樹，這樣可以提高查找效率。
在 JDK1.8 中，HashMap 還引入了一個新的概念，叫做負(fù)載因子(load factor)，它是指哈希表中鍵值對的數(shù)量與數(shù)組長度的比值。當(dāng)鍵值對的數(shù)量超過了負(fù)載因子與數(shù)組長度的乘積時，就會觸發(fā)擴(kuò)容操作，HashMap 會自動將數(shù)組長度擴(kuò)大一倍，并將原來的鍵值對重新分配到新的數(shù)組中。這樣做的目的是為了保證散列表的性能，因為當(dāng)負(fù)載因子過高時，散列表的性能會急劇下降。
二、HashMap的底層數(shù)據(jù)結(jié)構(gòu)
解答：在jdk1.8以前，HashMa采用鏈表+數(shù)組，自Jdk1.8以后，HashMap采用鏈表+數(shù)組+紅黑樹。在下圖中橫鏈(0-15)表中表示數(shù)組，豎(1-8)表示鏈表，在數(shù)組長度超過8之后，hashmap將數(shù)組自動轉(zhuǎn)為紅黑樹。
HashMapJDK1.8鏈表和紅黑樹轉(zhuǎn)化
三、JDK1.8對hash算法和尋址算法如何優(yōu)化的？
1、對Hash值算法的優(yōu)化
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位右移后的結(jié)果Hash_2為：
Hash_2: 0000 0000 0000 0000 1111 1111 1111 1111對上述Hash_1和Hash_2的兩個值進(jìn)行異或
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 =====> 轉(zhuǎn)為10進(jìn)制int值，這個值就是這個key的hash值hash算法的優(yōu)化：對每個hash值，在它的低16位中，讓高低16位進(jìn)行異或，讓它的低16位同時保持了高低16位的特征，盡量避免一些hash值后續(xù)出現(xiàn)沖突，大家可能會進(jìn)入數(shù)組的同一位置。
2、對尋址算法的優(yōu)化
(p = tab[i = (n - 1) & hash]
// (n-1) & hash ==> 數(shù)組里的一個位置hash & (n-1) 效果是跟hash對n取模是一樣的，但是與運(yùn)算的性能要比hash對n取模要高很多。數(shù)組的長度會一直是2的n次方，只要他保持?jǐn)?shù)組長度是2的n次方。
- 尋址為什么不用取模？
對于上面尋址算法，由于計算機(jī)對比取模，與運(yùn)算會更快。所以為了效率，HashMap 中規(guī)定了哈希表長度為 2 的 k 次方，而 2^k-1 轉(zhuǎn)為二進(jìn)制就是 k 個連續(xù)的 1，那么 hash & (k 個連續(xù)的 1) 返回的就是 hash 的低 k 個位，該計算結(jié)果范圍剛好就是 0 到 2^k-1，即 0 到 length - 1，跟取模結(jié)果一樣。
也就是說，哈希表長度 length 為 2 的整次冪時， hash & (length - 1) 的計算結(jié)果跟 hash % length 一樣，而且效率還更好。
- 為什么不直接用 hashCode() 而是用它的高 16 位進(jìn)行異或計算新 hash 值？#
int 類型占 32 位，可以表示 2^32 種數(shù)（范圍：-2^31 到 2^31-1），而哈希表長度一般不大，在 HashMap 中哈希表的初始化長度是 16（HashMap 中的 DEFAULT_INITIAL_CAPACITY），如果直接用 hashCode 來尋址，那么相當(dāng)于只有低 4 位有效，其他高位不會有影響。這樣假如幾個 hashCode 分別是 210、220、2^30，那么尋址結(jié)果 index 就會一樣而發(fā)生沖突，所以哈希表就不均勻分布了。
尋址算法的優(yōu)化：用與運(yùn)算替代取模，提升性能。（由于計算機(jī)對比取模，與運(yùn)算會更快）
四、HashMap是如何解決hash碰撞問題
hash沖突問題，鏈表+紅黑樹，O(n)和O(logN)。
hashmap采用的就是鏈地址法（拉鏈法），jdk1.7中，當(dāng)沖突時，在沖突的地址上生成一個鏈表，將沖突的元素的key，通過equals進(jìn)行比較，相同即覆蓋，不同則添加到鏈表上，此時如果鏈表過長，效率就會大大降低，查找和添加操作的時間復(fù)雜度都為O(n)；但是在jdk1.8中如果鏈表長度大于8，鏈表就會轉(zhuǎn)化為紅黑樹，時間復(fù)雜度也降為了O(logn)，性能得到了很大的優(yōu)化。
HashMapJDK1.8鏈表和紅黑樹轉(zhuǎn)化
五、HashMap是如何進(jìn)行擴(kuò)容的
HashMap底層是一個數(shù)組，當(dāng)這個數(shù)組滿了之后，他就會自動進(jìn)行擴(kuò)容，變成一個更大數(shù)組。
1、JDK1.7下的擴(kuò)容機(jī)制
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長度已經(jīng)達(dá)到了上限，就不再擴(kuò)容了。如果還未達(dá)到上限，則創(chuàng)建一個新的table，并調(diào)用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線程不安全的情況下，這種頭插法可能會導(dǎo)致環(huán)狀節(jié)點。
2、JDK1.8下的擴(kuò)容機(jī)制
源碼如下：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 記錄原來的數(shù)組長度
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值在新表對應(yīng)的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) // 如果已經(jīng)是紅黑樹的節(jié)點，那就對其重新劃分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// loHead: 下標(biāo)不變情況下的鏈表頭
// loTail: 下標(biāo)不變情況下的鏈表尾
// hiHead: 下標(biāo)改變情況下的鏈表頭
// hiTail: 下標(biāo)改變情況下的鏈表尾
// 如果
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 {
// 與運(yùn)算不等于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;
}正常情況下，計算節(jié)點在table中的下標(biāo)的方法是：hash&(oldTable.length-1)，擴(kuò)容之后，table長度翻倍，計算table下標(biāo)的方法是hash&(newTable.length-1)，也就是hash&(oldTable.length*2-1)，于是我們有了這樣的結(jié)論：這新舊兩次計算下標(biāo)的結(jié)果，要不然就相同，要不然就是新下標(biāo)等于舊下標(biāo)加上舊數(shù)組的長度。
數(shù)組長度為16時，有兩個keyA和keyB。
KeyA：
n-1: 0000 0000 0000 0000 0000 0000 0000 1111
hash1: 1111 1111 1111 1111 0000 1111 0000 0101
&結(jié)果: 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
&結(jié)果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5在數(shù)組長度為16的時候，他們兩個hash值沖突會使用拉鏈發(fā)解決沖突。
當(dāng)數(shù)組長度擴(kuò)容到32之后，需要重新對每個hash值進(jìn)行尋址，也就是每個hash值跟新的數(shù)組length-1 進(jìn)行操作。
KeyA：
n-1: 0000 0000 0000 0000 0000 0000 000*1* 1111
hash1: 1111 1111 1111 1111 0000 1111 0000 0101
&結(jié)果: 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
&結(jié)果: 0000 0000 0000 0000 0000 000*1* 0000 0101 = 21判斷二進(jìn)制結(jié)果是否多出一個bit的1，如果沒有多，那就用原來的index，如果多出來了那就用index+oldCap，通過這個方式，避免了rehash的時候，用每個hash對新數(shù)組的length取模，取模性能不高，位運(yùn)算性能比較高。
