1 Hash算法
哈希函數(shù)的目標(biāo)是計算key在數(shù)組中的下標(biāo)聋袋。判斷一個哈希函數(shù)的標(biāo)準(zhǔn)是：散列是否均勻、計算是否簡單贷币。
HashMap哈希函數(shù)的步驟：
對key對象的hashcode進行擾動
通過取模求得數(shù)組下標(biāo)
擾動是為了讓hashcode的隨機性更高掠廓，第二步取模就不會讓所以的key都聚集在一起，提高散列均勻度苔严。
static final int hash(Object key) {
int h;
// 獲取到key的hashcode定枷，在高低位異或運算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
也就是低16位是和高16位進行異或，高16位保持不變届氢。一般的數(shù)組長度都會比較短欠窒，取模運算中只有低位參與散列；高位與低位進行異或退子，讓高位也得以參與散列運算岖妄，使得散列更加均勻。
2 HashMap的數(shù)組長度
HashMap的默認(rèn)數(shù)組長度的16寂祥，如果給于了初始長度荐虐，那么將計算出大于等于當(dāng)前給定數(shù)組長度的最小2的冪次方的數(shù)，如果給定的數(shù)組長度超過MAXIMUM_CAPAC丸凭，則用MAXIMUM_CAPAC作為數(shù)組長度福扬。
//創(chuàng)建 HashMap 時未指定初始容量情況下的默認(rèn)容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//HashMap 的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
規(guī)格化數(shù)組長度
static final int tableSizeFor(int cap) {
// 注意這里必須減一
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
當(dāng)給定初始長度時，會調(diào)用如上方法將HashMap的數(shù)組長度設(shè)置為2的冪次方惜犀。上面一連串的位移操作是為了把n的最高位1后面的位都變成1铛碑。這樣就是得到一尾數(shù)連續(xù)為1的數(shù)，通過n+1操作就得到一個2的冪次方的數(shù)虽界。
注意：
n=cap-1是為了當(dāng)給的初始長度是2的冪次方時汽烦，讓結(jié)果等于當(dāng)前給定的初始長度。
3 HashMap定位
HashMap控制數(shù)組長度為2的整數(shù)次冪莉御，好處是對hashcode進行求余運算和讓hashcode與數(shù)組長度-1進行位與運算是相同的效果撇吞。能夠快速定位Key所在的數(shù)組的位置俗冻，HashMap通過如下方法快速定位。
4 Hash擴容
HashMap每次擴容都使當(dāng)前數(shù)組長度變成原數(shù)組長度的2倍（除最大容量外）梢夯。
如上（a）為原數(shù)組長度言疗，（b）為擴容后的數(shù)組長度，可以看出颂砸，當(dāng)擴容后數(shù)組原位置上的Key將落在新數(shù)組的原位置或原位置+原數(shù)組長度噪奄。所有擴容后數(shù)據(jù)的遷移就變得很高效了，只需要判斷Key的Hash&原數(shù)組長度n就知道Key在擴容后的位置人乓。
5 HashMap數(shù)據(jù)結(jié)構(gòu)
//HashMap 默認(rèn)的裝載因子,當(dāng) HashMap 中元素數(shù)量超過 容量*裝載因子 時勤篮，進行 resize() 操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//用來確定何時將解決 hash 沖突的鏈表轉(zhuǎn)變?yōu)榧t黑樹
static final int TREEIFY_THRESHOLD = 8;
// 用來確定何時將解決 hash 沖突的紅黑樹轉(zhuǎn)變?yōu)殒湵? static final int UNTREEIFY_THRESHOLD = 6;
/* 當(dāng)需要將解決 hash 沖突的鏈表轉(zhuǎn)變?yōu)榧t黑樹時，需要判斷下此時數(shù)組容量色罚，若是由于數(shù)組容量太信龅蕖（小于 MIN_TREEIFY_CAPACITY ）導(dǎo)致的 hash沖突太多戳护，則不進行鏈表轉(zhuǎn)變?yōu)榧t黑樹操作金抡，轉(zhuǎn)為利用 resize() 函數(shù)對 hashMap 擴容 */
static final int MIN_TREEIFY_CAPACITY = 64;
HashMap的裝載因子默認(rèn)為0.75，是為了權(quán)衡效率和空間腌且。當(dāng)裝載因子越小時梗肝，Hash沖突就越小，但占用空間就越大铺董。
JDK1.8HashMap引入了紅黑樹結(jié)構(gòu)巫击，當(dāng)鏈表長度過長時，將鏈表轉(zhuǎn)換為紅黑樹精续，提高鏈表查詢效率坝锰。當(dāng)鏈表長度大于等于8時，會把鏈表轉(zhuǎn)換為紅黑樹重付。當(dāng)鏈表長度等于小于等于6時，會把紅黑樹轉(zhuǎn)換成鏈表确垫。
為什么在8和6的時候轉(zhuǎn)換？
因為當(dāng)負(fù)載因子是0.75時森爽，泊松分布中鏈表長度為8的概率已經(jīng)很小了嚣镜，為什么在6的時候轉(zhuǎn)換為鏈表，一是因為6和8的概率相差較大菊匿，二是防止在8的時候?qū)ν粋€元素平凡的添加和刪除计福，導(dǎo)致鏈表在長度在8與7之間平凡轉(zhuǎn)換導(dǎo)致效率低下。
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
鏈表轉(zhuǎn)換成紅黑樹還有一個限制條件：
當(dāng)鏈表要轉(zhuǎn)換為紅黑樹時徽职，首先要判斷當(dāng)前數(shù)組長度是否大于64象颖，如果小于，就進行擴容姆钉。
為什么做這一個判讀说订，是因為，數(shù)組長度較小時潮瓶，如果鏈表長度能達(dá)到8陶冷，那么離數(shù)組擴容也不遠(yuǎn)了，所有先擴容毯辅，防止轉(zhuǎn)換后在擴容埂伦，導(dǎo)致效率低下。
5.1Node節(jié)點
// Node<K,V> 類用來實現(xiàn)數(shù)組及鏈表的數(shù)據(jù)結(jié)構(gòu)
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //保存節(jié)點的 hash 值
final K key; //保存節(jié)點的 key 值
V value; //保存節(jié)點的 value 值
Node<K,V> next; //指向鏈表結(jié)構(gòu)下的當(dāng)前節(jié)點的 next 節(jié)點思恐，紅黑樹 TreeNode 節(jié)點中也有用到
}
// TreeNode<K,V> 繼承 LinkedHashMap.Entry<K,V>沾谜，用來實現(xiàn)紅黑樹相關(guān)的存儲結(jié)構(gòu)
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 存儲當(dāng)前節(jié)點的父節(jié)點
TreeNode<K,V> left; //存儲當(dāng)前節(jié)點的左孩子
TreeNode<K,V> right; //存儲當(dāng)前節(jié)點的右孩子
TreeNode<K,V> prev; // 存儲當(dāng)前節(jié)點的前一個節(jié)點
boolean red; // 存儲當(dāng)前節(jié)點的顏色（紅、黑）
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
注意：
TreeNode還有prev胀莹，next兩個引用基跑，保留了雙向鏈表的特性，在數(shù)組擴容時嗜逻，方便紅黑樹的遍歷涩僻。
5.2 put方法
//指定節(jié)點 key,value，向 hashMap 中插入節(jié)點
public V put(K key, V value) {
//注意待插入節(jié)點 hash 值的計算栈顷，調(diào)用了 hash(key) 函數(shù)
//實際調(diào)用 putVal（）進行節(jié)點的插入
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/*根據(jù) hash 值確定節(jié)點在數(shù)組中的插入位置逆日，若此位置沒有元素則進行插入，注意確定插入位置所用的計算方法為 (n - 1) & hash,由于 n 一定是２的冪次萄凤，這個操作相當(dāng)于
hash % n */
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//說明待插入位置存在元素
Node<K,V> e; K k;
//比較原來元素與待插入元素的 hash 值和 key 值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//若原來元素是紅黑樹節(jié)點室抽，調(diào)用紅黑樹的插入方法:putTreeVal
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//證明原來的元素是鏈表的頭結(jié)點，從此節(jié)點開始向后尋找合適插入位置
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//找到插入位置后靡努，新建節(jié)點插入
p.next = newNode(hash, key, value, null);
//若鏈表上節(jié)點超過TREEIFY_THRESHOLD - 1坪圾，將鏈表變?yōu)榧t黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}//end else
if (e != null) { // 待插入元素在 hashMap 中已存在
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}//end else
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}//end putval
插入流程：
如果數(shù)組沒有初始化就是初始化數(shù)組
定位數(shù)組中的位置，如果當(dāng)前位置沒有數(shù)據(jù)惑朦，就直接插入兽泄。
-
當(dāng)前位置存在數(shù)據(jù)
如果是TreeNode直接插入
如果是Node，判斷是否存在當(dāng)前Key漾月，如果存在則替換值病梢，否則插入鏈表的尾部，然后判斷是否需要轉(zhuǎn)換成紅黑樹。
判斷數(shù)組是否需要擴容蜓陌。
注意：
JDK1.7使用頭插觅彰，雖然效率高，但是在多線程下擴容會形成環(huán)钮热。JDK1.8使用尾插填抬，然后可以避免多線程形成環(huán)，但是數(shù)據(jù)會丟失隧期，使用尾插是為了統(tǒng)計鏈表長度，判斷是否需要轉(zhuǎn)換為紅黑樹读拆。
5.3 resize方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
/*
1鸵闪、resize（）函數(shù)在size > threshold時被調(diào)用蚌讼。
oldCap大于 0 代表原來的 table 表非空， oldCap 為原表的大小篡石，
oldThr（threshold） 為 oldCap × load_factor
*/
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
}
/*
2凰萨、resize（）函數(shù)在table為空被調(diào)用胖眷。
oldCap 小于等于 0 且 oldThr 大于0，代表用戶創(chuàng)建了一個 HashMap珊搀，但是使用的構(gòu)造函數(shù)為
HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)
或 HashMap(Map<? extends K, ? extends V> m)境析，導(dǎo)致 oldTab 為 null，oldCap 為0劳淆，
oldThr 為用戶指定的 HashMap的初始容量沛鸵。
*/
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
/*
3、resize（）函數(shù)在table為空被調(diào)用朝刊。
oldCap 小于等于 0 且 oldThr 等于0拾氓，用戶調(diào)用 HashMap()構(gòu)造函數(shù)創(chuàng)建的 HashMap底哥，所有值均采用默認(rèn)值趾徽，
oldTab（Table）表為空，oldCap為0疲酌，oldThr等于0了袁，
*/
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;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//把 oldTab 中的節(jié)點 reHash 到 newTab 中去
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//若節(jié)點是單個節(jié)點载绿，直接在 newTab 中進行重定位
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//若節(jié)點是 TreeNode 節(jié)點崭庸，要進行 紅黑樹的 rehash 操作
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//若是鏈表，進行鏈表的 rehash 操作
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//根據(jù)算法 e.hash & oldCap 判斷節(jié)點位置 rehash 后是否發(fā)生改變
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
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;
// rehash 后節(jié)點新的位置一定為原來基礎(chǔ)上加上 oldCap
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
擴容流程：
-
首先確定新數(shù)組的大小
如果數(shù)組長度大于等于最大容量就不擴容
如果擴容后的數(shù)組大于等于最大容量，就讓擴容后的數(shù)組長度設(shè)置為最大容量熬粗。
否則就是原來容量的2倍（這里沒有解析初始化數(shù)組驻呐，數(shù)組初始化也會擴容）
-
創(chuàng)建新的數(shù)組，遍歷的就的數(shù)據(jù)進行數(shù)組遷移
當(dāng)前位置是TreeNode含末，則調(diào)用TreeNode的split方法
當(dāng)前位置是Node佣盒，遍歷鏈表，將鏈表放置在新數(shù)組的當(dāng)前位置或者紊搪，當(dāng)前位置+原數(shù)組長度的位置全景。
5.4 split方法
//這個函數(shù)的功能是對紅黑樹進行 rehash 操作
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
//由于 TreeNode 節(jié)點之間存在雙端鏈表的關(guān)系，可以利用鏈表關(guān)系進行 rehash
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
//rehash 操作之后注意對根據(jù)鏈表長度進行 untreeify 或 treeify 操作
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}//end if
}//end split
注意：
由于TreeNode維持了雙向鏈表的特征，所以數(shù)據(jù)遷移和單鏈表一樣炕贵，將數(shù)據(jù)遷移到新數(shù)組的當(dāng)前位置或這當(dāng)前位置+原數(shù)組長度的位置称开。最后判斷新鏈表長度，如果大于等于8則轉(zhuǎn)換成紅黑樹钥弯，如果小于等于6轉(zhuǎn)換成鏈表脆霎。當(dāng)HashMap在刪除節(jié)點時总处，不會判斷長度睛蛛，也不會將紅黑樹轉(zhuǎn)換為鏈表。
