­

談談集合.Map

  • 2020 年 3 月 12 日
  • 筆記

本文來談談我們平時使用最多的HashMap。

1. 簡介

HashMap是我們在開發過程中用的最多的一個集合結構，沒有之一。HashMap實現了Map介面，內部存放Key-Value鍵值對，支援泛型。在JDK1.8以前，HashMap內部是以數組加鏈表的結構維護鍵值對數據。在JDK1.8中，HashMap以數組、鏈表加紅黑樹的結構維護數據，當鏈表長度大於8以後會自動轉為紅黑樹提升數據增刪改查的效率。另外JDK還提供了很多Map介面的其他實現，比較常用的有LinkedHashMap、TreeMap以及已經淘汰但是經常拿來和HashMap做對比的HashTable。他們的繼承關係如下。

值得注意的是HashMap不是執行緒安全的，所以JDK又提供了ConcurrentHashMap和SynchronizedMap等，可以在多執行緒環境下使用。

2. HashMap中一些常量介紹

    // Hash表的默認初始化長度，默認是16      static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;      //Hash表的最大長度      static final int MAXIMUM_CAPACITY = 1 << 30;      //默認負載因子，負載因子的大小可以平衡時間和空間的關係，如果負載因子較大，比較節省空間，但是增加了Hash碰撞的幾率      //如果負載因子較小，resize會發生的比較頻繁，空間利用率不高，但是減少了Hash碰撞的概率。      static final float DEFAULT_LOAD_FACTOR = 0.75f;      //當桶上面的鏈表長度大於8時，鏈表會轉換成樹結構      static final int TREEIFY_THRESHOLD = 8;      static final int UNTREEIFY_THRESHOLD = 6;      static final int MIN_TREEIFY_CAPACITY = 64        transient Node<K,V>[] table;        /**       * Holds cached entrySet(). Note that AbstractMap fields are used       * for keySet() and values().       */      transient Set<Map.Entry<K,V>> entrySet;        /**       * The number of key-value mappings contained in this map.       */      transient int size;        /**       * The number of times this HashMap has been structurally modified       * Structural modifications are those that change the number of mappings in       * the HashMap or otherwise modify its internal structure (e.g.,       * rehash).  This field is used to make iterators on Collection-views of       * the HashMap fail-fast.  (See ConcurrentModificationException).       */      transient int modCount;        /**       * The next size value at which to resize (capacity * load factor).       *       * @serial       */      // (The javadoc description is true upon serialization.      // Additionally, if the table array has not been allocated, this      // field holds the initial array capacity, or zero signifying      // DEFAULT_INITIAL_CAPACITY.)      int threshold;        /**       * The load factor for the hash table.       *       * @serial       */      final float loadFactor;

2. 確定Hash桶位置分析

HashMap在將鍵值對放入Map中的第一步是找出這個鍵值對在Hash表中的位置。JDK1.8中HashMap的做法是：

    //第一步:獲得key的hashCode，並加入擾動函數，增加hash值的隨機性，減少衝突。      static final int hash(Object key) {          int h;          return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);      }        //其中n是Hash表的長度，相當於hash%n      (n - 1) & hash

總的來說，HashMap在計算元素在桶中位置的演算法很簡單：就是根據key的Hashcode值，加入擾動函數之後再跟Hasn表的長度取余就得到這個鍵值對在Hash表中的位置。這邊加入擾動函數的做法是：將key本身的Hashcode值右移16位，再跟自身進行異或。自己的高半區和低半區做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機性。

Peter Lawley在文章《An introduction to optimising a hashing strategy》里做了一個實驗：他隨機選取了352個字元串，在他們散列值完全沒有衝突的前提下，對它們做低位掩碼，取數組下標。結果顯示，當HashMap數組長度為512的時候，也就是用掩碼取低9位的時候，在沒有擾動函數的情況下，發生了103次碰撞，接近30%。而在使用了擾動函數之後只有92次碰撞。碰撞減少了將近10%。看來擾動函數確實還是有功效的。見本文

3. put方法分析

確定好鍵值對（Entry）的位置後，HashMap進行put操作。下面以JDK1.8的程式碼做下分析。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                 boolean evict) {      Node<K,V>[] tab; Node<K,V> p; int n, i;      //step1：判斷Hash表是否為空，如果為空就創建一個長度為16的Hash表      if ((tab = table) == null || (n = tab.length) == 0)          n = (tab = resize()).length;      //step2：如果這Hash桶位置上沒數據，直接在這個位置上創建      if ((p = tab[i = (n - 1) & hash]) == null)          tab[i] = newNode(hash, key, value, null);      else {          Node<K,V> e; K k;          //step3:如果這個Key在HashMap中已經存在，直接覆蓋這個key的值          if (p.hash == hash &&              ((k = p.key) == key || (key != null && key.equals(k))))              e = p;          //step4:以紅黑樹的方式加入該鍵值對          else if (p instanceof TreeNode)              e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);          else {              //step5:這個桶上是鏈表，遍歷鏈表，如果在遍歷過程中發現這個key已經存在，直接覆蓋這個key的值返回              //      如果發現這個key不存在，直接在鏈表尾部加入這個鍵值對，並判斷鏈表長度是否大於8，如果長度大於8轉為紅黑樹              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;              }          }          //step6：如果key之前在HashMap中存在，用新值覆蓋舊值，並返回舊值          if (e != null) { // existing mapping for key              V oldValue = e.value;              if (!onlyIfAbsent || oldValue == null)                  e.value = value;              afterNodeAccess(e);              return oldValue;          }      }      ++modCount;      //如果size大於閾值就行進擴容。      if (++size > threshold)          resize();      afterNodeInsertion(evict);      return null;  }

總結一下HashMap進行put元素的過程：
step1：會先判斷Hash表是否創建，如果沒被創建（也就是在創建HashMap時沒指定任何參數），就創建一個長度為16的Hash表，並將閾值設置為12；
step2：根據key的hashCode值計算出在Hash表中的位置，如果這個位置上沒任何元素，直接在這個位置上創建元素，然後將size++後就結束了。如果這個位置上有元素進入步驟3.
step3：如果這個位置上有元素，判斷這個元素是否和新加入元素的key相等（判斷的標準是key的hash值相等，並且通過equals方法比較也相等），如果相等用新元素的value覆蓋舊元素的value，並且返回舊元素的值，方法結束，否則進入步驟4；
step4：判斷這個位置上是不是一個樹形結構，如果是樹形結構，按紅黑樹的形式加入元素，然後返回；否則進入步驟5；
step5：進入步驟5的話，那麼這兒位置上一定是一個鏈表結構，遍歷鏈表，如果在遍歷過程中發現這個key已經存在，直接覆蓋這個key的值返回，如果發現這個key不存在，直接在鏈表尾部加入這個鍵值對，並判斷鏈表長度是否大於8，如果長度大於8轉為紅黑樹。

至此，整個put過程結束。順便提下，HashMap是允許元素的鍵值為null，並且會存放在Hash表的第一個位置。

4. get方法分析

HashMap的get方法比較簡單，源程式碼如下:

final Node<K,V> getNode(int hash, Object key) {      Node<K,V>[] tab; Node<K,V> 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<K,V>)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;  }

如果hash表為空，或者hash值所在的桶位置上沒有值則直接返回null。否則就通過比較key的hash值和equals方法，兩者都相等就返回對應的value值。

5. 擴容機制分析

當元素向HashMap容器中添加元素的時候，會判斷當前元素的個數，如果當前元素的個數大於等於閾值時，即當前數組table的長度載入因子就要進行自動擴容。

由於HashMap的底層數據結構是「鏈表散列」，即數組和鏈表的組合，而數組是無法自動擴容的，所以只能是換一個更大的數組去裝填以前的元素和將要添加的新元素。

HashMap的擴容過程是這樣的：首先會創建一個大小是原來一倍的數組（如果原來的數組大小已經達到的最大值，那麼不會再創建新的數組，只是將閾值改成最大值然後返回原數組），然後將舊數組中的元素一個個複製到新數組中。從整體上看，擴容就是這麼一個簡單的過程，只不過HashMap在重新計算元素在新數組中位置的時候針對不同的元素採取了些優化措施。比如原來舊數組中每個位置上的值是null值就直接跳過了；如果原來位置上的值是單個值，先通過這個值的hashcode值取余新數組的長度，得出在新數組中的位置，然後再賦值過去；如果原來位置上是一個紅黑樹結構，就調用split（）方法進行拆分放置（這塊程式碼沒仔細看過）；如果是鏈表結構，那麼元素在新數組中的位置要麼和之前一樣，要麼就是現在的位置加上舊數組的長度。

6. 執行緒安全相關

大家都知道HashMap是執行緒非安全的。下面的情況會產生執行緒安全問題。

  1. put的時候導致的多執行緒數據不一致
    比如有兩個執行緒A和B，首先A希望插入一個key-value對到HashMap中，首先計算記錄所要落到的 hash桶的索引坐標，然後獲取到該桶裡面的鏈表頭結點，此時執行緒A的時間片用完了，而此時執行緒B被調度得以執行，和執行緒A一樣執行，只不過執行緒B成功將記錄插到了桶裡面，假設執行緒A插入的記錄計算出來的 hash桶索引和執行緒B要插入的記錄計算出來的 hash桶索引是一樣的，那麼當執行緒B成功插入之後，執行緒A再次被調度運行時，它依然持有過期的鏈表頭但是它對此一無所知，以至於它認為它應該這樣做，如此一來就覆蓋了執行緒B插入的記錄，這樣執行緒B插入的記錄就憑空消失了，造成了數據不一致的行為。
  2. resize而引起死循環（JDK1.8已經不會出現該問題）
    這種情況發生在JDK1.7 中HashMap自動擴容時，當2個執行緒同時檢測到元素個數超過 數組大小 × 負載因子。此時2個執行緒會在put()方法中調用了resize()，兩個執行緒同時修改一個鏈表結構會產生一個循環鏈表（JDK1.7中，會出現resize前後元素順序倒置的情況）。接下來再想通過get()獲取某一個元素，就會出現死循環。具體產生死循環的原因請看這篇部落格

執行緒安全的Map

  • Hashtable
  • ConcurrentHashMap
  • Synchronized Map

ConcurrentHashMap這邊先不介紹，後面會專門寫文章介紹。SynchronizedMap是集合工具類生成的並發類，其實現執行緒安全的原理是在每個方法上加了synchronized。

下面介紹下HashMap和HashTable的區別。

1.HashTable的方法是同步的，在方法的前面都有synchronized來同步，HashMap未經同步，所以在多執行緒場合要手動同步.
2.HashTable不允許null值(key和value都不可以) ,HashMap允許null值(key和value都可以)。
3.HashTable有一個contains(Object value)功能和containsValue(Object value)功能一樣。
4.HashTable使用Enumeration進行遍歷，HashMap使用Iterator進行遍歷。

5.HashTable中hash數組默認大小是11，增加的方式是 old*2+1。HashMap中hash數組的默認大小是16，而且一定是2的指數。

7. 其他Map實現

7.1 TreeMap

TreeMap是有序的Map結構。應用在需要根據key排序的場景下。TreeMap內部是通過紅黑樹實現有序的。這邊就不進行深入研究了。感興趣的大家可以自己研究下程式碼。

下面提供下TreeMap的使用示例：

//根據key的默認排序順序排序  TreeMap<String, String> treeMap = new TreeMap<>();  treeMap.put("Java","obj");  treeMap.put("Python","obk");  treeMap.put("C##","oxx");  treeMap.forEach((key,value) ->{      System.out.println("["+key+"]"+":"+"["+value+"]");  });    //自定義key的排序順序  //如果自定義了比較器，那麼TreeMap比較兩個key是否相等的規則就變成  //首先根據hashcode判斷，然後通過key的compare方法判斷，而不是通過equals方法判斷了  TreeMap<String, Object> treeMap1 = new TreeMap<>(new Comparator<String>() {      @Override      public int compare(String o1, String o2) {          return o1.compareToIgnoreCase(o2);      }  });  treeMap1.put("Java","obj");  treeMap1.put("Python","obk");  treeMap1.put("java","oxx");  treeMap1.forEach((key,value) ->{      System.out.println("["+key+"]"+":"+"["+value+"]");  });

7.2 LinkedHashMap

LinkedHashMap繼承於HashMap，HashMap是無序的，當我們希望有順序地去存儲key-value時，就需要使用LinkedHashMap了。LinkedHashMap使用雙向鏈表維護順序。（Entry中維護了兩個指針，分別指向前面的節點和後面的節點）

LinkedHashMap的有序性分兩種：插入順序和訪問順序。

LinkedHashMap的構造函數的參數中有一個accessOrder的參數。這個accessOrder設置為false，表示以插入順序訪問Map中的值。這個也是默認值。

 LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);          linkedHashMap.put("name1","Java");          linkedHashMap.put("name2","Python");          linkedHashMap.put("name3","C##");            linkedHashMap.forEach((key,value) ->{              System.out.println("["+key+"]"+":"+"["+value+"]");          });

輸出

[name1]:[Java]  [name2]:[Python]  [name3]:[C##]

輸出的順序和我們put元素的順序是一致的。

還有一種模式是訪問順序模式，也就是將accessOrder設置成true。我們來看下效果。

    LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);          linkedHashMap.put("name1","Java");          linkedHashMap.put("name2","Python");          linkedHashMap.put("name3","C##");          linkedHashMap.get("name2");          linkedHashMap.get("name1");          linkedHashMap.forEach((key,value) ->{              System.out.println("["+key+"]"+":"+"["+value+"]");          });

輸出

[name3]:[C##]  [name2]:[Python]  [name1]:[Java]

可以看出，在訪問順序模式下，通過get方法和put方法訪問過的元素都會被放置到雙向鏈表的尾部。

參考

  • https://www.cnblogs.com/xawei/p/6747660.html
  • https://blog.csdn.net/zs319428/article/details/81984635
  • https://blog.csdn.net/yan_wenliang/article/details/50976113

VirMach 便宜 VPS

QNews

QNews