深入淺出HashMap

Map

map是一種 key/value組織的數(shù)據(jù)結(jié)構(gòu)。在Java中Map是一個(gè)接口類，其實(shí)現(xiàn)類比較常用的有：
HashMap, LinkedHashMap, TreeMap。

HashMap

HashMap在Map家族中用的最多的集合類，他是非線程安全的，允許key為null，可以插入相同的key值，但是會覆蓋value值。內(nèi)部數(shù)據(jù)結(jié)構(gòu)有數(shù)組，單鏈表，紅黑樹。

什么是HashMap

HashMap是Map接口的實(shí)現(xiàn)類，其內(nèi)部成員機(jī)構(gòu)如下


image
  • 其中table是個(gè)Node類型數(shù)組，是HashMap最重要的成員，用來存儲每個(gè)節(jié)點(diǎn)數(shù)據(jù)。(其實(shí)Node是單鏈表數(shù)據(jù)結(jié)構(gòu))
  • entrySet是用來緩存Node節(jié)點(diǎn)數(shù)據(jù)的，用來遍歷訪問的
  • loadFactor是負(fù)載因子，用來表示table的填滿程度 默認(rèn)值為0.75
  • threshold 值為capacity * loadFactor 當(dāng)table節(jié)點(diǎn)個(gè)數(shù)大于threshold值的時(shí)候，就需要resize了

HashMap的工作原理

先從一段簡單的代碼說起

public static void main(String[] args) {
    Map<Integer, String> integerStringMap = new HashMap<>();
    integerStringMap.put(1, "a");
    integerStringMap.put(2, "b");
    integerStringMap.put(3, "h");
    integerStringMap.put(6, "i");
    integerStringMap.put(17, "j");
    integerStringMap.put(49, "j");
    integerStringMap.put(25, "c");    
    System.out.println(integerStringMap.toString());
}

該段代碼簡單的使用HashMap存儲<Integer,String>值，下圖為內(nèi)部存儲結(jié)構(gòu)


HashMap

其中table只要插入一個(gè)值 其length(capacity)就會設(shè)置為16(該值可以自己設(shè)定，不設(shè)置則默認(rèn)為16)，當(dāng)table size值超過 capacity * loadFactor(16 * 0.75 = 12) 時(shí) table就會開始resize，然后重新組織數(shù)據(jù)并插入新的節(jié)點(diǎn)?？梢酝ㄟ^以下代碼，驗(yàn)證以上說法是否正確

integerStringMap.put(4, "l");
integerStringMap.put(5, "l");
integerStringMap.put(7, "l");
integerStringMap.put(8, "l");
integerStringMap.put(9, "l");
integerStringMap.put(10, "l");

再觀察table 數(shù)組的length，同時(shí)threshold的值也相應(yīng)變了，至于為啥某些元素index變了 在下面內(nèi)容會詳細(xì)講解。


image

HashMap put方法工作原理

先從JDK8源碼說起。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
   Node<K,V>[] tab; Node<K,V> p; int n, i;
   // 首次插入就將length初始化為16(DEFAULT_INITIAL_CAPACITY)
   if ((tab = table) == null || (n = tab.length) == 0)
       n = (tab = resize()).length;
   // index 使用(n-1) & hash 取代模運(yùn)算[hash % n] n為2的n次冪
   if ((p = tab[i = (n - 1) & hash]) == null) // table對應(yīng)的位置沒有元素,則放入
       tab[i] = newNode(hash, key, value, null);
   else {  // 沖突 開始解決沖突
       Node<K,V> e; K k;
       // 確定插入節(jié)點(diǎn)與當(dāng)前idx相同節(jié)點(diǎn)是否"相等"
       if (p.hash == hash &&
           ((k = p.key) == key || (key != null && key.equals(k))))
           // 取代原來的node,value值之后設(shè)定
           e = p;
       // 使用紅黑樹組織node(沖突的第一個(gè)節(jié)點(diǎn)就是樹節(jié)點(diǎn)(Hash table中的)
       else if (p instanceof TreeNode)
           e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
       else {
           for (int binCount = 0; ; ++binCount) {
               // 找到單鏈表最后一個(gè)節(jié)點(diǎn)
               if ((e = p.next) == null) {
                   // 插入新的節(jié)點(diǎn)
                   p.next = newNode(hash, key, value, null);
                   // 如果單鏈表節(jié)點(diǎn)個(gè)數(shù)超過TREEIFY_THRESHOLD - 1則將單鏈表轉(zhuǎn)為紅黑樹
                   if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                       treeifyBin(tab, hash);
                   break;
               }
               // 遍歷單鏈表過程中找到key相同的node 則break
               if (e.hash == hash &&
                   ((k = e.key) == key || (key != null && key.equals(k))))
                   break;
               p = e;
           }
       }
       // 判定是否需要替換value值
       if (e != null) { // existing mapping for key
           V oldValue = e.value;
           if (!onlyIfAbsent || oldValue == null)
               e.value = value;
           // LinkedHashMap中使用
           afterNodeAccess(e);
           return oldValue;
       }
   }
   // table數(shù)組中元素個(gè)數(shù)
   ++modCount;
   // 需要擴(kuò)容
   if (++size > threshold)
       resize();
   // LinkedHashMap回掉方法
   afterNodeInsertion(evict);
   return null;
}

上述方法就是HashMap插入節(jié)點(diǎn)的代碼，主要有以下幾個(gè)步驟

  1. 如果是第一個(gè)元素則 resize 初始化table
  2. 找到插入節(jié)點(diǎn)的index值，即bucket在table中的索引值
  3. 判斷當(dāng)前bucket節(jié)點(diǎn)是否有值，沒有則直接插入，有則進(jìn)行下面步驟，假設(shè)新節(jié)點(diǎn)為a，bucket處的原節(jié)點(diǎn)為b
  4. 首先判斷a,b是否"相等",如果相等直接判斷是否需要替換value值，如果不相等則進(jìn)行下面步驟
  5. 如果index處節(jié)點(diǎn)是樹TreeNode類型則插入到紅黑樹中，如果不是進(jìn)行下面步驟
  6. 遍歷以index處節(jié)點(diǎn)為頭節(jié)點(diǎn)的單鏈表，遍歷中如果遇到"相等"的節(jié)點(diǎn)，則停止遍歷，然后判斷是否需要替換value值
  7. 遍歷到單鏈表結(jié)尾時(shí)(node->next == null)，判斷是否需要將單鏈表轉(zhuǎn)為樹(單鏈表節(jié)點(diǎn)個(gè)數(shù)超過8則需要轉(zhuǎn)位樹存儲)，若沒有超過，則插入到單鏈表結(jié)尾
  8. 插入后判斷

注意

以上說的“相等”是 hash值以及key的值或者equals都相等
e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))

當(dāng)兩個(gè)Key對象hashCode相同會發(fā)生什么

當(dāng)兩個(gè)key對象hashCode相同時(shí)，HashMap會將2個(gè)node放在同一個(gè)bucket里，新加的就插入到單鏈表后面(節(jié)點(diǎn)個(gè)數(shù)<8)或者紅黑樹中

兩個(gè)相同hashCode的key怎么取value

當(dāng)2個(gè)相同hashCode的key去獲取values時(shí)，HashMap首先會根據(jù)hashCode值進(jìn)行index獲取node的bucket位置，即定位到bucket的首節(jié)點(diǎn)，然后：如果是紅黑樹，則遍歷樹根據(jù)key.equals來定位value值；如果是單鏈表，原理一致，只是遍歷的是單鏈表。具體可以查看源碼。

HashMap怎么resize

當(dāng)table.size大于threshold值時(shí)，HashMap就會進(jìn)行一次resize操作。先看resize的代碼，然后再分析其流程

final Node<K,V>[] resize() {
   // 保留原來的數(shù)據(jù)
   Node<K,V>[] oldTab = table;
   int oldCap = (oldTab == null) ? 0 : oldTab.length;
   int oldThr = threshold;
   int newCap, newThr = 0;
   // 非空
   if (oldCap > 0) {
       // 長度已經(jīng)最大
       if (oldCap >= MAXIMUM_CAPACITY) {
           threshold = Integer.MAX_VALUE;
           return oldTab;
       }
       // 雙倍當(dāng)前數(shù)組length
       else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
           newThr = oldThr << 1; // double threshold 擴(kuò)大大小為原來的2倍
   }
   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); // 12
   }
   if (newThr == 0) {
       float ft = (float)newCap * loadFactor;
       newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                 (int)ft : Integer.MAX_VALUE);
   }
   threshold = newThr; // 設(shè)置新的 threshold
   @SuppressWarnings({"rawtypes","unchecked"})
       Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
   table = newTab;  // 當(dāng)前表指向新的空表 開始復(fù)制原先的數(shù)據(jù) 從oldTab
   if (oldTab != null) {
       for (int j = 0; j < oldCap; ++j) {
           Node<K,V> e;
           if ((e = oldTab[j]) != null) {
               oldTab[j] = null;
               // bucket只有一個(gè)節(jié)點(diǎn)直接將老節(jié)點(diǎn)插入到新的table中，注意要rehash的
               if (e.next == null)
                   newTab[e.hash & (newCap - 1)] = e;
               // 判斷是不是樹節(jié)點(diǎn)
               else if (e instanceof TreeNode)
                   ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
               else { // preserve order
                   // 下面處理目的 將bucket中的節(jié)點(diǎn)轉(zhuǎn)移到新的hash table上
                   // loHead, loTail用來構(gòu)成(e.hash & oldCap == 0)低oldCap位的節(jié)點(diǎn)單鏈表, 結(jié)果為newTab[j] = loHead
                   // hiHead, hiTail用來構(gòu)成(e.hash & oldCap != 0)高oldCap位的節(jié)點(diǎn)單鏈表, 結(jié)果為newTab[j + oldCap] = hiHead
                   // eg: oldCap為16, 則newCap為32, 假設(shè)index為1的bucket上有有1,17,49,65三個(gè)節(jié)點(diǎn)
                   // 則1. 1 & 16 = 0, 65 & 16 = 0則loHead -> 1 -> 65 <- loTail -> null, 結(jié)果為newTab[1] = loHead
                   // 2. 17 & 16 != 0, 49 & 16 != 0,則 hiHead -> 17 -> 49 <- hiTail -> null, 結(jié)果為newTab[17(1+16)] = hiHead
                   Node<K,V> loHead = null, loTail = null;
                   Node<K,V> hiHead = null, hiTail = null;
                   Node<K,V> 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;
                   }
               }
           }
       }
   }
   return newTab;
}

就以文章中例子代碼為例，下圖為oldTable -> newTable節(jié)點(diǎn)的轉(zhuǎn)移過程


image

參考文獻(xiàn)

Java 8系列之重新認(rèn)識HashMap
Java HashMap工作原理及實(shí)現(xiàn)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容