### HashMap簡介 從結構實現來講，HashMap是數組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）實現；本質上是基于hash表實現； > Hash表的讀寫性能在很大程度上依賴HashCode的隨機性，即HashCode越隨機散列，Hash表的沖突就越少，讀寫性能也就越高 HashMap基于哈希表的Map接口的實現。此實現提供所有可選的映射操作，并允許使用 null 值和 null 鍵。（除了不同步和允許使用 null 之外，HashMap類與Hashtable 大致相同）此類不保證映射的順序，特別是它不保證該順序恒久不變。 值得注意的是HashMap不是線程安全的，如果想要線程安全的HashMap，可以通過Collections類的靜態方法synchronizedMap獲得線程安全的HashMap。 ``` Map map = Collections.synchronizedMap(new HashMap()); ``` ### HashMap的數據結構 HashMap的底層主要是基于數組和鏈表來實現的，它之所以有相當快的查詢速度主要是因為它是通過計算散列碼來決定存儲的位置。HashMap中主要是通過key的hashCode來計算hash值的，只要hashCode相同，計算出來的hash值就一樣。如果存儲的對象對多了，就有可能不同的對象所算出來的hash值是相同的，這就出現了所謂的hash沖突。學過數據結構的同學都知道，解決hash沖突的方法有很多，HashMap底層是通過鏈表來解決hash沖突的。 下面一幅圖，形象的反映出HashMap的數據結構：數組加鏈表實現  ### HashMap屬性 ``` //樹化鏈表節點的閾值，當某個鏈表的長度大于或者等于這個長度，則擴大數組容量，或者樹化鏈表 static final int TREEIFY_THRESHOLD = 8; //初始容量，必須是2的倍數，默認是16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //最大所能容納的key-value 個數 static final int MAXIMUM_CAPACITY = 1 << 30; //默認的加載因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //存儲數據的Node數組，長度是2的冪。 transient Node<K,V>[] table; //keyset 方法要返回的結果 transient Set<Map.Entry<K,V>> entrySet; //map中保存的鍵值對的數量 transient int size; //hashmap 對象被修改的次數 transient int modCount; // 容量乘以裝載因子所得結果，如果key-value的 數量等于該值，則調用resize方法，擴大容量，同時修改threshold的值。 int threshold; //裝載因子 final float loadFactor; ``` ### 構造方法 ``` public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } ``` 注意：使用指定的初始容量和默認的加載因子初始化HashMap，這里需要注意的是，并不是你指定的初始容量是多少那么初始化之后的HashMap的容量就是多大，例如new HashMap\(20,0.8\); 那么實際的初始化容量是32，因為tableSizeFor\(\)方法會嚴格要求把初始化的容量是以2的次方數成長只能是16、32、64、128...... 在HashMap中，哈希桶數組table的長度length大小必須為2的n次方\(一定是合數\) ### 主要方法  * **put\(K key, V value\)**  執行邏輯： 1\) 根據key計算hash值，用于定位對象在HashMap數組的哪個節點。 2）判斷table有沒有初始化，如果沒有初始化，則調用resize\(\)方法為table初始化容量，以及threshold的值。 3）根據hash值定位該key對應的數組索引，如果對應的數組索引位置無值，則調用newNode\(\)方法，為該索引創建Node節點 4）如果根據hash值定位的數組索引有Node，并且Node中的key和需要新增的key相等，則將對應的value值更新。 5）如果在已有的table中根據hash找到Node，其中Node中的hash值和新增的hash相等，但是key值不相等的，那么創建新的Node，放到當前已存在的Node的鏈表尾部。如果當前Node的長度大于8,則調用treeifyBin\(\)方法擴大table數組的容量，或者將當前索引的所有Node節點變成TreeNode節點，變成TreeNode節點的原因是由于TreeNode節點組成的鏈表索引元素會快很多。 6）將當前的key-value 數量標識size自增，然后和threshold對比，如果大于threshold的值，則調用resize\(\)方法，擴大當前HashMap對象的存儲容量。 7）返回oldValue或者null； ``` /** * Implements Map.put and related methods * * @param key的hash值 * @param key值 * @param value值 * @param onlyIfAbsent如果是true，則不修改已存在的value值 * @param evict if false, the table is in creation mode. * @return 返回被修改的value，或者返回null。 */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) //如果是第一次調用，則會調用resize 初始化table 以及threshold n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) //如果對應的索引沒有Node，則新建Node放到table里面。 tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //如果hash值與已存在的hash相等，并且key相等，則準備更新對應Node的value e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //如果hash值一致，但是key不一致，那么將新的key-value添加到已有的Node的最后面 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // 當某個節點的鏈表長度大于8，則擴大table 數組的長度或者將當前節點鏈表變成樹節點鏈表 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) //hash值和key值相等的情況下，更新value值 e.value = value; //留給LinkedHashMap實現 afterNodeAccess(e); //返回舊的value return oldValue; } } //修改次數加1 ++modCount; //判斷table的容量是否需要擴展 if (++size > threshold) resize(); //留給LinkedHashMap擴展 afterNodeInsertion(evict); return null; } ``` * **resize\(\)** 上面調用到了一個resize方法， 我們來看看這個方法里面做了什么，實現邏輯如下： 1）如果當前數組為空，則初始化當前數組 2）如果當前table數組不為空，則將當前的table數組擴大兩倍，同時將閾值（threshold）擴大兩倍 ``` /** * 初始化，或者是擴展table 的容量。 * table的容量是按照2的指數增長的。 * 當擴大table 的容量的時候，元素的hash值以及位置可能發生變化。 */ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; //當前table 數組的長度 int oldCap = (oldTab == null) ? 0 : oldTab.length; //當前的閾值 int oldThr = threshold; int newCap, newThr = 0; //如果table數組已有值，則將其容量（size）和閾值（threshold）擴大兩倍 if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // 當第一次調用resize的時候會執行這個代碼，初始化table容量以及閾值 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //將新的閾值存儲起來 threshold = newThr; //重新分配table 的容量 @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //將以前table中的值copy到新的table中去 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order 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; } ``` * **get\(Object key\)** 根據key的hash值和key，可以唯一確定一個value，下面我們來看看get方法執行的邏輯 1）根據key計算hash值 2）根據hash值和key確定所需要返回的結果，如果不存在，則返回空 ``` /** * Implements Map.get and related methods * * @param key 的hash值 * @param key的值 * @return 返回由key和hash定位的Node，或者null */ 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 && // 如果索引到的第一個Node，key 和 hash值都和傳遞進來的參數相等，則返回該Node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { //如果索引到的第一個Node 不符合要求，循環變量它的下一個節點。 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; } ``` * **remove\(Object key\)** 執行邏輯： 1）根據key得到key的hash值 2）根據key 和hash值定位需要remove的Node 3\) 將Node從對應的鏈表移除，然后再將Node 前后的節點對接起來 4）返回被移除 的Node 5）key-value的數量減一，修改次數加一 ``` /** * Implements Map.remove and related methods * * @param key的hash值 * @param key值 * @param 需要remove 的value， * @param 為true時候，當value相等的時候才remove * @param 如果為false 的時候，不會移動其他節點。 * @return 返回被移除的Node，或者返回null */ final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null, e; K k; V v; if (p.hash == hash && //如果定位到的第一個元素符合條件，則跳出if else ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { do {//定位到的第一個Node元素不符合條件，則遍歷其鏈表 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } //移除符合要求的節點，將鏈表重新連接起來 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) tab[index] = node.next; else p.next = node.next; //修改次數加1 ++modCount; //當前的key-value 對數減一 --size; afterNodeRemoval(node); return node; } } return null; ``` ### 總結 * HashMap默認初始容量是16； * HashMap默認加載因子是0.75； * HashMap非線程安全； * 如果自定義對象作為Map的鍵，那么必須重寫hashCode和equals； * HashMap允許使用null值和null鍵； * HashMap不保證映射的順序，特別是它不保證該順序恒久不變； * HashMap的底層主要是基于數組和鏈表來實現； * HashMap其實就是一個Entry數組，Entry對象中包含了鍵和值，其中next也是一個Entry對象，它就是用來處理hash沖突的，形成一個鏈表； * 容量取2的整數次冪，是為了使不同hash值發生碰撞的概率較小，這樣就能使元素在哈希表中均勻地散列； * 如果key為null的話，hash值為0，對象存儲在數組中索引為0的位置。即table\[0\]； #### loadFactor加載因子取值影響 * 如果加載因子越大,填滿的元素越多,好處是空間利用率高了,但沖突的機會加大了.鏈表長度會越來越長,查找效率降低。 * 如果加載因子越小,填滿的元素越少,好處是沖突的機會減小了,但空間浪費多了.表中的數據將過于稀疏（很多空間還沒用，就開始擴容了） * 沖突的機會越大,則查找的成本越高 #### HashMap$Node 定義： ``` static class Node<K,V> implements Map.Entry<K,V> { final int hash; // hash值 final K key; V value; Node<K,V> next; //當hash值相同時，next存儲鏈表的下一個節點的引用 ...... } ``` #### HashMap擴容 當HashMap中的元素個數超過數組大小\*loadFactor時，就會進行數組擴容，loadFactor的默認值為0.75，這是一個折中的取值。也就是說，默認情況下，數組大小為16，那么當HashMap中元素個數超過16\*0.75=12的時候，就把數組的大小擴展為 2\*16=32，即擴大一倍，然后重新計算每個元素在數組中的位置，擴容是需要進行數組復制的，復制數組是非常消耗性能的操作，所以如果我們已經預知HashMap中元素的個數，那么預設元素的個數能夠有效的提高HashMap的性能 #### 源碼分析 ``` transient Node<K,V>[] table; //存儲元素的實體數組 final float loadFactor; //加載因子 ``` #### 通過反射獲取HashMap的table ``` public class Appliction { public static void main(String[] args) throws Exception { HashMap<Integer, String> m = new HashMap(); Random random = new Random(); for (int i = 0; i < 10000; i++) { int nextInt = random.nextInt(); m.put(nextInt, nextInt + ""); } Class cls = HashMap.class; // System.err.println("HashMap class ===>" + cls); Field table = cls.getDeclaredField("table"); table.setAccessible(true); Class cs = Class.forName("java.util.HashMap$Node"); // System.err.println("HashMap$Node class ===>" + cs); Object[] object = (Object[]) table.get(m); System.err.println(object.length); for (Object obj : object) { if (Objects.nonNull(obj)) { // System.err.println(obj); Field hash = cs.getDeclaredField("hash"); hash.setAccessible(true); // System.err.println("hash==>" + hash.get(obj)); Field next = cs.getDeclaredField("next"); next.setAccessible(true); Object nextValue = next.get(obj); if (Objects.nonNull(nextValue)) { System.err.println("next===>" + nextValue); } } } } } ``` ### 為什么HashMap線程不安全 上面說到，HashMap會進行resize操作，在resize操作的時候會造成線程不安全。下面將舉兩個可能出現線程不安全的地方。 1、put的時候導致的多線程數據不一致。 這個問題比較好想象，比如有兩個線程A和B，首先A希望插入一個key-value對到HashMap中，首先計算記錄所要落到的桶的索引坐標，然后獲取到該桶里面的鏈表頭結點，此時線程A的時間片用完了，而此時線程B被調度得以執行，和線程A一樣執行，只不過線程B成功將記錄插到了桶里面，假設線程A插入的記錄計算出來的桶索引和線程B要插入的記錄計算出來的桶索引是一樣的，那么當線程B成功插入之后，線程A再次被調度運行時，它依然持有過期的鏈表頭但是它對此一無所知，以至于它認為它應該這樣做，如此一來就覆蓋了線程B插入的記錄，這樣線程B插入的記錄就憑空消失了，造成了數據不一致的行為。 2、另外一個比較明顯的線程不安全的問題是HashMap的get操作可能因為resize而引起死循環（cpu100%），具體分析如下： > 注意： > 在jdk1.8之前新加入的沖突元素將會插到原有鏈表的頭部，當時設計HashMap的大叔采用頭插法而沒有采用尾插法有一點考慮是性能優化，認為最近put進去的元素，被get的概率相對較其他元素大，采用頭插法能夠更快得獲取到最近插入的元素；但頭插法的設計有一個特點，就是擴容之后，鏈表上的元素順序會反過來，這也是死循環的一個重要原因； > 在jdk1.8及之后時，使用的是數組+鏈表+紅黑樹的數據結構（當鏈表的深度達到8的時候，也就是默認閾值，就會自動擴容把鏈表轉成紅黑樹的數據結構來把時間復雜度從O（n）變成O（logN）提高了效率），會先進行插入再進行擴容，執行的是尾插法，直接插到鏈表尾部/紅黑數樹，不會出現逆序和環形鏈表死循環問題 下面的代碼是resize的核心內容： ``` void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } } ``` 這個方法的功能是將原來的記錄重新計算在新桶的位置，然后遷移過去  我們假設有兩個線程同時需要執行resize操作，我們原來的桶數量為2，記錄數為3，需要resize桶到4，原來的記錄分別為：\[3,A\],\[7,B\],\[5,C\]，在原來的map里面，我們發現這三個entry都落到了第二個桶里面。 假設線程thread1執行到了transfer方法的Entry next = e.next這一句，然后時間片用完了，此時的e = \[3,A\], next = \[7,B\]。線程thread2被調度執行并且順利完成了resize操作，需要注意的是，此時的\[7,B\]的next為\[3,A\]。此時線程thread1重新被調度運行，此時的thread1持有的引用是已經被thread2 resize之后的結果。線程thread1首先將\[3,A\]遷移到新的數組上，然后再處理\[7,B\]，而\[7,B\]被鏈接到了\[3,A\]的后面，處理完\[7,B\]之后，就需要處理\[7,B\]的next了啊，而通過thread2的resize之后，\[7,B\]的next變為了\[3,A\]，此時，\[3,A\]和\[7,B\]形成了環形鏈表，在get的時候，如果get的key的桶索引和\[3,A\]和\[7,B\]一樣，那么就會陷入死循環。 _**參考資料**_ [https://www.jianshu.com/p/e2f75c8cce01](https://www.jianshu.com/p/e2f75c8cce01)