hashmap转红黑树的阈值为8_面试必考的 HashMap，这篇总结到位了
1 概述
HashMap是基于哈希表實現的,每一個元素是一個key-value對,其內部通過單鏈表解決沖突問題,容量不足(超過了閥值)時,同樣會自動增長.
HashMap是非線程安全的,只適用于單線程環境,多線程環境可以采用并發包下的concurrentHashMap
HashMap 實現了Serializable接口，因此它支持序列化，實現了Cloneable接口，能被克隆
HashMap是基于哈希表的Map接口的非同步實現.此實現提供所有可選的映射操作,并允許使用null值和null鍵.此類不保證映射的順序,特別是它不保證該順序恒久不變.
Java8中又對此類底層實現進行了優化，比如引入了紅黑樹的結構以解決哈希碰撞
2 HashMap的數據結構
在Java中,最基本的結構就是兩種,一個是數組,另外一個是模擬指針(引用),所有的數據結構都可以用這兩個基本結構來構造,HashMap也不例外. HashMap實際上是一個"鏈表散列"的數據結構,即數組和鏈表的結合體.
HashMap的主結構類似于一個數組,添加值時通過key確定儲存位置.
每個位置是一個Entry的數據結構,該結構可組成鏈表.
當發生沖突時,相同hash值的鍵值對會組成鏈表.
這種數組+鏈表的組合形式大部分情況下都能有不錯的性能效果,Java6、7就是這樣設計的. 然而,在極端情況下,一組(比如經過精心設計的)鍵值對都發生了沖突，這時的哈希結構就會退化成一個鏈表，使HashMap性能急劇下降.
所以在Java8中,HashMap的結構實現變為數組+鏈表+紅黑樹
可以看出,HashMap底層就是一個數組結構
數組中的每一項又是一個鏈表
當新建一個HashMap時,就會初始化一個數組.
3 三大集合與迭代子
HashMap使用三大集合和三種迭代子來輪詢其Key、Value和Entry對象
public?class?HashMapExam?{????public?static?void?main(String[]?args)?{
????????Map?map?=?new?HashMap(16);
????????for?(int?i?=?0;?i?????????????map.put(i,?new?String(new?char[]{(char)?('A'+?i)}));
????????}
????????System.out.println("======keySet=======");
????????Set?set?=?map.keySet();
????????Iterator?iterator?=?set.iterator();
????????while?(iterator.hasNext())?{
????????????System.out.println(iterator.next());
????????}
????????System.out.println("======values=======");
????????Collection?values?=?map.values();
????????Iterator?stringIterator=values.iterator();
????????while?(stringIterator.hasNext())?{
????????????System.out.println(stringIterator.next());
????????}
????????System.out.println("======entrySet=======");
????????for?(Map.Entry?entry?:?map.entrySet())?{
????????????System.out.println(entry);
????????}
????}
}
4 源碼分析
//默認的初始容量16,且實際容量是2的整數冪?????static?final?int?DEFAULT_INITIAL_CAPACITY?=?1?<????//最大容量(傳入容量過大將被這個值替換)
????static?final?int?MAXIMUM_CAPACITY?=?1?<????//?默認加載因子為0.75(當表達到3/4滿時,才會再散列),這個因子在時間和空間代價之間達到了平衡.更高的因子可以降低表所需的空間,但是會增加查找代價,而查找是最頻繁操作
????static?final?float?DEFAULT_LOAD_FACTOR?=?0.75f;
????//桶的樹化閾值：即?鏈表轉成紅黑樹的閾值，在存儲數據時，當鏈表長度?>= 8時，則將鏈表轉換成紅黑樹
????static?final?int?TREEIFY_THRESHOLD?=?8;
???//?桶的鏈表還原閾值：即?紅黑樹轉為鏈表的閾值，當在擴容(resize())時(HashMap的數據存儲位置會重新計算)，在重新計算存儲位置后，當原有的紅黑樹內數量?<= 6時，則將?紅黑樹轉換成鏈表
????static?final?int?UNTREEIFY_THRESHOLD?=?6;
???//最小樹形化容量閾值：即?當哈希表中的容量?>?該值時，才允許樹形化鏈表?(即?將鏈表?轉換成紅黑樹)
因為紅黑樹的平均查找長度是log(n)，長度為8的時候，平均查找長度為3，如果繼續使用鏈表，平均查找長度為8/2=4，這才有轉換為樹的必要
鏈表長度如果是小于等于6，6/2=3，雖然速度也很快的，但是轉化為樹結構和生成樹的時間并不會太短
還有選擇6和8，中間有個差值7可以有效防止鏈表和樹頻繁轉換
假設一下，如果設計成鏈表個數超過8則鏈表轉換成樹結構，鏈表個數小于8則樹結構轉換成鏈表，如果一個HashMap不停的插入、刪除元素，鏈表個數在8左右徘徊，就會頻繁的發生樹轉鏈表、鏈表轉樹，效率會很低。
????//?小于該值時使用的是擴容哦!!!
????static?final?int?MIN_TREEIFY_CAPACITY?=?64;
????//?存儲數據的Node數組,長度是2的冪.????
????//?HashMap采用鏈表法解決沖突，每一個Node本質上是一個單向鏈表?
????//HashMap底層存儲的數據結構,是一個Node數組.上面得知Node類為元素維護了一個單向鏈表.至此,HashMap存儲的數據結構也就很清晰了:維護了一個數組,每個數組又維護了一個單向鏈表.之所以這么設計,考慮到遇到哈希沖突的時候,同index的value值就用單向鏈表來維護
????//與?JDK?1.7?的對比(Entry類)，僅僅只是換了名字
????transient?Node[]?table;
????//?HashMap的底層數組中已用槽的數量?
????transient?int?size;
????//?HashMap的閾值，用于判斷是否需要調整HashMap的容量(threshold?=?容量*加載因子)?
????int?threshold;
????//?負載因子實際大小
????final?float?loadFactor;
????//?HashMap被改變的次數?
????transient?int?modCount;
????//?指定“容量大小”和“加載因子”的構造函數,是最基礎的構造函數
????public?HashMap(int?initialCapacity,?float?loadFactor)?{
????????if?(initialCapacity?????????????throw?new?IllegalArgumentException("Illegal?initial?capacity:?"?+
???????????????????????????????????????????????initialCapacity);
????????//?HashMap的最大容量只能是MAXIMUM_CAPACITY???????????????????????????????????????
????????if?(initialCapacity?>?MAXIMUM_CAPACITY)
????????????initialCapacity?=?MAXIMUM_CAPACITY;
????????//負載因子須大于0
????????if?(loadFactor?<=?0?||?Float.isNaN(loadFactor))
????????????throw?new?IllegalArgumentException("Illegal?load?factor:?"?+
???????????????????????????????????????????????loadFactor);
????????//?設置"負載因子"????????????????????????????????????????
????????this.loadFactor?=?loadFactor;
????????//?設置"HashMap閾值",當HashMap中存儲數據的數量達到threshold時,就需將HashMap的容量加倍????
????????this.threshold?=?tableSizeFor(initialCapacity);
????}
上面的tableSizeFor有何用?
tableSizeFor方法保證函數返回值是大于等于給定參數initialCapacity最小的2的冪次方的數值
??int?n?=?cap?-?1;
??n?|=?n?>>>?1;
??n?|=?n?>>>?2;
??n?|=?n?>>>?4;
??n?|=?n?>>>?8;
??n?|=?n?>>>?16;
??return?(n?=?MAXIMUM_CAPACITY)???MAXIMUM_CAPACITY?:?n?+?1;
??}
a |= b 等同于 a = a|b
逐行分析
int n = cap - 1
給定的cap 減 1,為了避免參數cap本來就是2的冪次方,這樣一來,經過后續操作，cap將會變成2 * cap,是不符合我們預期的n |= n >>> 1
n >>> 1 : n無符號右移1位,即n二進制最高位的1右移一位
n | (n >>> 1) 導致 n二進制的高2位值為1
目前n的高1~2位均為1n |= n >>> 2
n繼續無符號右移2位
n | (n >>> 2) 導致n二進制表示的高34位經過運算值均為1
目前n的高14位均為1n |= n >>> 4
n繼續無符號右移4位
n | (n >>> 4) 導致n二進制表示的高58位經過運算值均為1
目前n的高18位均為1n |= n >>> 8
n繼續無符號右移8位
n | (n >>> 8) 導致n二進制表示的高916位經過運算值均為1
目前n的高116位均為1
可以看出,無論給定cap(cap < MAXIMUM_CAPACITY )的值是多少,經過以上運算,其值的二進制所有位都會是1.再將其加1,這時候這個值一定是2的冪次方.
當然如果經過運算值大于MAXIMUM_CAPACITY,直接選用MAXIMUM_CAPACITY.
至此tableSizeFor如何保證cap為2的冪次方已經顯而易見了,那么問題來了
4.1 為什么cap要保持為2的冪次方？
主要與HashMap中的數據存儲有關.
在Java8中,HashMap中key的Hash值由Hash(key)方法計得
HashMap中存儲數據table的index是由key的Hash值決定的.
在HashMap存儲數據時,我們期望數據能均勻分布,以防止哈希沖突.
自然而然我們就會想到去用%取余操作來實現我們這一構想
取余(%)操作 : 如果除數是2的冪次則等價于與其除數減一的與(&)操作.
這也就解釋了為什么一定要求cap要為2的冪次方.再來看看table的index的計算規則：
等價于:index = e.hash % newCap
采用二進制位操作&,相對于%,能夠提高運算效率,這就是cap的值被要求為2冪次的原因
4.2 Node類
static?class?Node?implements?Map.Entry?{????????final?int?hash;
????????final?K?key;
????????V?value;
????????Node?next;
????????Node(int?hash,?K?key,?V?value,?Node?next)?{
????????????this.hash?=?hash;
????????????this.key?=?key;
????????????this.value?=?value;
????????????this.next?=?next;
????????}
????????public?final?K?getKey()????????{?return?key;?}
????????public?final?V?getValue()??????{?return?value;?}
????????public?final?String?toString()?{?return?key?+?"="?+?value;?}
????????public?final?int?hashCode()?{
????????????return?Objects.hashCode(key)?^?Objects.hashCode(value);
????????}
????????public?final?V?setValue(V?newValue)?{
????????????V?oldValue?=?value;
????????????value?=?newValue;
????????????return?oldValue;
????????}
????????public?final?boolean?equals(Object?o)?{
????????????if?(o?==?this)
????????????????return?true;
????????????if?(o?instanceof?Map.Entry)?{
????????????????Map.Entry?e?=?(Map.Entry)o;
????????????????if?(Objects.equals(key,?e.getKey())?&&
????????????????????Objects.equals(value,?e.getValue()))
????????????????????return?true;
????????????}
????????????return?false;
????????}
????}
Node 類是HashMap中的靜態內部類,實現Map.Entry接口.定義了key鍵、value值、next節點,也就是說元素之間構成了單向鏈表.
4.3 TreeNode
static?final?class?TreeNode?extends?LinkedHashMap.Entry?{????????TreeNode?parent;??//?red-black?tree?links
????????TreeNode?left;
????????TreeNode?right;
????????TreeNode?prev;????//?needed?to?unlink?next?upon?deletion
????????boolean?red;
????????TreeNode(int?hash,?K?key,?V?val,?Node?next)?{}
????????//?返回當前節點的根節點??
????????final?TreeNode?root()?{??
??????????for?(TreeNode?r?=?this,?p;;)?{??
????????????if?((p?=?r.parent)?==?null)??
????????????????return?r;??
????????????r?=?p;??
????????}??
????}?
?}
紅黑樹結構包含前、后、左、右節點，以及標志是否為紅黑樹的字段
此結構是Java8新加的
4.4 hash方法
Java 8中的散列值優化函數
只做一次16位右位移異或
key.hashCode()函數調用的是key鍵值類型自帶的哈希函數，返回int型散列值
理論上散列值是一個int型，如果直接拿散列值作為下標訪問HashMap主數組的話，考慮到2進制32位帶符號的int范圍大概40億的映射空間。只要哈希函數映射得比較均勻松散，一般應用是很難出現碰撞的。
但問題是一個40億長度的數組，內存是放不下的.HashMap擴容之前的數組初始大小才16,所以這個散列值是不能直接拿來用的.
用之前還要先做對數組的長度取模運算，得到的余數才能用來訪問數組下標
源碼中模運算就是把散列值和數組長度做一個"與"操作，
這也正好解釋了為什么HashMap的數組長度要取2的整次冪
因為這樣(數組長度-1)正好相當于一個“低位掩碼”
“與”操作的結果就是散列值的高位全部歸零，只保留低位值，用來做數組下標訪問
以初始長度16為例，16-1=15
2進制表示是00000000 00000000 00001111
和某散列值做“與”操作如下，結果就是截取了最低的四位值
但這時候問題就來了,這樣就算我的散列值分布再松散,要是只取最后幾位的話,碰撞也會很嚴重
這時候“擾動函數”的價值就體現出來了
右位移16位，正好是32位一半，自己的高半區和低半區做異或，就是為了混合原始hashCode的高位和低位，以此來加大低位的隨機性
而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來。
index的運算規則是e.hash & (newCap - 1)
newCap是2的冪,所以newCap - 1的高位全0
若e.hash值只用自身的hashcode,index只會和e.hash的低位做&操作.這樣一來,index的值就只有低位參與運算,高位毫無存在感,從而會帶來哈希沖突的風險
所以在計算key的hashCode時,用其自身hashCode與其低16位做異或操作
這也就讓高位參與到index的計算中來了,即降低了哈希沖突的風險又不會帶來太大的性能問題
4.5 Put方法
①.判斷鍵值對數組table[i]是否為空或為null，否則執行resize()進行擴容
②.根據鍵值key計算hash值得到插入的數組索引i，如果table[i]==null，直接新建節點添加，轉向⑥，如果table[i]不為空，轉向③
③.判斷table[i]的首個元素是否和key一樣，如果相同直接覆蓋value，否則轉向④，這里的相同指的是hashCode以及equals
④.判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向⑤
⑤.遍歷table[i]，判斷鏈表長度是否大于8，大于8的話把鏈表轉換為紅黑樹，在紅黑樹中執行插入操作，否則進行鏈表的插入操作；遍歷過程中若發現key已經存在直接覆蓋value即可
⑥.插入成功后，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，執行resize()擴容
public?V?put(K?key,?V?value)?{????????//?對key的hashCode()做hash
????????return?putVal(hash(key),?key,?value,?false,?true);
????}
final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,?boolean?evict)?{
????????Node[]?tab;?Node?p;?int?n,?i;
????????//?步驟①?tab為空則調用resize()初始化創建
????????if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)?????????
????????????n?=?(tab?=?resize()).length;
????????//?步驟②?計算index,并對null做處理??
????????//tab[i?=?(n?-?1)?&?hash對應下標的第一個節點???
????????if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)
????????????//?無哈希沖突的情況下,將value直接封裝為Node并賦值
????????????tab[i]?=?newNode(hash,?key,?value,?null);
????????else?{
????????????Node?e;?K?k;
????????????//?步驟③?節點的key相同,直接覆蓋節點
????????????if?(p.hash?==?hash?&&?((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????e?=?p;
????????????//?步驟④?判斷該鏈為紅黑樹????
????????????else?if?(p?instanceof?TreeNode)
?????????????????//?p是紅黑樹類型，則調用putTreeVal方式賦值
????????????????e?=?((TreeNode)p).putTreeVal(this,?tab,?hash,?key,?value);
????????????//?步驟⑤?p非紅黑樹類型,該鏈為鏈表????
????????????else?{
????????????????//?index?相同的情況下
????????????????for?(int?binCount?=?0;?;?++binCount)?{
????????????????????if?((e?=?p.next)?==?null)?{
????????????????????????//?如果p的next為空,將新的value值添加至鏈表后面
????????????????????????p.next?=?newNode(hash,?key,?value,?null);
????????????????????????if?(binCount?>=?TREEIFY_THRESHOLD?-?1)
????????????????????????????//?如果鏈表長度大于8,鏈表轉化為紅黑樹,執行插入
????????????????????????????treeifyBin(tab,?hash);
????????????????????????break;
????????????????????}
????????????????????//?key相同則跳出循環
????????????????????if?(e.hash?==?hash?&&??((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????????????break;
????????????????????//就是移動指針方便繼續取?p.next
????????????????????p?=?e;
????????????????}
????????????}
????????????if?(e?!=?null)?{?//?existing?mapping?for?key
????????????????V?oldValue?=?e.value;
????????????????//根據規則選擇是否覆蓋value
????????????????if?(!onlyIfAbsent?||?oldValue?==?null)
????????????????????e.value?=?value;
????????????????afterNodeAccess(e);
????????????????return?oldValue;
????????????}
????????}
????????++modCount;
????????//?步驟⑥:超過最大容量,就擴容
????????if?(++size?>?threshold)
????????????//?size大于加載因子,擴容
????????????resize();
????????afterNodeInsertion(evict);
????????return?null;
????}
在構造函數中最多也只是設置了initialCapacity、loadFactor的值,并沒有初始化table,table的初始化工作是在put方法中進行的.
4.6 resize
擴容(resize)就是重新計算容量,向HashMap對象里不停的添加元素,內部的數組無法裝載更多的元素時,就需要擴大數組的長度.
當然Java里的數組是無法自動擴容的,方法是使用一個新的數組代替已有的容量小的數組
?????*?該函數有2種使用情況：1.初始化哈希表 2.當前數組容量過小，需擴容
?????*/
final?Node[]?resize()?{
????????Node[]?oldTab?=?table;
????????int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;
????????int?oldThr?=?threshold;
????????int?newCap,?newThr?=?0;
????????//?針對情況2：若擴容前的數組容量超過最大值，則不再擴充
????????if?(oldCap?>?0)?{
????????????if?(oldCap?>=?MAXIMUM_CAPACITY)?{
????????????????threshold?=?Integer.MAX_VALUE;
????????????????return?oldTab;
????????????}
????????????//?針對情況2：若無超過最大值，就擴充為原來的2倍
????????????else?if?((newCap?=?oldCap?<?????????????????????oldCap?>=?DEFAULT_INITIAL_CAPACITY)
????????????????//newCap設置為oldCap的2倍并小于MAXIMUM_CAPACITY，且大于默認值,?新的threshold增加為原來的2倍
????????????????newThr?=?oldThr?<????????}
????????//?針對情況1：初始化哈希表(采用指定 or 默認值)
????????else?if?(oldThr?>?0)?//?initial?capacity?was?placed?in?threshold
????????????//?threshold>0,?將threshold設置為newCap,所以要用tableSizeFor方法保證threshold是2的冪次方
????????????newCap?=?oldThr;
????????else?{???????????????//?zero?initial?threshold?signifies?using?defaults
????????????//?默認初始化
????????????newCap?=?DEFAULT_INITIAL_CAPACITY;
????????????newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);
????????}
????????//?計算新的resize上限
????????if?(newThr?==?0)?{
????????????//?newThr為0，newThr?=?newCap?*?0.75
????????????float?ft?=?(float)newCap?*?loadFactor;
????????????newThr?=?(newCap?float)MAXIMUM_CAPACITY??
??????????????????????(int)ft?:?Integer.MAX_VALUE);
????????}
????????threshold?=?newThr;
????????@SuppressWarnings({"rawtypes","unchecked"})
????????????//?新生成一個table數組
????????????Node[]?newTab?=?(Node[])new?Node[newCap];
????????table?=?newTab;
????????if?(oldTab?!=?null)?{
????????????//?oldTab?復制到?newTab
????????????for?(int?j?=?0;?j?????????????????Node?e;
????????????????if?((e?=?oldTab[j])?!=?null)?{
????????????????????oldTab[j]?=?null;
????????????????????if?(e.next?==?null)
???????????????????????//?鏈表只有一個節點，直接賦值
???????????????????????//為什么要重新Hash呢？因為長度擴大以后，Hash的規則也隨之改變。
????????????????????????newTab[e.hash?&?(newCap?-?1)]?=?e;
????????????????????else?if?(e?instanceof?TreeNode)
????????????????????????//?e為紅黑樹的情況
????????????????????????((TreeNode)e).split(this,?newTab,?j,?oldCap);
????????????????????else?{?//?preserve?order鏈表優化重hash的代碼塊
????????????????????????Node?loHead?=?null,?loTail?=?null;
????????????????????????Node?hiHead?=?null,?hiTail?=?null;
????????????????????????Node?next;
????????????????????????do?{
????????????????????????????next?=?e.next;
????????????????????????????//?原索引
????????????????????????????if?((e.hash?&?oldCap)?==?0)?{
????????????????????????????????if?(loTail?==?null)
????????????????????????????????????loHead?=?e;
????????????????????????????????else
????????????????????????????????????loTail.next?=?e;
????????????????????????????????loTail?=?e;
????????????????????????????}
????????????????????????????//?原索引?+?oldCap
????????????????????????????else?{
????????????????????????????????if?(hiTail?==?null)
????????????????????????????????????hiHead?=?e;
????????????????????????????????else
????????????????????????????????????hiTail.next?=?e;
????????????????????????????????hiTail?=?e;
????????????????????????????}
????????????????????????}?while?((e?=?next)?!=?null);
????????????????????????//?原索引放到bucket里
????????????????????????if?(loTail?!=?null)?{
????????????????????????????loTail.next?=?null;
????????????????????????????newTab[j]?=?loHead;
????????????????????????}
????????????????????????//?原索引+oldCap放到bucket里
????????????????????????if?(hiTail?!=?null)?{
????????????????????????????hiTail.next?=?null;
????????????????????????????newTab[j?+?oldCap]?=?hiHead;
????????????????????????}
????????????????????}
????????????????}
????????????}
????????}
????????return?newTab;
????}
4.7 remove方法
remove(key) 方法 和 remove(key, value) 方法都是通過調用removeNode的方法來實現刪除元素的
final?Node?removeNode(int?hash,?Object?key,?Object?value,???????????????????????????????boolean?matchValue,?boolean?movable)?{
????????Node[]?tab;?Node?p;?int?n,?index;
????????if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&
????????????(p?=?tab[index?=?(n?-?1)?&?hash])?!=?null)?{
????????????Node?node?=?null,?e;?K?k;?V?v;
????????????if?(p.hash?==?hash?&&
????????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????//?index?元素只有一個元素
????????????????node?=?p;
????????????else?if?((e?=?p.next)?!=?null)?{
????????????????if?(p?instanceof?TreeNode)
????????????????????//?index處是一個紅黑樹
????????????????????node?=?((TreeNode)p).getTreeNode(hash,?key);
????????????????else?{
????????????????????//?index處是一個鏈表，遍歷鏈表返回node
????????????????????do?{
????????????????????????if?(e.hash?==?hash?&&
????????????????????????????((k?=?e.key)?==?key?||
?????????????????????????????(key?!=?null?&&?key.equals(k))))?{
????????????????????????????node?=?e;
????????????????????????????break;
????????????????????????}
????????????????????????p?=?e;
????????????????????}?while?((e?=?e.next)?!=?null);
????????????????}
????????????}
????????????//?分不同情形刪除節點
????????????if?(node?!=?null?&&?(!matchValue?||?(v?=?node.value)?==?value?||
?????????????????????????????????(value?!=?null?&&?value.equals(v))))?{
????????????????if?(node?instanceof?TreeNode)
????????????????????((TreeNode)node).removeTreeNode(this,?tab,?movable);
????????????????else?if?(node?==?p)
????????????????????tab[index]?=?node.next;
????????????????else
????????????????????p.next?=?node.next;
????????????????++modCount;
????????????????--size;
????????????????afterNodeRemoval(node);
????????????????return?node;
????????????}
????????}
????????return?null;
????}
4.8 get
/**???*?函數原型
???*?作用：根據鍵key，向HashMap獲取對應的值
???*/?
?? map.get(key)；
?/**
???*?源碼分析
???*/?
???public?V?get(Object?key)?{
????Node?e;
????//?1\.?計算需獲取數據的hash值
????//?2\.?通過getNode()獲取所查詢的數據?->>分析1
????//?3\.?獲取后，判斷數據是否為空
????return?(e?=?getNode(hash(key),?key))?==?null???null?:?e.value;
}
/**
???*?分析1：getNode(hash(key),?key))
???*/?
final?Node?getNode(int?hash,?Object?key)?{
????Node[]?tab;?Node?first,?e;?int?n;?K?k;
????//?1\.?計算存放在數組table中的位置
????if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&
????????(first?=?tab[(n?-?1)?&?hash])?!=?null)?{
????????//?4\.?通過該函數，依次在數組、紅黑樹、鏈表中查找(通過equals()判斷)
????????//?a.?先在數組中找，若存在，則直接返回
????????if?(first.hash?==?hash?&&?//?always?check?first?node
????????????((k?=?first.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????return?first;
????????//?b.?若數組中沒有，則到紅黑樹中尋找
????????if?((e?=?first.next)?!=?null)?{
????????????//?在樹中get
????????????if?(first?instanceof?TreeNode)
????????????????return?((TreeNode)first).getTreeNode(hash,?key);
????????????//?c.?若紅黑樹中也沒有，則通過遍歷，到鏈表中尋找
????????????do?{
????????????????if?(e.hash?==?hash?&&
????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????????return?e;
????????????}?while?((e?=?e.next)?!=?null);
????????}
????}
????return?null;
}
在JDK1.7及以前的版本中，HashMap里是沒有紅黑樹的實現的，在JDK1.8中加入了紅黑樹是為了防止哈希表碰撞攻擊，當鏈表鏈長度為8時，及時轉成紅黑樹，提高map的效率
如果某個桶中的記錄過大的話(當前是TREEIFY_THRESHOLD = 8)，HashMap會動態的使用一個專門的treemap實現來替換掉它。這樣做的結果會更好，是O(logn)，而不是糟糕的O(n)。它是如何工作的？前面產生沖突的那些KEY對應的記錄只是簡單的追加到一個鏈表后面，這些記錄只能通過遍歷來進行查找。但是超過這個閾值后HashMap開始將列表升級成一個二叉樹，使用哈希值作為樹的分支變量，如果兩個哈希值不等，但指向同一個桶的話，較大的那個會插入到右子樹里。如果哈希值相等，HashMap希望key值最好是實現了Comparable接口的，這樣它可以按照順序來進行插入。這對HashMap的key來說并不是必須的，不過如果實現了當然最好。如果沒有實現這個接口，在出現嚴重的哈希碰撞的時候，你就并別指望能獲得性能提升了。
這個性能提升有什么用處？比方說惡意的程序，如果它知道我們用的是哈希算法，它可能會發送大量的請求，導致產生嚴重的哈希碰撞。然后不停的訪問這些key就能顯著的影響服務器的性能，這樣就形成了一次拒絕服務攻擊(DoS)。JDK 8中從O(n)到O(logn)的飛躍，可以有效地防止類似的攻擊，同時也讓HashMap性能的可預測性稍微增強了一些
/**???*?源碼分析：resize(2 * table.length)
???*?作用：當容量不足時(容量?>?閾值)，則擴容(擴到2倍)
???*/?
???void?resize(int?newCapacity)?{??
????//?1\.?保存舊數組(old?table)?
????Entry[]?oldTable?=?table;??
????//?2\.?保存舊容量(old?capacity?)，即數組長度
????int?oldCapacity?=?oldTable.length;?
????//?3\.?若舊容量已經是系統默認最大容量了，那么將閾值設置成整型的最大值，退出????
????if?(oldCapacity?==?MAXIMUM_CAPACITY)?{??
????????threshold?=?Integer.MAX_VALUE;??
????????return;??
????}??
????//?4\.?根據新容量(2倍容量)新建1個數組，即新table??
????Entry[]?newTable?=?new?Entry[newCapacity];??
????//?5\.?(重點分析)將舊數組上的數據(鍵值對)轉移到新table中，從而完成擴容?->>分析1.1?
????transfer(newTable);?
????//?6\.?新數組table引用到HashMap的table屬性上
????table?=?newTable;??
????//?7\.?重新設置閾值??
????threshold?=?(int)(newCapacity?*?loadFactor);?
}?
?/**
???*?分析1.1：transfer(newTable);?
???*?作用：將舊數組上的數據(鍵值對)轉移到新table中，從而完成擴容
???*?過程：按舊鏈表的正序遍歷鏈表、在新鏈表的頭部依次插入
???*/?
void?transfer(Entry[]?newTable)?{
??????//?1\.?src引用了舊數組
??????Entry[]?src?=?table;?
??????//?2\.?獲取新數組的大小?=?獲取新容量大小?????????????????
??????int?newCapacity?=?newTable.length;
??????//?3\.?通過遍歷?舊數組，將舊數組上的數據(鍵值對)轉移到新數組中
??????for?(int?j?=?0;?j???????????//?3.1?取得舊數組的每個元素??
??????????Entry?e?=?src[j];???????????
??????????if?(e?!=?null)?{
??????????????//?3.2?釋放舊數組的對象引用(for循環后，舊數組不再引用任何對象)
??????????????src[j]?=?null;?
??????????????do?{?
??????????????????//?3.3?遍歷?以該數組元素為首?的鏈表
??????????????????//?注：轉移鏈表時，因是單鏈表，故要保存下1個結點，否則轉移后鏈表會斷開
??????????????????Entry?next?=?e.next;?
?????????????????//?3.3?重新計算每個元素的存儲位置
?????????????????int?i?=?indexFor(e.hash,?newCapacity);?
?????????????????// 3.4 將元素放在數組上：采用單鏈表的頭插入方式?=?在鏈表頭上存放數據?=?將數組位置的原有數據放在后1個指針、將需放入的數據放到數組位置中
?????????????????//?即?擴容后，可能出現逆序：按舊鏈表的正序遍歷鏈表、在新鏈表的頭部依次插入
?????????????????e.next?=?newTable[i];?
?????????????????newTable[i]?=?e;??
?????????????????//?訪問下1個Entry鏈上的元素，如此不斷循環，直到遍歷完該鏈表上的所有節點
?????????????????e?=?next;?????????????
?????????????}?while?(e?!=?null);
?????????????//?如此不斷循環，直到遍歷完數組上的所有數據元素
?????????}
?????}
?}
從上面可看出：在擴容resize()過程中，在將舊數組上的數據 轉移到 新數組上時，轉移數據操作 = 按舊鏈表的正序遍歷鏈表、在新鏈表的頭部依次插入，即在轉移數據、擴容后，容易出現鏈表逆序的情況
設重新計算存儲位置后不變，即擴容前 = 1->2->3，擴容后 = 3->2->1
此時若并發執行 put 操作，一旦出現擴容情況，則 容易出現 環形鏈表，從而在獲取數據、遍歷鏈表時 形成死循環(Infinite Loop)，即死鎖
單線程rehash
單線程情況下，rehash無問題
多線程并發下的rehash
這里假設有兩個線程同時執行了put操作并引發了rehash，執行了transfer方法，并假設線程一進入transfer方法并執行完next = e.next后，因為線程調度所分配時間片用完而“暫停”，此時線程二完成了transfer方法的執行。此時狀態如下。
接著線程1被喚醒，繼續執行第一輪循環的剩余部分
e.next?=?newTable[1]?=?nullnewTable[1]?=?e?=?key(5)
e?=?next?=?key(9)
結果如下圖所示
接著執行下一輪循環，結果狀態圖如下所示
繼續下一輪循環，結果狀態圖如下所示
此時循環鏈表形成，并且key(11)無法加入到線程1的新數組。在下一次訪問該鏈表時會出現死循環。
Fast-fail
產生原因
在使用迭代器的過程中如果HashMap被修改，那么ConcurrentModificationException將被拋出，也即Fast-fail策略。
當HashMap的iterator()方法被調用時，會構造并返回一個新的EntryIterator對象，并將EntryIterator的expectedModCount設置為HashMap的modCount(該變量記錄了HashMap被修改的次數)。
HashIterator()?{??expectedModCount?=?modCount;
??if?(size?>?0)?{?//?advance?to?first?entry
??Entry[]?t?=?table;
??while?(index?????;
??}
}
在通過該Iterator的next方法訪問下一個Entry時，它會先檢查自己的expectedModCount與HashMap的modCount是否相等，如果不相等，說明HashMap被修改，直接拋出ConcurrentModificationException。該Iterator的remove方法也會做類似的檢查。該異常的拋出意在提醒用戶及早意識到線程安全問題。
線程安全解決方案
單線程條件下，為避免出現ConcurrentModificationException，需要保證只通過HashMap本身或者只通過Iterator去修改數據，不能在Iterator使用結束之前使用HashMap本身的方法修改數據。因為通過Iterator刪除數據時，HashMap的modCount和Iterator的expectedModCount都會自增，不影響二者的相等性。如果是增加數據，只能通過HashMap本身的方法完成，此時如果要繼續遍歷數據，需要重新調用iterator()方法從而重新構造出一個新的Iterator，使得新Iterator的expectedModCount與更新后的HashMap的modCount相等。
多線程條件下，可使用Collections.synchronizedMap方法構造出一個同步Map，或者直接使用線程安全的ConcurrentHashMap。
總結
以上是生活随笔為你收集整理的hashmap转红黑树的阈值为8_面试必考的 HashMap，这篇总结到位了的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 相同布局在不同手机上显示不同_不懂响应式
- 下一篇： java map key 大写转小写_S