大綱
- 前言
- HashMap解決了什么問題
- 查詢速率不高的問題
- 哈希沖突
- 自動擴容
- 從put()方法開始了解原始碼
- resize()實作擴容的關鍵
- (e.hash & oldCap) == 0 到底是什么？
- split()擴容時對紅黑樹的處理
- 關于紅黑樹的最少必要知識
- 紅黑樹插入后保持平衡
- treeify()建立紅黑樹(基于雙鏈生成紅黑樹)
- untreeify()把雙鏈變單鏈
- balanceInsertion()確保插入后的平衡性
- putTreeVal()往紅黑樹里插入資料
- 總結
- 為什么HashMap的容量一定是2的冪次
- 為什么負載因子是0.75
前言
HashMap底層是使用陣列來實作哈希表的，之所以哈希表存盤和查詢快，是因為往哈希表里面放東西的時候，會先通過key算出一個哈希值(hash)，然后利用這個hash值來與哈希表的容量進行取余運算（取余和取模是由區別的），然后就得到了準確的陣列下標，然后就可以快速地進行插入操作；同理查詢也一樣，通過準確的陣列下標就可以快速得到結果，
HashMap解決了什么問題
查詢速率不高的問題
因為HashMap是基于陣列的，而陣列查詢速率是很高的，因為：
- 每一個元素的記憶體地址在空間中是連續的
- 每一個元素型別一樣，所以占有空間大小一樣
- 知道第一個元素的記憶體地址，知道了每一個元素的空間大小，又知道了要查的那一個元素的下標，所以通過數學運算式就可以計算出那個元素的準確記憶體地址，從而直接通過記憶體地址來定位那個元素，所以陣列的查詢效率是最高的，
哈希沖突
所謂的哈希沖突就是在插入元素的時候，通過計算得到的陣列下標上已經存在元素（一個或多個）了，并且這個元素的key與要插入元素的key值不一樣**（通過hash和equal()來判斷）**，但又不能把原先那個元素的value給覆寫掉，所以就發生了沖突，HashMap解決這個沖突是同過鏈表和紅黑樹來解決的，如果不懂什么是紅黑樹也沒關系，等下原始碼分析的時候會順帶講到，現在只要知道它是一個平衡二叉樹，并且效率要比AVL樹要高就行了，
自動擴容
因為HashMap是基于陣列來實作的，但雖然陣列查詢效率高，但它的長度是固定的，所以如果存的元素多了，很容易造成哈希沖突，達不到一個很好的散列效果，所以必須要對陣列進行擴容，所以HashMap里面就會涉及到陣列的自動擴容，
從put()方法開始了解原始碼
二話不說，學習原始碼之前先放一張UML圖，來明確HashMap的繼承關系
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-kQOLtjC7-1635150735122)(HashMap原始碼詳解.assets/image-20211024143751356.png)]
首先撰寫一段簡單的代碼，往HashMap里面放元素
public static void main(String[] args) {
Map<String,String> map = new HashMap<>();
map.put("hello","hello");
}
然后我們點進去看，因為這個方法是在Map介面里面宣告了，而HashMap實作了該介面，所以來到HashMap類
public V put(K key, V value) {
//算出key的hash值
return putVal(hash(key), key, value, false, true);
}
我們發現真正執行添加元素的方法是putVal()，并且在這一步我們算出了key對應的hash值，然后繼續
下面是執行添加元素的核心方法，遇到長代碼先不要慌，先聽我分析一下再看，首先putVal()方法主要做的事情就是算出要添加的元素要放到的陣列下標是什么，算出下標后然后看看下標對應的那個位置有沒有存在的元素，如果為空則直接放進去就行，如果不是則再分析這個原本就存在節點的key值到底和要添加的元素的key值一不一樣，如果一樣則會有對應操作，否則再繼續判斷這個節點是不是一棵樹的根節點，如果是就再執行對應操作，否則就當成鏈來處理，然后請大家耐心看完并理解下面的代碼，
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//定義了tab陣列用來存放值
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//重新計算陣列的長度
n = (tab = resize()).length;
//在這里jdk8使用了‘&’位運算來替代了jdk7的'%'取余運算子，因為位運算的效率更高
//用'&'取余是有限制的，必須是2的n次冪才行，所以規定初始容量必須是2的冪次
//等下會分析一下用'&'的可行性
if ((p = tab[i = (n - 1) & hash]) == null)
//如果對應的陣列下標上沒有節點，則直接賦一個新的節點上前去就好了
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//第一種情況是存在的key與現在要插進去的key相同(通過hash和equal()方法進行判斷)
//理論上，如果一個類的equals方法重寫了，那么hashCode()方法必須重寫，
//并且equals方法回傳如果是true，hashoCode()方法回傳值必須一樣
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);
//如果鏈的長度大于等于8的時候 ，就會變成樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//在遍歷程序中看看有沒有key一樣的元素，如果有則退出回圈
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//經過上面那些步驟，如果e不等于空，則說明存在key值與要添加元素的key值相同的情況
//所以接下來就要考慮到底是保留舊值還是用新值覆寫舊值
if (e != null) { // existing mapping for key
V oldValue = e.value;
//這里說明如果onlyIfAbsent為true的話，說明如果舊值存在，則不進行替換，
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//此說明此hashMap被修改的次數加一，在迭代器建立視圖的時候會用到
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
筆者第一次看見’&'這個位運算子的時候，最后在網上查了多篇資料然后搞懂了，下面我整理一下我查到的資料，
首先用’&‘取余運算是有限制條件的：使用’&'運算的兩個數必須有一個是2的n次冪才行，所以java規定了容量都必須為2的冪次
之所以一定是2的冪次，是因為對于一個數x，它要被除以2的n次方，也就是在位運算中相當把x右移了n位，而剛好被移出去的n位就是我們要求的余數，
其實這也不難理解，我們可以用十進制去理解一下，比如有一個數 1001，然后因為二進制被除以2就可以類比于十進制除以了10，都是向右移了一位，所以1001向右移了一位就是100，然后移出去的那一位是1，所以1001除10的余數就是1，
然后觀察一下下面的例子
11%4=3
=> 1011 & (0011) //因為11除4的余數，相當于11化為二進制后向右移動兩位，移出去的那兩位就是余數，所以用0011與11進行按位('&')與運算，剛好就能得到后兩位
=> 1011 & (0100 - 1)
=> 11 & (4 - 1) //在這里把4看所哈希表的容量，就可以理解為什么要規定容量為2的冪次了
綜上所述，用 x&(2的n次冪-1) 可以實作取余操作
我們發現在putVal()方法里面有resize()方法，它就是用來實作自動擴容的，
resize()實作擴容的關鍵
老規矩，先講訴一下下面的代碼主要是干什么的，然后再請讀者認真看看下面的代碼，首先，進行擴容最棘手的問題就是如何把因為發生了哈希沖突而形成的鏈或者樹重散列映射到新的陣列去，無論是樹還是鏈都有一個共通的做法，就是形成一條低位鏈和高位鏈，把低位鏈放在新陣列的舊下標下，也就是在舊陣列是什么下標在新陣列就是什么下標；而高位鏈則放在新陣列的（舊陣列下標+舊陣列容量）的下標上
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//在一開始閾值是被設0的
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//如果大于2的30次方，則無法再擴容
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
//這里表示舊容量和閾值都為0
newCap = DEFAULT_INITIAL_CAPACITY;//被賦值16
//DEFAULT_LOAD_FACTOR 是0.75
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//被賦值12
}
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) //對樹進行處理 split()等下會介紹，不用著急
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //如果當前下標下的元素既不是單個，也不是一棵樹的根節點，則當作鏈表處理
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//下面的回圈就是把原來的一條鏈分為兩條，一條是低位鏈，一條是高位鏈，
do {
next = e.next;
//下面這個(e.hash & oldCap) == 0 難理解不用怕，下面會講訴一下
//如果等于零，則說明在新陣列中的索引不變
//否則，在新陣列中的索引等于就索引加上舊容量
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;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
(e.hash & oldCap) == 0 到底是什么？
首先先放結論，通過這個演算法可以巧妙地把節點分為兩類
- 等于0時，該頭節點放到新陣列時的索引位置等于其在舊陣列時的索引位置，它們記為低位 low
- 不等于0時，該頭節點放到新陣列時的索引等于其在舊陣列的索引位置再加上陣列的長度，
其實記住上面結論就可以了，但也不妨看看分析，
當(e.hash & oldCap) == 0時的推導
oldCap = 2^4 = 10000
e.hash = 01010 //這個是隨便列的，只要滿足(e.hash & oldCap) == 0即可
(2*oldCap-1)= 011111
(oldCap - 1) = 01111
//然后我們就會驚奇地發現(2*oldCap-1)&e.hash 與 (oldCap-1)&e.hash的結果是一樣的，因為決定結果的(2*oldCap-1)和(oldCap-1)倒數四個低位都是1
//而(2*oldCap-1)&e.hash 和 (oldCap-1)&e.hash 剛好是分別用來算新陣列下標和舊陣列下標的，然后它們兩個算出的結果一樣，所有下標在新陣列里沒有變，
//所以有頭節點放到新陣列時的索引位置等于其在舊陣列時的索引位置的結論
當(e.hash & oldCap) != 0時的推導
oldCap = 2^4 = 10000
e.hash = 11010 //這個是隨便列的，只要滿足(e.hash & oldCap) == 0即可
(2*oldCap-1)= 011111
(oldCap - 1) = 01111
(2*oldCap-1)&e.hash結果如下
011111
& 11010
----------
11010
(oldCap-1)&e.hash結果如下
01111
& 11010
----------
01010
我們發現，下面的結果加上一個舊容量(10000)就等于上面的結果了，所以也就印證了結論
//不等于0時，該頭節點放到新陣列時的索引等于其在舊陣列的索引位置再加上陣列的長度，
然后我們看看resize()中處理樹的方法，split()
split()擴容時對紅黑樹的處理
還是先說說這個方法做了啥，其實這個方法不涉及任何有關紅黑樹的知識，大家可以無壓力閱讀，這個方法主要是基于紅黑樹各個節點所形成的雙鏈表來實作的，而這個雙鏈表是在由單鏈表節點轉為紅黑樹的時候順便實作的，所以下面的方法其實跟上面resize()處理鏈表沒什么本質區別，核心都是把鏈分為低位和高位鏈，
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;
//因為紅黑樹的節點之前除了組成了一棵樹的關系外，它們還組成了一條雙鏈表
//所以可以通過簡單的遍歷這條雙鏈表，來把它分為低位鏈和高位鏈
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
//形成一個低位雙鏈表
//bit就是容量
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;
}
}
if (loHead != null) {
//如果小于建樹的閾值（6），就把這個由TreeNode組成的雙鏈表換成由Node組成的單鏈表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) //否則，則可以進行樹化
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);
}
}
}
通過看上面的方法，我們還會發現如果紅黑樹的雙鏈表被分為兩條后，如果它們沒有到達指定條件去重新生成一棵樹的話，就會重新變為普通的單鏈表，
在將treeify()方法來建立紅黑樹之前，先介紹紅黑樹的基礎知識
關于紅黑樹的最少必要知識
首先先列一下紅黑樹的特性：
- 每個節點要么是紅色，要么是黑色；
- 根節點永遠是黑色的；
- 所有的葉節點都是是黑色的（注意這里說葉子節點其實是上圖中的 NIL 節點）；
- 每個紅色節點的兩個子節點一定都是黑色；
- 從任一節點到其子樹中每個葉子節點的路徑都包含相同數量的黑色節點；
紅黑樹插入后保持平衡
關于往紅黑樹里插入新的元素，首先按照普通的二叉樹的方法來找到正確的位置并插進去(新插進去的節點都會被標記成紅色)，然后再分析插完節點后是否有不滿足上訴規則的，如果有不滿足，則要通過某些方法來使它滿足，從而是紅黑樹重新達到平衡的狀態，（下面的圖都是子樹而不是一棵完整的紅黑樹!）
-
第一種情況，插入的節點的父節點和其叔節點的顏色都是紅色的，（N是新插入的節點）
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-eYkdkTTC-1635150735126)(HashMap原始碼詳解.assets/image-20211025151107059.png)]
這種情況很明顯不滿足上訴的第四條規則，所有要轉換一下，變成下圖所表示
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-NRqayfam-1635150735128)(HashMap原始碼詳解.assets/image-20211025151310815.png)]
如果G的父節點也是紅色的，這樣就又違反了規則四了，但其實這與把紅色的N插進去時的場景是一樣的，我們可以把G設為新的調整節點，然后重復進行上訴步驟，直到發現了調整節點的父節點不是紅色的，那么就停止調整，
-
第二種情況，如果父親節點是紅色的，但叔叔節點是黑色的，像下圖
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-KGsKgXwf-1635150735130)(HashMap原始碼詳解.assets/image-20211025151843888.png)]
這種情況下，我們可以通過對G節點進行右旋轉并且更改相應節點的顏色來達到目的，轉換后如下圖
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-vA6J9xB4-1635150735131)(HashMap原始碼詳解.assets/image-20211025152049240.png)]
-
還有一種情況就是上一種情況的特例，就是插入的節點是父親節點的右子節點，如下圖
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-g1h2e8Cb-1635150735132)(HashMap原始碼詳解.assets/image-20211025152153089.png)]
然后我們可以通過對P進行左旋轉，來使得與上圖一樣，(轉換后如下圖)
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-rpASQIMf-1635150735133)(HashMap原始碼詳解.assets/image-20211025152251866.png)]
treeify()建立紅黑樹(基于雙鏈生成紅黑樹)
因為在建立紅黑樹之前，各個節點就已經形成了一條雙鏈表，而雙鏈表的頭就是要建立的紅黑樹的頭節點，所以這個方法大概就是遍歷鏈表，然后逐步的把遍歷到的節點加入到紅黑樹之中，如果有不平衡，就通過剛才所述的方法來調整，最終形成了一棵紅黑樹，代碼如下
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
//根節點的hash大于當前節點的
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) //如果是可排序的,dir將被賦為排序后的結果
//當 hashCode 相等且不可比較時，就用下面的方法打破僵局
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
//在這里p被設為了左節點或右節點，如果不為空則繼續回圈下去，找到為空的為止
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
//hash值比根節點小的放左邊
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//確保保證紅黑樹插入后的自平衡性
root = balanceInsertion(root, x);
break;
}
}
}
}
//確保給定的根節點是bin(桶)的第一個節點
//因為在上訴操作中，root節點可能發生變化，所以要重新確保，
moveRootToFront(tab, root);
}
上面的代碼主要是把節點插到樹里面，而確保平衡性的是呼叫了 balanceInsertion(root, x) 方法
untreeify()把雙鏈變單鏈
如果雙鏈表在經過split()方法拆分后，發現其不足以形成一棵新的紅黑樹，所以就要使用untreeify()來使雙鏈表退化為單鏈表
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
balanceInsertion()確保插入后的平衡性
這個方法主要就涉及如果發現不平衡，就通過旋轉來確保平衡性，下面是代碼
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//如果沒有父節點，說明這個是根節點
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//如果x的父節點不是紅色，或者x的父節點就是根節點(因為祖父節點為空)
//這是不會影響紅黑樹的平衡性，所有直接回傳root
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//如果父節點是祖父節點的左子節點
if (xp == (xppl = xpp.left)) {
//如果祖父右位元組的為紅色
if ((xppr = xpp.right) != null && xppr.red) {
//把祖父節點的左右子節點變為黑色，然后它自己變為紅色，
//然后繼續把祖父節點設為新的調整節點，然后繼續回圈調整
//直到調整節點的父節點不是紅色的，就完成了
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
//如果調整節點是父節點的右位元組的，則要多進行一次左旋調整，
if (x == xp.right) {
//對xp進行左旋
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
//對xpp進行右旋
root = rotateRight(root, xpp);
}
}
}
}
//下面是上面的對稱操作
else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
至此，split()方法中對紅黑樹的處理就完成了，并且知道了resize()方法是怎樣實作擴容的，
然后我們繼續沿著putVal()方法往下看，然后我們發現了如果要插入的那個桶存在節點，并且那個節點就是樹的根節點的時候，就會呼叫putTreeVal()
putTreeVal()往紅黑樹里插入資料
這個方法很簡單，主要就是先找到要插入位置，然后插進去，再平衡一下，最后把root節點設為當前桶的節點（也是雙鏈表的頭節點），代碼如下
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
//放到左邊
if ((ph = p.hash) > h)
dir = -1;
//放到右邊
else if (ph < h)
dir = 1;
//如果遇到key值一樣的，回傳當前treeNode元素
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
//如果要插入的左子節點或右子節點不是空的，繼續回圈
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
繼續在putVal()方法往下看，然后我們發現在對鏈處理的時候，會呼叫到treeifyBin()方法，目的是如果單鏈的長度在大于8的時候，就要生成紅黑樹，提高查找的效率，所以treeifyBin()就是把單鏈進化成雙鏈，然后再呼叫treeify()方法基于雙鏈生成一棵紅黑樹，代碼如下
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果容量小于64，則還不能建樹，先擴容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
//把單鏈表變成(TreeNode)雙鏈表
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
//在這里才真正開始樹化
hd.treeify(tab);
}
}
至此，往哈希表里放元素的原理就基本講完了，下面對一些常見的問題進行總結
總結
為什么HashMap的容量一定是2的冪次
直接求余效率不如位移運算，正因為容量是2的冪次，所以才可以用’&‘來替代取余運算子’%’
為什么負載因子是0.75
我們知道，threshold(閾值)在一開始是通過負載因子乘以初始容量16來獲取的，也就是 0.75*16=12，而為什么要設為0.75，官方檔案的解釋是：理想情況下，在隨機 hashCodes 下，bins 中節點的頻率遵循泊松分布 (http:en.wikipedia.orgwikiPoisson_distribution)，對于默認調整大小閾值 0.75，引數平均約為 0.5，
加載因子過高：
例如為1，雖然減少了空間開銷，提高了空間利用率，但同時也增加了查詢時間成本，
加載因子過低：
例如0.5，雖然可以減少查詢時間成本，但是空間利用率很低，同時提高了rehash操作的次數，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/336238.html
標籤：其他
上一篇：一看就懂的貪心演算法
下一篇：入職一家初創公司第一周的血與淚