自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

厲害了！把 HashMap 剖析的只剩渣了！

作者：麥洛
開發(fā) 前端
HashMap并不是全能的，對于一些特殊的情景下的需求官方拓展了一些其他的類來滿足，如線程安全的ConcurrentHashMap、記錄插入順序的LinkHashMap、給key排序的TreeMap等。

[[399567]]

 前言

HashMap是一個非常重要的集合，日常使用也非常的頻繁，同時也是面試重點。本文并不打算講解基礎(chǔ)的使用api，而是深入HashMap的底層，講解關(guān)于HashMap的重點知識。需要讀者對散列表和HashMap有一定的認識。

HashMap本質(zhì)上是一個散列表，那么就離不開散列表的三大問題：散列函數(shù)、哈希沖突、擴容方案;同時作為一個數(shù)據(jù)結(jié)構(gòu)，必須考慮多線程并發(fā)訪問的問題，也就是線程安全。這四大重點則為學(xué)習HashMap的重點，也是HashMap設(shè)計的重點。

HashMap屬于Map集合體系的一部分，同時繼承了Serializable接口可以被序列化，繼承了Cloneable接口可以被復(fù)制。他的的繼承結(jié)構(gòu)如下：

img

HashMap并不是全能的，對于一些特殊的情景下的需求官方拓展了一些其他的類來滿足，如線程安全的ConcurrentHashMap、記錄插入順序的LinkHashMap、給key排序的TreeMap等。

文章內(nèi)容主要講解四大重點：散列函數(shù)、哈希沖突、擴容方案、線程安全，再補充關(guān)鍵的源碼分析和相關(guān)的問題。

本文所有內(nèi)容如若未特殊說明，均為JDK1.8版本。

哈希函數(shù)

哈希函數(shù)的目標是計算key在數(shù)組中的下標。判斷一個哈希函數(shù)的標準是：散列是否均勻、計算是否簡單。

HashMap哈希函數(shù)的步驟：

  1. 對key對象的hashcode進行擾動
  2. 通過取模求得數(shù)組下標

擾動是為了讓hashcode的隨機性更高，第二步取模就不會讓所以的key都聚集在一起，提高散列均勻度。擾動可以看到hash()方法：

  1. static final int hash(Object key) { 
  2.     int h; 
  3.     // 獲取到key的hashcode，在高低位異或運算 
  4.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 
  5. } 

也就是低16位是和高16位進行異或，高16位保持不變。一般的數(shù)組長度都會比較短，取模運算中只有低位參與散列;高位與低位進行異或，讓高位也得以參與散列運算，使得散列更加均勻。具體運算如下圖(圖中為了方便采用8位進行演示，32位同理)：

img

對hashcode擾動之后需要對結(jié)果進行取模。HashMap在jdk1.8并不是簡單使用%進行取模，而是采用了另外一種更加高性能的方法。HashMap控制數(shù)組長度為2的整數(shù)次冪，好處是對hashcode進行求余運算和讓hashcode與數(shù)組長度-1進行位與運算是相同的效果。如下圖：

img

但位與運算的效率卻比求余高得多，從而提升了性能。在擴容運算中也利用到了此特性，后面會講。取模運算的源碼看到putVal()方法，該方法在put()方法中被調(diào)用：

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 
  2.                boolean evict) { 
  3.     ... 
  4.     // 與數(shù)組長度-1進行位與運算，得到下標 
  5.     if ((p = tab[i = (n - 1) & hash]) == null) 
  6.         ... 
  7. } 

完整的hash計算過程可以參考下圖：

img

上面我們提到HashMap的數(shù)組長度為2的整數(shù)次冪，那么HashMap是如何控制數(shù)組的長度為2的整數(shù)次冪的?修改數(shù)組長度有兩種情況：

  1. 初始化時指定的長度
  2. 擴容時的長度增量

先看第一種情況。默認情況下，如未在HashMap構(gòu)造器中指定長度，則初始長度為16。16是一個較為合適的經(jīng)驗值，他是2的整數(shù)次冪，同時太小會頻繁觸發(fā)擴容、太大會浪費空間。如果指定一個非2的整數(shù)次冪，會自動轉(zhuǎn)化成大于該指定數(shù)的最小2的整數(shù)次冪。如指定6則轉(zhuǎn)化為8，指定11則轉(zhuǎn)化為16。結(jié)合源碼來分析，當我們初始化指定一個非2的整數(shù)次冪長度時，HashMap會調(diào)用tableSizeFor()方法：

  1. public HashMap(int initialCapacity, float loadFactor) { 
  2.     ... 
  3.     this.loadFactor = loadFactor; 
  4.     // 這里調(diào)用了tableSizeFor方法 
  5.     this.threshold = tableSizeFor(initialCapacity); 
  6. } 
  7.  
  8. static final int tableSizeFor(int cap) { 
  9.     // 注意這里必須減一 
  10.     int n = cap - 1; 
  11.     n |= n >>> 1; 
  12.     n |= n >>> 2; 
  13.     n |= n >>> 4; 
  14.     n |= n >>> 8; 
  15.     n |= n >>> 16; 
  16.     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 
  17. } 

tableSizeFor()方法的看起來很復(fù)雜，作用是使得最高位1后續(xù)的所有位都變?yōu)?，最后再+1則得到剛好大于initialCapacity的最小2的整數(shù)次冪數(shù)。如下圖(這里使用了8位進行模擬，32位也是同理)：

img

那為什么必須要對cap進行-1之后再進行運算呢?如果指定的數(shù)剛好是2的整數(shù)次冪，如果沒有-1結(jié)果會變成比他大兩倍的數(shù)，如下：

  1. 00100 --高位1之后全變1--> 00111 --加1---> 01000 

第二種改變數(shù)組長度的情況是擴容。HashMap每次擴容的大小都是原來的兩倍，控制了數(shù)組大小一定是2的整數(shù)次冪，相關(guān)源碼如下：

  1. final Node<K,V>[] resize() { 
  2.     ... 
  3.     if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 
  4.                  oldCap >= DEFAULT_INITIAL_CAPACITY) 
  5.             // 設(shè)置為原來的兩倍 
  6.             newThr = oldThr << 1; 
  7.     ... 
  8. } 

小結(jié)

  1. HashMap通過高16位與低16位進行異或運算來讓高位參與散列，提高散列效果;
  2. HashMap控制數(shù)組的長度為2的整數(shù)次冪來簡化取模運算，提高性能;
  3. HashMap通過控制初始化的數(shù)組長度為2的整數(shù)次冪、擴容為原來的2倍來控制數(shù)組長度一定為2的整數(shù)次冪。

哈希沖突解決方案

再優(yōu)秀的hash算法永遠無法避免出現(xiàn)hash沖突。hash沖突指的是兩個不同的key經(jīng)過hash計算之后得到的數(shù)組下標是相同的。解決hash沖突的方式很多，如開放定址法、再哈希法、公共溢出表法、鏈地址法。HashMap采用的是鏈地址法，jdk1.8之后還增加了紅黑樹的優(yōu)化，如下圖：

img

出現(xiàn)沖突后會在當前節(jié)點形成鏈表，而當鏈表過長之后，會自動轉(zhuǎn)化成紅黑樹提高查找效率。紅黑樹是一個查找效率很高的數(shù)據(jù)結(jié)構(gòu)，時間復(fù)雜度為O(logN)，但紅黑樹只有在數(shù)據(jù)量較大時才能發(fā)揮它的優(yōu)勢。關(guān)于紅黑樹的轉(zhuǎn)化，HashMap做了以下限制。

  • 當鏈表的長度>=8且數(shù)組長度>=64時，會把鏈表轉(zhuǎn)化成紅黑樹。
  • 當鏈表長度>=8，但數(shù)組長度<64時，會優(yōu)先進行擴容，而不是轉(zhuǎn)化成紅黑樹。
  • 當紅黑樹節(jié)點數(shù)<=6，自動轉(zhuǎn)化成鏈表。

那就有了以下問題：

為什么需要數(shù)組長度到64才會轉(zhuǎn)化紅黑樹?

當數(shù)組長度較短時，如16，鏈表長度達到8已經(jīng)是占用了最大限度的50%，意味著負載已經(jīng)快要達到上限，此時如果轉(zhuǎn)化成紅黑樹，之后的擴容又會再一次把紅黑樹拆分平均到新的數(shù)組中，這樣非但沒有帶來性能的好處，反而會降低性能。所以在數(shù)組長度低于64時，優(yōu)先進行擴容。

為什么要大于等于8轉(zhuǎn)化為紅黑樹，而不是7或9?

樹節(jié)點的比普通節(jié)點更大，在鏈表較短時紅黑樹并未能明顯體現(xiàn)性能優(yōu)勢，反而會浪費空間，在鏈表較短是采用鏈表而不是紅黑樹。在理論數(shù)學(xué)計算中(裝載因子=0.75)，鏈表的長度到達8的概率是百萬分之一;把7作為分水嶺，大于7轉(zhuǎn)化為紅黑樹，小于7轉(zhuǎn)化為鏈表。紅黑樹的出現(xiàn)是為了在某些極端的情況下，抗住大量的hash沖突，正常情況下使用鏈表是更加合適的。

注意，紅黑樹在jdk1.8之后出現(xiàn)的，jdk1.7采用的是數(shù)組+鏈表模式。

小結(jié)

  1. HashMap采用鏈地址法，當發(fā)生沖突時會轉(zhuǎn)化為鏈表，當鏈表過長會轉(zhuǎn)化為紅黑樹提高效率。
  2. HashMap對紅黑樹進行了限制，讓紅黑樹只有在極少數(shù)極端情況下進行抗壓。

擴容方案

當HashMap中的數(shù)據(jù)越來越多，那么發(fā)生hash沖突的概率也就會越來越高，通過數(shù)組擴容可以利用空間換時間，保持查找效率在常數(shù)時間復(fù)雜度。那什么時候進行擴容?由HashMap的一個關(guān)鍵參數(shù)控制：裝載因子。

裝載因子=HashMap中節(jié)點數(shù)/數(shù)組長度，他是一個比例值。當HashMap中節(jié)點數(shù)到達裝載因子這個比例時，就會觸發(fā)擴容;也就是說，裝載因子控制了當前數(shù)組能夠承載的節(jié)點數(shù)的閾值。如數(shù)組長度是16，裝載因子是0.75，那么可容納的節(jié)點數(shù)是16*0.75=12。裝載因子的數(shù)值大小需要仔細權(quán)衡。裝載因子越大，數(shù)組利用率越高，同時發(fā)生哈希沖突的概率也就越高;裝載因子越小，數(shù)組利用率降低，但發(fā)生哈希沖突的概率也降低了。所以裝載因子的大小需要權(quán)衡空間與時間之間的關(guān)系。在理論計算中，0.75是一個比較合適的數(shù)值，大于0.75哈希沖突的概率呈指數(shù)級別上升，而小于0.75沖突減少并不明顯。HashMap中的裝載因子的默認大小是0.75，沒有特殊要求的情況下，不建議修改他的值。

那么在到達閾值之后，HashMap是如何進行擴容的呢?HashMap會把數(shù)組長度擴展為原來的兩倍，再把舊數(shù)組的數(shù)據(jù)遷移到新的數(shù)組，而HashMap針對遷移做了優(yōu)化：使用HashMap數(shù)組長度是2的整數(shù)次冪的特點，以一種更高效率的方式完成數(shù)據(jù)遷移。

JDK1.7之前的數(shù)據(jù)遷移比較簡單，就是遍歷所有的節(jié)點，把所有的節(jié)點依次通過hash函數(shù)計算新的下標，再插入到新數(shù)組的鏈表中。這樣會有兩個缺點：1、每個節(jié)點都需要進行一次求余計算;2、插入到新的數(shù)組時候采用的是頭插入法，在多線程環(huán)境下會形成鏈表環(huán)。jdk1.8之后進行了優(yōu)化，原因在于他控制數(shù)組的長度始終是2的整數(shù)次冪，每次擴展數(shù)組都是原來的2倍，帶來的好處是key在新的數(shù)組的hash結(jié)果只有兩種：在原來的位置，或者在原來位置+原數(shù)組長度。具體為什么我們可以看下圖：

img

從圖中我們可以看到，在新數(shù)組中的hash結(jié)果，僅僅取決于高一位的數(shù)值。如果高一位是0，那么計算結(jié)果就是在原位置，而如果是1，則加上原數(shù)組的長度即可。這樣我們只需要判斷一個節(jié)點的高一位是1 or 0就可以得到他在新數(shù)組的位置，而不需要重復(fù)hash計算。HashMap把每個鏈表拆分成兩個鏈表，對應(yīng)原位置或原位置+原數(shù)組長度，再分別插入到新的數(shù)組中，保留原來的節(jié)點順序，如下：

img

小結(jié)

  1. 裝載因子決定了HashMap擴容的閾值，需要權(quán)衡時間與空間，一般情況下保持0.75不作改動;
  2. HashMap擴容機制結(jié)合了數(shù)組長度為2的整數(shù)次冪的特點，以一種更高的效率完成數(shù)據(jù)遷移，同時避免頭插法造成鏈表環(huán)。

線程安全

HashMap作為一個集合，主要功能則為CRUD，也就是增刪查改數(shù)據(jù)，那么就肯定涉及到多線程并發(fā)訪問數(shù)據(jù)的情況。并發(fā)產(chǎn)生的問題，需要我們特別關(guān)注。

HashMap并不是線程安全的，在多線程的情況下無法保證數(shù)據(jù)的一致性。舉個例子：HashMap下標2的位置為null，線程A需要將節(jié)點X插入下標2的位置，在判斷是否為null之后，線程被掛起;此時線程B把新的節(jié)點Y插入到下標2的位置;恢復(fù)線程A，節(jié)點X會直接插入到下標2，覆蓋節(jié)點Y，導(dǎo)致數(shù)據(jù)丟失，如下圖：

jdk1.7及以前擴容時采用的是頭插法，這種方式插入速度快，但在多線程環(huán)境下會造成鏈表環(huán)，而鏈表環(huán)會在下一次插入時找不到鏈表尾而發(fā)生死循環(huán)。

那如果結(jié)果數(shù)據(jù)一致性問題呢?解決這個問題有三個方案：

  • 采用Hashtable
  • 調(diào)用Collections.synchronizeMap()方法來讓HashMap具有多線程能力
  • 采用ConcurrentHashMap

前兩個方案的思路是相似的，均是每個方法中，對整個對象進行上鎖。Hashtable是老一代的集合框架，很多的設(shè)計均以及落后，他在每一個方法中均加上了synchronize關(guān)鍵字保證線程安全。

  1. // Hashtable 
  2. public synchronized V get(Object key) {...} 
  3. public synchronized V put(K key, V value) {...} 
  4. public synchronized V remove(Object key) {...} 
  5. public synchronized V replace(K key, V value) {...} 
  6. ... 

第二種方法是返回一個SynchronizedMap對象，這個對象默認每個方法會鎖住整個對象。如下源碼：

img

這里的mutex是什么呢?直接看到構(gòu)造器：

  1. final Object      mutex;        // Object on which to synchronize 
  2. SynchronizedMap(Map<K,V> m) { 
  3.     this.m = Objects.requireNonNull(m); 
  4.     // 默認為本對象 
  5.     mutex = this; 
  6. } 
  7. SynchronizedMap(Map<K,V> m, Object mutex) { 
  8.     this.m = m; 
  9.     this.mutex = mutex; 
  10. } 

可以看到默認鎖的就是本身，效果和Hashtable其實是一樣的。這種簡單粗暴鎖整個對象的方式造成的后果是：

  • 鎖是非常重量級的，會嚴重影響性能。
  • 同一時間只能有一個線程進行讀寫，限制了并發(fā)效率。

ConcurrentHashMap的設(shè)計就是為了解決此問題。他通過降低鎖粒度+CAS的方式來提高效率。簡單來說，ConcurrentHashMap鎖的并不是整個對象，而是一個數(shù)組的一個節(jié)點，那么其他線程訪問數(shù)組其他節(jié)點是不會互相影響，極大提高了并發(fā)效率;同時ConcurrentHashMap讀操作并不需要獲取鎖，如下圖：

img

關(guān)于ConcurrentHashMap和Hashtable的更多內(nèi)容，限于篇幅，我會在另一篇文章講解。那么，使用了上述的三種解決方案是不是絕對線程安全?先觀察下面的代碼：

  1. ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>(); 
  2. map.put("abc","123"); 
  3.  
  4. Thread1: 
  5. if (map.containsKey("abc")){ 
  6.     String s = map.get("abc"); 
  7. } 
  8.  
  9. Thread2: 
  10. map.remove("abc"); 

當Thread1調(diào)用containsKey之后釋放鎖，Thread2獲得鎖并把“abc”移除再釋放鎖，這個時候Thread1讀取到的s就是一個null了，也就出現(xiàn)了問題了。所以ConcurrentHashMap類或者Collections.synchronizeMap()方法或者Hashtable都只能在一定的限度上保證線程安全，而無法保證絕對線程安全。

關(guān)于線程安全，還有一個fast-fail問題，即快速失敗。當使用HashMap的迭代器遍歷HashMap時，如果此時HashMap發(fā)生了結(jié)構(gòu)性改變，如插入新數(shù)據(jù)、移除數(shù)據(jù)、擴容等，那么Iteractor會拋出fast-fail異常，防止出現(xiàn)并發(fā)異常，在一定限度上保證了線程安全。如下源碼：

  1. final Node<K,V> nextNode() { 
  2.     ... 
  3.     if (modCount != expectedModCount) 
  4.         throw new ConcurrentModificationException(); 
  5.    ... 
  6. } 

創(chuàng)建Iteractor對象時會記錄HashMap的modCount變量，每當HashMap發(fā)生結(jié)構(gòu)性改變時，modCount會加1。在迭代時判斷HashMap的modCount和自己保存的expectedModCount是否一致即可判斷是否發(fā)生了結(jié)構(gòu)性改變。

fast-fail異常只能當做遍歷時的一種安全保證，而不能當做多線程并發(fā)訪問HashMap的手段。若有并發(fā)需求，還是需要使用上述的三種方法。

小結(jié)

  1. HashMap并不能保證線程安全，在多線程并發(fā)訪問下會出現(xiàn)意想不到的問題，如數(shù)據(jù)丟失等
  2. HashMap1.8采用尾插法進行擴容，防止出現(xiàn)鏈表環(huán)導(dǎo)致的死循環(huán)問題
  3. 解決并發(fā)問題的的方案有Hashtable、Collections.synchronizeMap()、ConcurrentHashMap。其中最佳解決方案是ConcurrentHashMap
  4. 上述解決方案并不能完全保證線程安全
  5. 快速失敗是HashMap迭代機制中的一種并發(fā)安全保證

源碼解析

關(guān)鍵變量的理解

HashMap源碼中有很多的內(nèi)部變量，這些變量會在下面源碼分析中經(jīng)常出現(xiàn)，首先需要理解這些變量的意義。

  1. // 存放數(shù)據(jù)的數(shù)組 
  2. transient Node<K,V>[] table; 
  3. // 存儲的鍵值對數(shù)目 
  4. transient int size; 
  5. // HashMap結(jié)構(gòu)修改的次數(shù)，主要用于判斷fast-fail 
  6. transient int modCount; 
  7. // 最大限度存儲鍵值對的數(shù)目(threshodl=table.length*loadFactor)，也稱為閾值 
  8. int threshold; 
  9. // 裝載因子，表示可最大容納數(shù)據(jù)數(shù)量的比例 
  10. final float loadFactor; 
  11. // 靜態(tài)內(nèi)部類，HashMap存儲的節(jié)點類型；可存儲鍵值對，本身是個鏈表結(jié)構(gòu)。 
  12. static class Node<K,V> implements Map.Entry<K,V> {...} 

擴容

HashMap源碼中把初始化操作也放到了擴容方法中，因而擴容方法源碼主要分為兩部分：確定新的數(shù)組大小、遷移數(shù)據(jù)。詳細的源碼分析如下，我打了非常詳細的注釋，可選擇查看。擴容的步驟在上述已經(jīng)講過了，讀者可以自行結(jié)合源碼，分析HashMap是如何實現(xiàn)上述的設(shè)計。

  1. final Node<K,V>[] resize() { 
  2.     // 變量分別是原數(shù)組、原數(shù)組大小、原閾值；新數(shù)組大小、新閾值 
  3.     Node<K,V>[] oldTab = table; 
  4.     int oldCap = (oldTab == null) ? 0 : oldTab.length; 
  5.     int oldThr = threshold; 
  6.     int newCap, newThr = 0; 
  7.  
  8.     // 如果原數(shù)組長度大于0 
  9.     if (oldCap > 0) { 
  10.         // 如果已經(jīng)超過了設(shè)置的最大長度(1<<30,也就是最大整型正數(shù)) 
  11.         if (oldCap >= MAXIMUM_CAPACITY) { 
  12.             // 直接把閾值設(shè)置為最大正數(shù) 
  13.             threshold = Integer.MAX_VALUE; 
  14.             return oldTab; 
  15.         } 
  16.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 
  17.                  oldCap >= DEFAULT_INITIAL_CAPACITY) 
  18.             // 設(shè)置為原來的兩倍 
  19.             newThr = oldThr << 1;  
  20.     } 
  21.  
  22.     // 原數(shù)組長度為0，但最大限度不是0，把長度設(shè)置為閾值 
  23.     // 對應(yīng)的情況就是新建HashMap的時候指定了數(shù)組長度 
  24.     else if (oldThr > 0)  
  25.         newCap = oldThr; 
  26.     // 第一次初始化，默認16和0.75 
  27.     // 對應(yīng)使用默認構(gòu)造器新建HashMap對象 
  28.     else {                
  29.         newCap = DEFAULT_INITIAL_CAPACITY; 
  30.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 
  31.     } 
  32.     // 如果原數(shù)組長度小于16或者翻倍之后超過了最大限制長度，則重新計算閾值 
  33.     if (newThr == 0) { 
  34.         float ft = (float)newCap * loadFactor; 
  35.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 
  36.                   (int)ft : Integer.MAX_VALUE); 
  37.     } 
  38.     threshold = newThr; 
  39.  
  40.     @SuppressWarnings({"rawtypes","unchecked"}) 
  41.     // 建立新的數(shù)組 
  42.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 
  43.     table = newTab; 
  44.     if (oldTab != null) { 
  45.         // 循環(huán)遍歷原數(shù)組，并給每個節(jié)點計算新的位置 
  46.         for (int j = 0; j < oldCap; ++j) { 
  47.             Node<K,V> e; 
  48.             if ((e = oldTab[j]) != null) { 
  49.                 oldTab[j] = null; 
  50.                 // 如果他沒有后繼節(jié)點，那么直接使用新的數(shù)組長度取模得到新下標 
  51.                 if (e.next == null) 
  52.                     newTab[e.hash & (newCap - 1)] = e; 
  53.                 // 如果是紅黑樹，調(diào)用紅黑樹的拆解方法 
  54.                 else if (e instanceof TreeNode) 
  55.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 
  56.                 // 新的位置只有兩種可能：原位置，原位置+老數(shù)組長度 
  57.                 // 把原鏈表拆成兩個鏈表，然后再分別插入到新數(shù)組的兩個位置上 
  58.                 // 不用多次調(diào)用put方法 
  59.                 else {  
  60.                     // 分別是原位置不變的鏈表和原位置+原數(shù)組長度位置的鏈表 
  61.                     Node<K,V> loHead = null, loTail = null; 
  62.                     Node<K,V> hiHead = null, hiTail = null; 
  63.                     Node<K,V> next; 
  64.                     // 遍歷老鏈表，判斷新增判定位是1or0進行分類 
  65.                     do { 
  66.                         next = e.next; 
  67.                         if ((e.hash & oldCap) == 0) { 
  68.                             if (loTail == null) 
  69.                                 loHead = e; 
  70.                             else 
  71.                                 loTail.next = e; 
  72.                             loTail = e; 
  73.                         } 
  74.                         else { 
  75.                             if (hiTail == null) 
  76.                                 hiHead = e; 
  77.                             else 
  78.                                 hiTail.next = e; 
  79.                             hiTail = e; 
  80.                         } 
  81.                     } while ((e = next) != null); 
  82.                     // 最后賦值給新的數(shù)組 
  83.                     if (loTail != null) { 
  84.                         loTail.next = null; 
  85.                         newTab[j] = loHead; 
  86.                     } 
  87.                     if (hiTail != null) { 
  88.                         hiTail.next = null; 
  89.                         newTab[j + oldCap] = hiHead; 
  90.                     } 
  91.                 } 
  92.             } 
  93.         } 
  94.     } 
  95.     // 返回新數(shù)組 
  96.     return newTab; 
  97. } 

添加數(shù)值

調(diào)用put()方法添加鍵值對，最終會調(diào)用putVal()來真正實現(xiàn)添加邏輯。代碼解析如下：

  1. public V put(K key, V value) { 
  2.     // 獲取hash值，再調(diào)用putVal方法插入數(shù)據(jù) 
  3.     return putVal(hash(key), key, value, false, true); 
  4. } 
  5.  
  6. // onlyIfAbsent表示是否覆蓋舊值，true表示不覆蓋，false表示覆蓋，默認為false 
  7. // evict和LinkHashMap的回調(diào)方法有關(guān)，不在本文討論范圍 
  8. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 
  9.                boolean evict) { 
  10.  
  11.     // tab是HashMap內(nèi)部數(shù)組，n是數(shù)組的長度，i是要插入的下標，p是該下標對應(yīng)的節(jié)點 
  12.     Node<K,V>[] tab; Node<K,V> p; int n, i; 
  13.  
  14.     // 判斷數(shù)組是否是null或者是否是空，若是，則調(diào)用resize()方法進行擴容 
  15.     if ((tab = table) == null || (n = tab.length) == 0) 
  16.         n = (tab = resize()).length; 
  17.  
  18.     // 使用位與運算代替取模得到下標 
  19.     // 判斷當前下標是否是null，若是則創(chuàng)建節(jié)點直接插入，若不是，進入下面else邏輯 
  20.     if ((p = tab[i = (n - 1) & hash]) == null) 
  21.         tab[i] = newNode(hash, key, value, null); 
  22.     else { 
  23.  
  24.         // e表示和當前key相同的節(jié)點，若不存在該節(jié)點則為null 
  25.         // k是當前數(shù)組下標節(jié)點的key 
  26.         Node<K,V> e; K k; 
  27.  
  28.         // 判斷當前節(jié)點與要插入的key是否相同，是則表示找到了已經(jīng)存在的key 
  29.         if (p.hash == hash && 
  30.             ((k = p.key) == key || (key != null && key.equals(k)))) 
  31.             e = p; 
  32.         // 判斷該節(jié)點是否是樹節(jié)點，如果是調(diào)用紅黑樹的方法進行插入 
  33.         else if (p instanceof TreeNode) 
  34.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 
  35.         // 最后一種情況是直接鏈表插入 
  36.         else { 
  37.             for (int binCount = 0; ; ++binCount) { 
  38.                 if ((e = p.next) == null) { 
  39.                     p.next = newNode(hash, key, value, null); 
  40.                     // 長度大于等于8時轉(zhuǎn)化為紅黑樹 
  41.                     // 注意，treeifyBin方法中會進行數(shù)組長度判斷， 
  42.                     // 若小于64，則優(yōu)先進行數(shù)組擴容而不是轉(zhuǎn)化為樹 
  43.                     if (binCount >= TREEIFY_THRESHOLD - 1)  
  44.                         treeifyBin(tab, hash); 
  45.                     break; 
  46.                 } 
  47.                 // 找到相同的直接跳出循環(huán) 
  48.                 if (e.hash == hash && 
  49.                     ((k = e.key) == key || (key != null && key.equals(k)))) 
  50.                     break; 
  51.                 p = e; 
  52.             } 
  53.         } 
  54.  
  55.         // 如果找到相同的key節(jié)點，則判斷onlyIfAbsent和舊值是否為null 
  56.         // 執(zhí)行更新或者不操作，最后返回舊值 
  57.         if (e != null) {  
  58.             V oldValue = e.value; 
  59.             if (!onlyIfAbsent || oldValue == null) 
  60.                 e.value = value; 
  61.             afterNodeAccess(e); 
  62.             return oldValue; 
  63.         } 
  64.     } 
  65.  
  66.     // 如果不是更新舊值，說明HashMap中鍵值對數(shù)量發(fā)生變化 
  67.     // modCount數(shù)值+1表示結(jié)構(gòu)改變 
  68.     ++modCount; 
  69.     // 判斷長度是否達到最大限度，如果是則進行擴容 
  70.     if (++size > threshold) 
  71.         resize(); 
  72.     // 最后返回null（afterNodeInsertion是LinkHashMap的回調(diào)） 
  73.     afterNodeInsertion(evict); 
  74.     return null; 
  75. } 

代碼中關(guān)于每個步驟有了詳細的解釋，這里來總結(jié)一下：

  1. 總體上分為兩種情況：找到相同的key和找不到相同的key。找了需要判斷是否更新并返回舊value，沒找到需要插入新的Node、更新節(jié)點數(shù)并判斷是否需要擴容。
  2. 查找分為三種情況：數(shù)組、鏈表、紅黑樹。數(shù)組下標i位置不為空且不等于key，那么就需要判斷是否樹節(jié)點還是鏈表節(jié)點并進行查找。
  3. 鏈表到達一定長度后需要擴展為紅黑樹，當且僅當鏈表長度>=8且數(shù)組長度>=64。

最后畫一張圖總體再加深一下整個流程的印象：

img

其他問題

為什么jdk1.7以前控制數(shù)組的長度為素數(shù)，而jdk1.8之后卻采用的是2的整數(shù)次冪?

答：素數(shù)長度可以有效減少哈希沖突;JDK1.8之后采用2的整數(shù)次冪是為了提高求余和擴容的效率，同時結(jié)合高低位異或的方法使得哈希散列更加均勻。

為何素數(shù)可以減少哈希沖突?若能保證key的hashcode在每個數(shù)字之間都是均勻分布，那么無論是素數(shù)還是合數(shù)都是相同的效果。例如hashcode在1~20均勻分布，那么無論長度是合數(shù)4，還是素數(shù)5，分布都是均勻的。而如果hashcode之間的間隔都是2，如1,3,5...,那么長度為4的數(shù)組，位置2和位置4兩個下標無法放入數(shù)據(jù)，而長度為5的數(shù)組則沒有這個問題。長度為合數(shù)的數(shù)組會使間隔為其因子的hashcode聚集出現(xiàn)，從而使得散列效果降低。

為什么插入HashMap的數(shù)據(jù)需要實現(xiàn)hashcode和equals方法?對這兩個方法有什么要求?

答：通過hashcode來確定插入下標，通過equals比較來尋找數(shù)據(jù);兩個相等的key的hashcode必須相等，但擁有相同的hashcode的對象不一定相等。

這里需要區(qū)分好他們之間的區(qū)別：hashcode就像一個人的名，相同的人名字肯定相等，但是相同的名字不一定是同個人;equals比較內(nèi)容是否相同，一般由對象覆蓋重寫，默認情況下比較的是引用地址;“==”引用隊形比較的是引用地址是否相同，值對象比較的是值是否相同。

HashMap中需要使用hashcode來獲取key的下標，如果兩個相同的對象的hashcode不同，那么會造成HashMap中存在相同的key;所以equals返回相同的key他們的hashcode一定要相同。HashMap比較兩個元素是否相同采用了三種比較方法結(jié)合：p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))) 。

最后

關(guān)于HashMap的內(nèi)容很難在一篇文章講完，他的設(shè)計到的內(nèi)容非常多，如線程安全的設(shè)計可以延伸到ConcurrentHashMap與Hashtable，這兩個類與HashMap的區(qū)別以及內(nèi)部設(shè)計均非常重要，這些內(nèi)容我將在另外的文章做補充。最后，希望文章對你有幫助。

 

責任編輯：姜華 來源： 愛寫B(tài)ug的麥洛
HashMap 散列函數(shù)哈希沖突
相關(guān)推薦

2018-04-11 14:30:33

2018-05-14 22:58:14

戴爾

2017-02-23 08:00:04

智能語音Click

2021-03-01 12:06:12

Nginx命令Linux

2023-05-06 06:47:46

Bing聊天機器人

2020-06-08 17:35:27

Redis集群互聯(lián)網(wǎng)

2021-11-01 07:50:44

TomcatWeb應(yīng)用

2021-12-27 07:59:50

ECMAScript JSON模塊Node.js

2022-01-11 12:13:33

JavaScript編程語言

2019-02-20 10:43:40

Android

2021-09-17 12:18:53

NginxJavaScript前端

2017-02-20 10:17:53

華為

2019-06-17 08:30:09

TCPIP通信協(xié)議

2015-07-21 16:37:30

傳統(tǒng)互聯(lián)網(wǎng)

2022-04-08 08:11:28

Python代碼

2020-03-10 13:35:23

Gihub搜索開源

2021-06-03 09:30:30

Python操作注冊表regedit

2020-04-27 09:40:43

開源項目 Bug

2019-11-25 21:53:48

代碼算法BUG

2022-05-03 23:44:21

Python動態(tài)鏈接庫Ctypes
點贊
收藏

51CTO技術(shù)棧公眾號