hashmap取值_一万六千字的HashMap深度剖析
概論
HashMap 是無論在工作還是面試中都非常常見常考的數據結構。比如 Leetcode 第一題 Two Sum 的某種變種的最優解就是需要用到 HashMap 的，高頻考題 LRU Cache 是需要用到 LinkedHashMap 的。HashMap 用起來很簡單，所以今天我們來從源碼的角度梳理一下Hashmap
隨著JDK(Java Developmet Kit)版本的更新，JDK1.8對HashMap底層的實現進行了優化，例如引入紅黑樹的數據結構和擴容的優化等。
HashMap：它根據鍵的hashCode值存儲數據，大多數情況下可以直接定位到它的值，因而具有很快的訪問速度，但遍歷順序卻是不確定的。
HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null。
HashMap非線程安全，即任一時刻可以有多個線程同時寫HashMap，可能會導致數據的不一致。如果需要滿足線程安全，可以用 Collections的synchronizedMap方法使HashMap具有線程安全的能力，或者使用ConcurrentHashMap。
HashMap 的繼承關系
image-20201126201445602hashmap 的原理
對于 HashMap 中的每個 key，首先通過 hash function 計算出一個 hash 值,這個hash值經過取模運算就代表了在 buckets 里的編號 buckets 實際上是用數組來實現的，所以把這個hash值模上數組的長度得到它在數組的 index，就這樣把它放在了數組里。
如果果不同的元素算出了相同的哈希值，那么這就是哈希碰撞，即多個 key 對應了同一個桶。這個時候就是解決hash沖突的時候了，展示真正技術的時候到了。
隨著插入的元素越來越多，發生碰撞的概率就越大，某個桶中的鏈表就會越來越長，直到達到一個閾值，HashMap就受不了了，為了提升性能，會將超過閾值的鏈表轉換形態，轉換成紅黑樹的結構，這個閾值是 8 。也就是單個桶內的鏈表節點數大于 8 ，就會將鏈表有可能變身為紅黑樹。
解決Hash沖突的方法
開放定址法
這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希地址p=H(key)出現沖突時，以p為基礎，產生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。這種方法有一個通用的再散列函數形式：
Hi=(H(key)+di)% m i=1，2，…，n
其中H(key)為哈希函數，m 為表長，di稱為增量序列。增量序列的取值方式不同，相應的再散列方式也不同。主要有三種 線性探測再散列，二次探測再散列，偽隨機探測再散列
再哈希法
這種方法是同時構造多個不同的哈希函數
Hi=RH1(key) i=1，2，…，k
當哈希地址Hi=RH1(key)發生沖突時，再計算Hi=RH2(key)……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間
鏈地址法
這種方法的基本思想是將所有哈希地址為i的元素構成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。
鏈地址法適用于經常進行插入和刪除的情況。
建立公共溢出區
這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表。
hashmap 最終的形態
一頓操作猛如虎，搞得原本還是很單純的hashmap 變得這么復雜，難倒了無數英雄好漢，由于鏈表長度過程，會導致查詢變慢，所以鏈表慢慢最后演化出了紅黑樹的形態
HashMap主體上就是一個數組結構，每一個索引位置英文叫做一個 bin，我們這里先管它叫做桶，比如你定義一個長度為 8 的 HashMap，那就可以說這是一個由 8 個桶組成的數組。
當我們像數組中插入數據的時候，大多數時候存的都是一個一個 Node 類型的元素，Node 是 HashMap中定義的靜態內部類
image-20201127171502527Hashmap 的返回值
很多人以為Hashmap 是沒有返回值的，或者也沒有關注過Hashmap 的返回值，其實在你調用Hashmap的put(key,value) 方法 的時候，它會將當前key 已經有的值返回，然后把你的新值放到對應key 的位置上
public?class?JavaHashMap?{????public?static?void?main(String[]?args)?{
????????HashMap?map?=?new?HashMap();
????????String?oldValue?=?map.put("java大數據",?"數據倉庫");
????????System.out.println(oldValue);
????????oldValue?=?map.put("java大數據",?"實時數倉");
????????System.out.println(oldValue);
????}
}
運行結果如下，因為一開始是沒有值的，所以返回null,后面有值了，put 的時候就返回了舊的值
image-20201126202457415這里有一個問題需要注意一下，因為Map的Key,Value 的類型都是引用類型，所以在沒有值的情況下一定返回的是null，而不是0 等初始值。
HashMap 的關鍵內部元素
存儲容器 table;
因為HashMap內部是用一個數組來保存內容的， 它的定義 如下
transient Node[] table
如果哈希桶數組很大，即使較差的Hash算法也會比較分散，如果哈希桶數組數組很小，即使好的Hash算法也會出現較多碰撞，所以就需要在空間成本和時間成本之間權衡，其實就是在根據實際情況確定哈希桶數組的大小，并在此基礎上設計好的hash算法減少Hash碰撞。那么通過什么方式來控制map使得Hash碰撞的概率又小，哈希桶數組(Node[] table)占用空間又少呢？答案就是好的Hash算法和擴容機制。
在HashMap中，哈希桶數組table的長度length大小必須為2的n次方(一定是合數)，這是一種非常規的設計，常規的設計是把桶的大小設計為素數。相對來說素數導致沖突的概率要小于合數
size 元素個數
size這個字段其實很好理解，就是HashMap中實際存在的鍵值對數量。注意和table的長度length、容納最大鍵值對數量threshold的區別
Node
?static?class?Node<K,V>?implements?Map.Entry<K,V>?{?????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;
?????}
}
Node是HashMap的一個靜態內部類。實現了Map.Entry接口，本質是就是一個映射(鍵值對),主要包括 hash、key、value 和 next 的屬性。
我們使用 put 方法像其中加鍵值對的時候，就會轉換成 Node 類型。其實就是newNode(hash, key, value, null);
TreeNode
當桶內鏈表到達 8 的時候，會將鏈表轉換成紅黑樹，就是 TreeNode類型，它也是 HashMap中定義的靜態內部類。
static?final?class?TreeNodeV>?extends?LinkedHashMap.EntryV>?{????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)?{super(hash,?key,?val,?next);
}
說起TreeNode ，就不得不說其他三個相關參數 TREEIFY_THRESHOLD=8 和 UNTREEIFY_THRESHOLD=6 以及 MIN_TREEIFY_CAPACITY=64
TREEIFY_THRESHOLD=8 指的是鏈表的長度大于8 的時候進行樹化， UNTREEIFY_THRESHOLD=6 ?說的是當元素被刪除鏈表的長度小于6 的時候進行退化，由紅黑樹退化成鏈表
MIN_TREEIFY_CAPACITY=64 意思是數組中元素的個數必須大于等于64之后才能進行樹化
modCount
modCount字段主要用來記錄HashMap內部結構發生變化的次數，主要用于迭代的快速失敗。強調一點，內部結構發生變化指的是結構發生變化，例如put新鍵值對，但是某個key對應的value值被覆蓋不屬于結構變化。
閾值 threshold
它是加在因子乘以初始值大小，后續擴容的時候和數組大小一樣，2倍進行擴容
threshold?=?(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY)實際存儲元素個數 size
size 默認大小是0 ，它指的是數組存儲的元素個數，而不是整個hashmap 的元素個數，對于下面這張圖就是3 而不是11
transient?int?size;image-20201127171502527
debug 源碼 插入元素的過程
public?class?JavaHashMap?{????public?static?void?main(String[]?args)?{
????????HashMap<String,?String>?map?=?new?HashMap<String,?String>();
????????String?oldValue?=?map.put("java大數據",?"數據倉庫");
????}
}
調用put()方法
這個方法沒什么好說的，是hashmap 提供給用戶調用的方法，很簡單
調用 putval()
Put 方法實際上調用的實 ?putval() 方法
image-20201126204454960可以看出在進入putval() 方法之間，需要借助hash 方法先計算出key 的hash 值，然后將key 的hash值和key同時傳入
調用hash() 方法
image-20201126204634472這個key的hashCode()方法得到其hashCode 值(該方法適用于每個Java對象)，然后再通過Hash算法的后兩步運算(高位運算和取模運算，下文有介紹)來定位該鍵值對的存儲位置，有時兩個key會定位到相同的位置，表示發生了Hash碰撞。當然Hash算法計算結果越分散均勻，Hash碰撞的概率就越小，map的存取效率就會越高。
在JDK1.8的實現中，優化了高位運算的算法，通過hashCode()的高16位異或低16位實現的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、質量來考慮的，這么做可以在數組table的length比較小的時候，也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷。
進入 putval()
進入putval 方法之后，整體數據流程如下，下面會詳細介紹每一步
image-20201126204925231final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,???????????????boolean?evict)?{
????Node[]?tab;?Node?p;?int?n,?i;//?判斷是否需要初始化數組if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)
????????n?=?(tab?=?resize()).length;if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)//?當前位置為空，則直接插入，同時意味著不走else?最后直接返回null
????????tab[i]?=?newNode(hash,?key,?value,?null);else?{
????????Node?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)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;
????????}
????}//?可以看出只有當前key?的位置為空的時候才判斷時候需要reszie?已經返回?null?其他情況下都走了else?的環節
????++modCount;if?(++size?>?threshold)
????????resize();
????afterNodeInsertion(evict);return?null;
}
判斷數組是否為空,需不需要調用resize 方法
第一次調用，這里table 是null,所以會走resize 方法
image-20201126205708504resize 方法本身也是比較復雜的，因為這里是第一次調用，所以這里進行了簡化
????final?Node[]?resize()?{????????Node[]?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)??????????????????????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?float)MAXIMUM_CAPACITY??
??????????????????????(int)ft?:?Integer.MAX_VALUE);
????????}
????????threshold?=?newThr;@SuppressWarnings({"rawtypes","unchecked"})
????????Node[]?newTab?=?(Node[])new?Node[newCap];
????????table?=?newTab;if?(oldTab?!=?null)?{//?因為?oldTab?為null?所以不會進來這個if?判斷，所以將這里的代碼省略了
????????}return?newTab;
????}
table 為空首次初始化
如果是的話，初始化數組大小和threashold
newCap?=?DEFAULT_INITIAL_CAPACITY;newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);
初始化之后，將新創建的數組返回，在返回之前完成了對變量table 的賦值
image-20201126211551514table 不為空 不是首次初始化
如果不是的話就用當前數組的信息初始化新數組的大小
image-20201126211919741最后完成table 的初始化，返回table ，這里其實還有數據遷移，但是為了保證文章的結構，所以將resize 方法的詳細講解單獨提了出來
table?=?newTab;判斷當前位置是否有元素
1 沒有 直接放入當前位置
2 有 將當前節點記做p
當前節點記做p 然后進入else 循環
else?{????Node?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)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;
????}
?}
判斷直接覆蓋(判斷是否是同一個key)
判斷新的key 和老的key 是否相同，這里同時要求了hash 值和 實際的值是相等的情況下然后直接完成了e=p 的賦值，其實也就是完成了替換，因為key 是相同的。
如果不是同一個key 的話這里就要將當前元素插入鏈表或者紅黑樹了，因為是不同的key 了
判斷插入紅黑樹
如果當前元素是一個 TreeNode 則將當前元素放入紅黑樹，然后
image-20201126220247642判斷插入鏈表
如果不是同一key并且當前元素類型不是TreeNode 則將當前元素插入鏈表(因為key對應的位置已經有元素了，其實可以認為是鏈表的頭元素)
可以看出采用的是尾插法，循環過程中當下一個節點是null的時候則進行插入，插入完畢之后判斷是否需要樹化
JDK 1.7 之前使用頭插法、JDK 1.8 使用尾插法
其實主要是根據(e=p.next)==null 進行判斷進入哪一個if ,因為每個 if 都含有break 語句，所以只能進入一個 然后就退出循環了
image-20201126220940075?if?((e?=?p.next)?==?null)?{
?????p.next?=?newNode(hash,?key,?value,?null);
?????if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1st
?????????treeifyBin(tab,?hash);
?????break;
?}1、這段代碼也是上圖中的第一個if這段代碼的意思就是在遍歷鏈表的過程中，一直都沒有遇到和待插入key 相同的key(第二個if) 然后當前要插入的元素插入到了鏈表的尾部(當前if 語句)
第二個if 的意思 如果有發生key沖突則停止 后續這個節點會被相同的key覆蓋
2、插入之后判斷判斷局部變量binCount 時候大于7(TREEIFY_THRESHOLD-1),這里需要注意的是binCount 是從0開始的，所以實際的意思是判斷鏈表的長度在插入新元素之前是否大于等于8，如果是的話則進行樹化
3、并且這個時候變量e 的值是null ，因為是插入到鏈表的尾部的，所以這個時候key 是沒有對應的oldValue 的，所以e是null 在最后面的判斷返回中，也返回的是null
4、關于樹化，首先這是發生在插入鏈表的時刻,并且是插入鏈表尾部的時候，因為判斷過程是在第一個if 中，為了保證文章的結構關于樹化放在下面講
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // 這個賦值很有意思，它完成了你可以使用for 循環完成鏈表遍歷的核心功能 p = e;
1、這一段代碼的意思是在遍歷的過程中(e=p.next)!=null 的的時候，也就是在循環鏈表的過程中，判斷是否有和當前key 相等的key，相等的話e 就是要覆蓋的元素，如果不相等的話就繼續循環，知道找到這樣的e 或者是將鏈表循環結束，然后將元素插入到鏈表的尾部(第一個if)
2、因為是當key 存在的時候則跳出循環，所以鏈表的長度沒有發生變化，所以這里沒有判斷是否需要樹化
最后 返回oldValue 完成新值替換
if?(e?!=?null)?{?//?existing?mapping?for?key????V?oldValue?=?e.value;
????if?(!onlyIfAbsent?||?oldValue?==?null)
????????e.value?=?value;
????afterNodeAccess(e);
????return?oldValue;
}
這個時候e 就指向原來p 的位置了，因為e=p， 然后用新的value 覆蓋掉了oldValue 完成了插入，最后將 oldValue 返回。
最后 判斷是否需要擴容 返回null 值
其實能走到這一步，是那就說明放入元素的時候，key 對應的位置是沒有元素的，所以相當于數組中添加了一個新的元素，所以這里有判斷是否需要resize 和返回空值。
?++modCount;?if?(++size?>?threshold)
?????resize();
?afterNodeInsertion(evict);
?return?null;
單獨講解resize 方法
首選需要記住resize 方法是會返回擴容后的數組的
第一部分初始化新數組
這一部分不論是不是首次調用resize 方法，都會有的，但是數據遷移部分在首次調用的時候是沒有的
Node[]?oldTab?=?table;int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;int?oldThr?=?threshold;int?newCap,?newThr?=?0;//?判斷是oldCap?是否大于0?因為可能是首次resize，如果不是的話?oldCapif?(oldCap?>?0)?{//?到達擴容上限if?(oldCap?>=?MAXIMUM_CAPACITY)?{????????threshold?=?Integer.MAX_VALUE;return?oldTab;
????}//?這里是正常的擴容else?if?((newCap?=?oldCap?<1)??????????????oldCap?>=?DEFAULT_INITIAL_CAPACITY)
????????newThr?=?oldThr?<1;?//?double?threshold
}else?if?(oldThr?>?0)?//?initial?capacity?was?placed?in?threshold
????newCap?=?oldThr;//第一次調用resize?方法，然后使用默認值進行初始化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?float)MAXIMUM_CAPACITY??
??????????????(int)ft?:?Integer.MAX_VALUE);
}//?創建新的數組，下面
threshold?=?newThr;@SuppressWarnings({"rawtypes","unchecked"})
Node[]?newTab?=?(Node[])new?Node[newCap];
table?=?newTab;
如果數組的大小 大于等于MAXIMUM_CAPACITY之后，則 threshold = Integer.MAX_VALUE; 然后不擴容直接返回當前數組，所以可以看出hashmap 的擴容上限就是MAXIMUM_CAPACITY(230)
如果數組的大小 在擴容之后小于MAXIMUM_CAPACITY 并且原始大小大于DEFAULT_INITIAL_CAPACITY(16) 則進行擴容(DEFAULT_INITIAL_CAPACITY 的大小限制是為了防止該方法的調用是在樹化方法里調用的，這個時候數組大大小可能小于DEFAULT_INITIAL_CAPACITY)
新的數組創建好之后，就可以根據老的數組是否有值決定是否進行數據遷移
第二部分數據遷移
oldTab 也就是老的數組不為空的時候進行遷移
?if?(oldTab?!=?null)?{?????????????//?遍歷oldTable，拿到每一個元素準備放入大新的數組中去
??????for?(int?j?=?0;?j???????????Node?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)e).split(this,?newTab,?j,?oldCap);//?當前元素是鏈表，則遍歷鏈表????else?{?//?preserve?order
??????????????????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;
??????????????????????}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;
??????????????????}
??????????????}
??????????}
??????}
??}
判斷當前元素的next 是否為空，是則直接放入，其實就是只有一個元素，說明這是一個最正常的節點，不是桶內鏈表，也不是紅黑樹，這樣的節點會重新計算索引位置，然后插入。
是的話，判斷是不是TreeNode,不是的話則直接遍歷鏈表進行拷貝，保證鏈表的順序不變。
是的話則調用 TreeNode.split() ?方法，如果是一顆紅黑樹，則使用 split方法處理，原理就是將紅黑樹拆分成兩個 TreeNode 鏈表，然后判斷每個鏈表的長度是否小于等于 6，如果是就將 TreeNode 轉換成桶內鏈表，否則再轉換成紅黑樹。
完成數據的拷貝，返回新的數組
第三部分 返回新的數組
?return?newTab;只要沒有到達擴容上限，這一部分是肯定會走的，至于走不走數據遷移，需要潘丹是不是首次resize()
單獨講解樹化treeifyBin方法
?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;
?}
首先判斷是符滿足鏈表長度大于8(binCount 是否大于等于7) ,需要注意的是插入到鏈表的尾部導致鏈表的長度發生了變化的情況下，才判斷是否需要樹化
然后進入treeifyBin 方法中，進入樹化方法之后又判斷了,Hashmap 的大小是否大于64，如果不是的話，只是調用了resize 方法，讓數組擴容，而不是樹化
????int?n,?index;?Node?e;if?(tab?==?null?||?(n?=?tab.length)?????????resize();else?if?((e?=?tab[index?=?(n?-?1)?&?hash])?!=?null)?{
????????TreeNode?hd?=?null,?tl?=?null;do?{
????????????TreeNode?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);
????}
}
獲取元素的過程
public?V?get(Object?key)?{????Node?e;return?(e?=?getNode(hash(key),?key))?==?null???null?:?e.value;
}/**
?*?Implements?Map.get?and?related?methods.
?*
?*?@param?hash?hash?for?key
?*?@param?key?the?key
?*?@return?the?node,?or?null?if?none
?*/final?Node?getNode(int?hash,?Object?key)?{
????Node[]?tab;?Node?first,?e;?int?n;?K?k;if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&
????????(first?=?tab[(n?-?1)?&?hash])?!=?null)?{if?(first.hash?==?hash?&&?//?always?check?first?node
????????????((k?=?first.key)?==?key?||?(key?!=?null?&&?key.equals(k))))return?first;if?((e?=?first.next)?!=?null)?{if?(first?instanceof?TreeNode)return?((TreeNode)first).getTreeNode(hash,?key);do?{if?(e.hash?==?hash?&&
????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))return?e;
????????????}?while?((e?=?e.next)?!=?null);
????????}
????}return?null;
}image-20201127190819337
總結
resize 方法總結
resize(擴容) 的上限
resize 不是無限的，當到達resize 的上限，也就是230 之后，不再擴容
resize 方法只有三種情況下調用
-?第一種?是在**首次插入元素的時候完成數組的初始化**-?第二種?是在元素插入**完成后**判斷是否需要數組擴容，如果是的話則調用
-?第三種?是在元素插入鏈表尾部之后，進入樹化方法之后，如果不樹化則進行resize?
resize 的返回值
第一種情況下 返回老的數組也就是沒有resize 因為已經達到resize 的上限了
第二種情況下 返回一個空的數組 也就是第一次調用resize方法
第三章情況下 返回一個擴容后的數組 完成了數據遷移后的數組
key 的判斷
第一次判斷是當前位置有元素的時候，如果兩個key 相等則準備覆蓋值
第二次判斷是遍歷鏈表的時候，決定能否覆蓋鏈表中間key 相等的值而不是鏈表的尾部
樹化
樹化是發生在元素插入鏈表之后，并且這里是插入到鏈表的尾部導致鏈表的長度發生了變化的情況下(也就是走的for循環里的第一個if 語句)，而不是替換了鏈表里面的某一元素(也就是走的for循環里的第二個if 語句)
image-20201127114314435final?void?treeifyBin(Node[]?tab,?int?hash)?{
??int?n,?index;?Node?e;if?(tab?==?null?||?(n?=?tab.length)???????resize();else?if?((e?=?tab[index?=?(n?-?1)?&?hash])?!=?null)?{
??????TreeNode?hd?=?null,?tl?=?null;do?{
??????????TreeNode?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);
??}
}其實這代碼上面有一段注釋的，這里也帖一下,在table 太小的情況下，使用resize 否則替換指的位置鏈表上的全部Nodes(其實就是替換成紅黑樹)
/**
*?Replaces?all?linked?nodes?in?bin?at?index?for?given?hash?unless
*?table?is?too?small,?in?which?case?resizes?instead.
*/其實這里有一個隱含的意義，就是數組不大的時候，希望通過resize 的方法降低hash 沖突的概率，從而避免鏈表過長降低查詢時間，但是當數組比較大的時候reszie 成本太高，則通過將鏈表轉化成紅黑樹來降低查詢時間
for 循環遍歷鏈表而不是while
這是源代碼里面的一段，上面也解釋過了，這里使用for 循環遍歷鏈表，利用for 循環的index 進行計數，這里進行了刪減
for?(int?binCount?=?0;?;?++binCount)?{????if?((e?=?p.next)?==?null)?{
????????????doSomething();
????????break;
????p?=?e;
}
番外篇
hash 方法的實現方式
static?final?int?hash(Object?key)?{????int?h;
????return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);
}
JDK 1.8 中，是通過 hashCode() 的高 16 位異或低 16 位實現的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度，功效和質量來考慮的，減少系統的開銷，也不會造成因為高位沒有參與下標的計算，從而引起的碰撞
為什么要用異或運算符？ 保證了對象的 hashCode 的 32 位值只要有一位發生改變，整個 hash() 返回值就會改變。盡可能的減少碰撞。
鏈表法導致的鏈表過深問題為什么不用二叉查找樹代替
之所以選擇紅黑樹是為了解決二叉查找樹的缺陷，二叉查找樹在特殊情況下會變成一條線性結構(這就跟原來使用鏈表結構一樣了，造成很深的問題)，遍歷查找會非常慢。
而紅黑樹在插入新數據后可能需要通過左旋，右旋、變色這些操作來保持平衡，引入紅黑樹就是為了查找數據快，解決鏈表查詢深度的問題，我們知道紅黑樹屬于平衡二叉樹，但是為了保持“平衡”是需要付出代價的，但是該代價所損耗的資源要比遍歷線性鏈表要少，所以當長度大于8的時候，會使用紅黑樹，如果鏈表長度很短的話，根本不需要引入紅黑樹，引入反而會慢。
jdk8中對HashMap做了哪些改變
在java 1.8中，如果鏈表的長度超過了8，那么鏈表將轉換為紅黑樹。(桶的數量必須大于64，小于64的時候只會擴容)
發生hash碰撞時，java 1.7 會在鏈表的頭部插入，而java 1.8會在鏈表的尾部插入
在java 1.8中，Entry被Node替代(換了一個馬甲)
Hashmap 的容量大小為什么要求是2n
這里首選要說明一個前提，那就是元素在數組中的位置的計算方式是 tab[i = (n - 1) & hash] 也就是通過對數組大小求模得到的，因為我們知道hash 的計算方式是 ?hashCode() 的高 16 位異或低 16 位實現的，32 位值只要有一位發生改變，整個 hash() 返回值就會改變，也就是說我們的hash 值發生沖突的概率是比較小的，也就是說hash 值是比較隨機的
所以更多的沖突是發生在取模的時候，所以這個時候只要保證了我們的取模運算 (n - 1) & hash，盡量能保證hash 值的特性也就是隨機性。因為我們知道與運算的特點是,兩位同時為“1”，結果才為“1”，否則為0
所以這個時候我們只要 (n - 1) 讓的二進制表示都是一串1，例如"011111" 就可以了，因為安位與1 結果是不變的，也就是可以延續hash 值的散列性
其實到這里就差不多了，然后我們看2n 的表示特點，然后就知道為什么要就hashmap 的大小是 2n了, 2n次方的二進制表示大家肯定都很清楚，2的6次方，就是從右向左 6 個 0，然后第 7 位是 1
image-20201127184124095其實這下我們就知道為什么了，因為只有數組的長度是2的次方了，n-1 的二進制才能盡可能多的是1
總結
以上是生活随笔為你收集整理的hashmap取值_一万六千字的HashMap深度剖析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 如果服务器开机显示NObootable,
- 下一篇： c# 再次尝试 连接失败_修复破裂婚姻，