1.獲取 index雏门，有關(guān)鍵的以下兩步
參考文檔：https://blog.csdn.net/supercmd/article/details/100042302
1.1 擾動(dòng)函數(shù)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
解讀：
- 為什么要用擾動(dòng)函數(shù)茁影？
答：擾動(dòng)函數(shù)就是解決碰撞問題呼胚。若不使用擾動(dòng)函數(shù)蝇更，則直接將key.hashCode()和下面的步驟2做與運(yùn)算，則會(huì)有以下情景访圃。
以初始長(zhǎng)度16為例况脆，16-1=15。2進(jìn)制表示是00000000 00000000 00001111看铆。和某散列值做“與”操作如下，結(jié)果就是截取了最低的四位值棠隐。
10100101 11000100 00100101
& 00000000 00000000 00001111
------------------------------
00000000 00000000 00000101
這樣就算散列值分布再松散助泽，要是只取最后幾位的話，碰撞也會(huì)很嚴(yán)重。如果散列本身做得不好厢漩，分布上成等差數(shù)列的漏洞溜嗜，恰好使最后幾個(gè)低位呈現(xiàn)規(guī)律性重復(fù)辟躏，則碰撞會(huì)更嚴(yán)重捎琐。
- 擾動(dòng)函數(shù)是怎么實(shí)現(xiàn)的瑞凑？
由擾動(dòng)函數(shù)源碼可知籽御，會(huì)有以下步驟：
①使用key.hashCode()計(jì)算hash值并賦值給變量h铃将；
②將h向右移動(dòng)16位；
③將變量h和向右移16位的h做異或運(yùn)算（二進(jìn)制位相同為0哪工，不同為1）雁比。此時(shí)得到經(jīng)過擾動(dòng)函數(shù)后的hash值偎捎。圖解如下：
h = hashCode(): 1111 1111 1111 1111 1111 0000 1110 1010
-----------------------------------------------------------
h: 1111 1111 1111 1111 1111 0000 1110 1010
h>>>16: 0000 0000 0000 0000 1111 1111 1111 1111
hash = h^(h>>>16): 1111 1111 1111 1111 0000 1111 0001 0101 高16位和低16位 異或運(yùn)算
-----------------------------------------------------------
(n-1)&hash: 0000 0000 0000 0000 0000 0000 0000 1111 與運(yùn)算
1111 1111 1111 1111 0000 1111 0001 0101
-------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 = 5
- 為什么要將key.hashCode()右移16位？
右移16位正好為32bit的一半丈牢，自己的高半?yún)^(qū)和低半?yún)^(qū)做異或己沛，是為了混合原始哈希嗎的高位和低位申尼，來加大低位的隨機(jī)性师幕。而且混合后的低位摻雜了高位的部分特征，使高位的信息也被保留下來
1.2 與運(yùn)算
int index = h & (length - 1)蒙挑； //確定index數(shù)組下標(biāo)
- 為什么要使用與運(yùn)算忆蚀？
若直接使用key.hashCode()計(jì)算出hash值馋袜，則范圍為：-2147483648到2147483648察皇，大約40億的映射空間什荣。若映射得比較均勻，是很難出現(xiàn)碰撞的桅锄。但是這么大范圍無法放入內(nèi)存中，況且HashMap的 初始容量為16檐束。所以必須要進(jìn)行與運(yùn)算取模茶没。
1.3 如何保證HashMap的容量是2的倍數(shù)
/**
* Returns a power of two size for the given target capacity.
* 返回給定目標(biāo)容量大小的2次方。
*/
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;
}
之所以在開始移位前先將容量-1，是為了避免給定容量已經(jīng)是8,16這樣2的冪時(shí)廊移，不減一直接移位會(huì)導(dǎo)致得到的結(jié)果比預(yù)期大狡孔。比如預(yù)期16得到應(yīng)該是16殃恒，直接移位的話會(huì)得到32离唐。
參考文檔：https://www.cnblogs.com/xiyixiaodao/p/14483876.html
2.HashMap底層數(shù)據(jù)結(jié)構(gòu)
- JDK1.8之前的HashMap底層數(shù)據(jù)結(jié)構(gòu)
- 數(shù)組+鏈表
- JDK1.8之后的HashMap底層數(shù)據(jù)結(jié)構(gòu)
- 數(shù)組+鏈表+紅黑樹
- 鏈表長(zhǎng)度>=8 && 數(shù)組長(zhǎng)度>=64 鏈表轉(zhuǎn)化為紅黑樹
- 鏈表長(zhǎng)度>=8 && 數(shù)組長(zhǎng)度< 64 擴(kuò)容完沪，原來數(shù)組長(zhǎng)度*2
- 紅黑樹節(jié)點(diǎn)<=6,自動(dòng)轉(zhuǎn)化為鏈表
HashMap 的長(zhǎng)度為什么是2的冪次方
為了加快哈希計(jì)算以及減少哈希沖突
- 為什么可以加快計(jì)算嵌戈？
我們都知道為了找到 KEY 的位置在哈希表的哪個(gè)槽里面覆积，需要計(jì)算 hash(KEY) % 數(shù)組長(zhǎng)度
但是！% 計(jì)算比 & 慢很多
所以用 & 代替 %熟呛，為了保證 & 的計(jì)算結(jié)果等于 % 的結(jié)果需要把 length 減 1
hash%length==hash&(length-1)的前提是 length 是2的 n 次方
- 為什么可以減少?zèng)_突宽档？
假設(shè)現(xiàn)在數(shù)組的長(zhǎng)度 length 可能是偶數(shù)也可能是奇數(shù)
length 為偶數(shù)時(shí)，length-1 為奇數(shù)惰拱，奇數(shù)的二進(jìn)制最后一位是 1雌贱，這樣便保證了 hash &(length-1) 的最后一位可能為 0欣孤，也可能為 1（這取決于 h 的值），即 & 運(yùn)算后的結(jié)果可能為偶數(shù)段只，也可能為奇數(shù)，這樣便可以保證散列的均勻性。
而如果 length 為奇數(shù)的話，很明顯 length-1 為偶數(shù)，它的最后一位是 0，這樣 hash & (length-1) 的最后一位肯定為 0，即只能為偶數(shù)钾恢，這樣任何 hash 值都只會(huì)被散列到數(shù)組的偶數(shù)下標(biāo)位置上崩哩，這便浪費(fèi)了近一半的空間
因此，length 取 2 的整數(shù)次冪，是為了使不同 hash 值發(fā)生碰撞的概率較小奖年，這樣就能使元素在哈希表中均勻地散列水评。
解釋：
為了能讓 HashMap 存取高效拿霉，盡量較少碰撞偏瓤，也就是要盡量把數(shù)據(jù)分配均勻。我們上面也講到了過了，Hash 值的范圍值-2147483648到2147483647辛藻，前后加起來大概40億的映射空間纺蛆，只要哈希函數(shù)映射得比較均勻松散凤藏，一般應(yīng)用是很難出現(xiàn)碰撞的桨昙。但問題是一個(gè)40億長(zhǎng)度的數(shù)組，內(nèi)存是放不下的。所以這個(gè)散列值是不能直接拿來用的。用之前還要先做對(duì)數(shù)組的長(zhǎng)度取模運(yùn)算，得到的余數(shù)才能用來要存放的位置也就是對(duì)應(yīng)的數(shù)組下標(biāo)市怎。這個(gè)數(shù)組下標(biāo)的計(jì)算方法是“ (n - 1) & hash ”戚篙。（n代表數(shù)組長(zhǎng)度）
HashMap的put方法
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認(rèn) 初始化數(shù)組大小 16
static final int MAXIMUM_CAPACITY = 1 << 30; // 數(shù)組的最大容量 2的30次方
static final float DEFAULT_LOAD_FACTOR = 0.75f; //擴(kuò)容因子痛倚，加載因子 默認(rèn) 0.75
static final int TREEIFY_THRESHOLD = 8; //當(dāng)鏈表長(zhǎng)度>=8朋截，轉(zhuǎn)換為紅黑樹 （還有個(gè)前提，數(shù)組長(zhǎng)度>=64）
static final int UNTREEIFY_THRESHOLD = 6; //當(dāng)紅黑樹長(zhǎng)度 小于該值先巴，自動(dòng)轉(zhuǎn)換為鏈表
static final int MIN_TREEIFY_CAPACITY = 64; //轉(zhuǎn)換為紅黑樹時(shí)其爵，的數(shù)組長(zhǎng)度 要大于該值
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
public V put(K key, V value) {
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;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
}
HashMap 的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;
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
}
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) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
/*
這里如果判斷成立，那么該元素的地址在新的數(shù)組中就不會(huì)改變伸蚯。
因?yàn)閛ldCap的最高位的1摩渺，在e.hash對(duì)應(yīng)的位上為0，所以擴(kuò)容后得到的地址是一樣的剂邮，位置不會(huì)改變 摇幻，在后面的代碼的執(zhí)行中會(huì)放到loHead中去，最后賦值給newTab[j]挥萌；
如果判斷不成立囚企，那么該元素的地址變?yōu)?原下標(biāo)位置+oldCap，也就是lodCap最高位的1瑞眼，在e.hash對(duì)應(yīng)的位置上也為1龙宏，所以擴(kuò)容后的地址改變了，在后面的代碼中會(huì)放到hiHead中伤疙，最后賦值給newTab[j + oldCap]
舉個(gè)例子來說一下上面的兩種情況：
設(shè)：oldCap=16 二進(jìn)制為：0001 0000
oldCap-1=15 二進(jìn)制為：0000 1111
e1.hash=10 二進(jìn)制為：0000 1010
e2.hash=26 二進(jìn)制為：0101 1010
e1在擴(kuò)容前的位置為：e1.hash & oldCap-1 結(jié)果為：0000 1010
e2在擴(kuò)容前的位置為：e2.hash & oldCap-1 結(jié)果為：0000 1010
結(jié)果相同银酗，所以e1和e2在擴(kuò)容前在同一個(gè)鏈表上，這是擴(kuò)容之前的狀態(tài)徒像。
現(xiàn)在擴(kuò)容后黍特，需要重新計(jì)算元素的位置，在擴(kuò)容前的鏈表中計(jì)算地址的方式為e.hash & oldCap-1
那么在擴(kuò)容后應(yīng)該也這么計(jì)算锯蛀，擴(kuò)容后的容量為oldCap*2=32灭衷，2^5, 二進(jìn)制為：0010 0000。 所以 newCap=32旁涤，
新的計(jì)算方式應(yīng)該為
e1.hash & newCap-1
即：0000 1010 & 0001 1111
結(jié)果為0000 1010與擴(kuò)容前的位置完全一樣翔曲。
e2.hash & newCap-1 即：0101 1010 & 0001 1111
結(jié)果為0001 1010,為擴(kuò)容前位置+oldCap。
而這里卻沒有e.hash & newCap-1 而是 e.hash & oldCap劈愚，其實(shí)這兩個(gè)是等效的瞳遍，都是判斷倒數(shù)第五位是0，還是1菌羽。
如果是0掠械，則位置不變育八，是1則位置改變?yōu)閿U(kuò)容前位置+oldCap判呕。
再來分析下loTail, loHead這兩個(gè)的執(zhí)行過程（假設(shè)(e.hash & oldCap) == 0成立）：
第一次執(zhí)行：
e指向oldTab[j]所指向的node對(duì)象财剖，即e指向該位置上鏈表的第一個(gè)元素.
loTail為空,所以loHead指向與e相同的node對(duì)象（loHead = e;）隐孽，然后loTail也指向了同一個(gè)node對(duì)象（loTail = e;）。
最后肚菠，在判斷條件e指向next浸卦，就是指向oldTab鏈表中的第二個(gè)元素
第二次執(zhí)行：
lotail不為null，所以lotail.next指向e案糙，這里其實(shí)是lotail指向的node對(duì)象的next指向e，
也可以說是靴庆，loHead的next指向了e时捌，就是指向了oldTab鏈表中第二個(gè)元素。此時(shí)loHead指向
的node變成了一個(gè)長(zhǎng)度為2的鏈表炉抒。然后lotail=e也就是指向了鏈表中第二個(gè)元素的地址奢讨。
第三次執(zhí)行：
與第二次執(zhí)行類似，loHead上的鏈表長(zhǎng)度變?yōu)?焰薄，又增加了一個(gè)node拿诸，loTail指向新增的node......
hiTail與hiHead的執(zhí)行過程與以上相同。
由此可以看出塞茅，loHead是用來保存新鏈表上的頭元素的亩码，loTail是用來保存尾元素的，直到遍歷完鏈表野瘦。
這是(e.hash & oldCap) == 0成立的時(shí)候描沟。
(e.hash & oldCap) == 0不成立的情況也相同，其實(shí)就是把oldCap遍歷成兩個(gè)新的鏈表鞭光，
通過loHead和hiHead來保存鏈表的頭結(jié)點(diǎn)吏廉，然后將兩個(gè)頭結(jié)點(diǎn)放到newTab[j]與newTab[j+oldCap]上面去。
*/
// 原文鏈接：https://blog.csdn.net/dingjianmin/article/details/109247278
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e; // 相當(dāng)于 loTail指向的Node對(duì)象的next 指向了 e
loTail = e; //loTail 位置移動(dòng)到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;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
HashMap 中的紅黑樹
static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
/**
* Ensures that the given root is the first node of its bin.
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {}
//找出對(duì)應(yīng)的紅黑樹的節(jié)點(diǎn)：查找數(shù)據(jù)
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {}
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
//樹化 Node--》TreeNode
final void treeify(Node<K,V>[] tab) {}
//去樹化 TreeNode--》》Node
final Node<K,V> untreeify(HashMap<K,V> map) {}
//插入數(shù)據(jù)
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {}
//刪除數(shù)據(jù)
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {}
//rehash :擴(kuò)容時(shí)惰许，將舊數(shù)據(jù)rehash席覆，重新確認(rèn)index;將樹分為高區(qū)和低區(qū)兩個(gè)數(shù)
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {}
//左旋
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p){}
//右旋
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p){}
//插入數(shù)據(jù)后，對(duì)紅黑樹結(jié)構(gòu)進(jìn)行自平衡
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x)
//刪除數(shù)據(jù)后汹买，對(duì)紅黑樹結(jié)構(gòu)進(jìn)行自平衡
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x)
//遞歸檢查佩伤，是否符合紅黑樹規(guī)則
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {}
}
參考文檔:https://blog.csdn.net/qq_28063811/article/details/102842862
補(bǔ)充關(guān)于紅黑樹的知識(shí):
參考文檔:http://www.reibang.com/p/e136ec79235c
紅黑樹的特性：
1、每個(gè)節(jié)點(diǎn)要么是紅色晦毙，要么是黑色畦戒，但根節(jié)點(diǎn)永遠(yuǎn)是黑色的；
2结序、每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)一定都是黑色障斋；
3、紅色節(jié)點(diǎn)不能連續(xù)（也即是，紅色節(jié)點(diǎn)的孩子和父親都不能是紅色）垃环；
4邀层、從任一節(jié)點(diǎn)到其子樹中每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)；
5遂庄、所有的葉節(jié)點(diǎn)都是是黑色的（注意這里說葉子節(jié)點(diǎn)其實(shí)是上圖中的 NIL 節(jié)點(diǎn)）寥院；
————————————————
原文鏈接：https://blog.csdn.net/javageektech/article/details/102385013
紅黑樹插入情景:
紅黑樹刪除情景
- 紅黑樹:一種自平衡的二叉查找樹
- 怎么做到自平衡: 左旋,右旋,變色
- 什么情況下需要自平衡操作: 插入和刪除結(jié)點(diǎn)時(shí)
