HashMap詳解

HashMap詳解

HashMap相關介紹

HashMap是Java中的比較常見的集合，主要存放的是鍵值對，以key-value的形式存儲，不是線程安全的。它裡面的存儲的key和value可以為null值，但是key只允許有一個null值。HashMap是無序的，無法保證裡面存儲的鍵值對的有序性。jdk1.8之前的版本底層採用的是數組+鏈表的方式組成，jdk1.8之後採用的是數組+鏈表+紅黑樹的方式。數組具有查詢效率高、插入、刪除效率低，鏈表具有查詢效率低，但是插入、刪除效率高，HashMap採用這兩種方式的結構，可以保證查詢、插入、刪除效率都得到保證。

HashMap數據結構

jdk1.8之後的版本使用數據+鏈表+紅黑樹的方式作為底層的數據結構，在鏈表長度大於閾值8之後，如果數組長度大於64時，才會轉換成紅黑樹進行存儲。閾值預設是8。下麵我們介紹一下HashMap的設值過程：

1. 我們在調用HashMap的put設值時，首先會對值進行hash操作。

   public V put(K key, V value) {
   	return putVal(hash(key), key, value, false, true);
   }
   

2. 判斷索引的數組位置是否為空，如果為空，則進行初始化，分配空間，進行擴容。

   if ((tab = table) == null || (n = tab.length) == 0)
   	n = (tab = resize()).length;
   

3. 判斷這個位置是否有值，如果沒有值，則創建一個新的節點。

   if ((p = tab[i = (n - 1) & hash]) == null)
   	tab[i] = newNode(hash, key, value, null);
   

4. 如果這個位置有值，則需要解決衝突

   • 首先判斷鏈表的頭，代碼中的p，先判斷hash值是否和我們的相同，如果hash值相同的話，在判斷具體數值，如果相同，則先記錄該位置，也就是代碼中的e。

     Node<K,V> e; K k;
     if (p.hash == hash &&
       ((k = p.key) == key || (key != null && key.equals(k))))
       e = p;
     

   • 如果不同，那就需要遍歷鏈表，jdk1.8之後的做了優化，鏈表太長時，會轉換成紅黑樹，如果是TreeNode,則調用TreeNode的方法進行插入，此時就是採用的紅黑樹作為數據結構。

     else if (p instanceof TreeNode)
       e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
     

   • 如果不是TreeNode,則是用迴圈的方式遍歷鏈表，如果有相同的鏈表節點，則記錄該節點,代碼中的e，如果沒有相同的鏈表節點，則e為null,此時會創建一個新的Node，插入在鏈表最後。

     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;
     }
     

   • 最後判斷e是不是null,e代表的是是否存在相同的值，存在，則記錄的位置，不存在，則為null,如果存在，則會直接更新e記錄的位置的值。

     if (e != null) { // existing mapping for key
         V oldValue = e.value;
         if (!onlyIfAbsent || oldValue == null)
             e.value = value;
         afterNodeAccess(e);
         return oldValue;
     }
     

   • 在迴圈遍歷鏈表時，如果該節點是個新的節點，插入在鏈表最後，此時會判斷鏈表的長度是否大於TREEIFY_THRESHOLD - 1,預設是8，如果大於8,則會調用轉換成紅黑樹的方法，但是，方法裡面還會判斷數組長度是否大於MIN_TREEIFY_CAPACITY,預設是64,如果大於，則轉換成紅黑樹。

     if ((e = p.next) == null) {
         p.next = newNode(hash, key, value, null);
         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
             treeifyBin(tab, hash);
         break;
     }
     

     int n, index; Node<K,V> e;
     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
         resize();
     

關註微信公眾號「平哥技術站」, 每日更新，在手機上閱讀所有教程，隨時隨地都能學習。

原文鏈接:https://monkey.blog.xpyvip.top/archives/hashmap-xiang-jie