文檔處理控制欄： * [x] 選題收集：2017/12/28 * [ ] 初稿整理： * [ ] 補充校對： * [ ] 入庫存檔： --- # 圖解HashMap(一) ### 概述 HashMap是日常開發中經常會用到的一種數據結構，在介紹HashMap的時候會涉及到很多術語，比如時間復雜度O、散列(也叫哈希)、散列算法等，這些在大學課程里都有教過，但是由于某種不可抗力又還給老師了，在深入學習HashMap之前先了解HashMap設計的思路以及以及一些重要概念，在后續分析源碼的時候就能夠有比較清晰的認識。 ### HashMap是什么 在回答這個問題之前先看個例子：小明打算從A市搬家到B市，拿了兩個箱子把自己的物品打包就出發了。 到了B市之后，他想拿手機給家里報個平安，這時候問題來了，東西多了他忘記手機放在哪個箱子了？小明開始打開1號箱子找手機，沒找到；再打開2號箱子找，找到手機。當只有2個箱子的時候，東西又不多的情況下，他可能花個2分鐘就找到手機了，假如有20個箱子，每個箱子的東西又多又雜，那么花的時間就多了。小明總結了下查找耗時的原因，發現是因為這些東西放的沒有規律，如果他把每個箱子分個類別，比如定一個箱子專門放手機、電腦等電子設備，有專門放衣服的箱子等等，那么他找東西花的時間就可以大大縮短了。 其實HashMap也是用到這種思路，HashMap作為一種數據結構，像數組和鏈表一樣用于常規的增刪改查，在存數據的時候(put)并不是隨便亂放，而是會先做一次類似“分類”的操作再存儲，一旦“分類”存儲之后，下次取(get)的時候就可以大大縮短查找的時間。我們知道數組在執行查、改的效率很高，而增、刪(不是尾部)的效率低，鏈表相反，HashMap則是把這兩者結合起來，看下HashMap的數據結構 從上面的結構可以看出，通常情況下HashMap是以數組和鏈表的組合構成(Java8中將鏈表長度超過8的鏈表轉化成紅黑樹)。結合上面找手機的例子，我們簡單分析下HashMap存取操作的心路歷程。put存一個鍵值對的時候(比如存上圖蓋倫)，先根據鍵值"分類"，"分類"一頓操作后告訴我們，蓋倫應該屬于14號坑，直接定位到14號坑。接下來有幾種情況： * 14號坑沒人，nice，直接存值； * 14號有人，也叫蓋倫，替換原來的攻擊值； * 14號有人，叫老王！插隊到老王前面去(單鏈表的頭插入方式，同一位置上新元素總會被放在鏈表的頭部位置) get取的時候也需要傳鍵值，根據傳的鍵值來確定要找的是哪個"類別"，比如找火男，"分類"一頓操作夠告訴我們火男屬于2號坑，于是我們直接定位到2號坑開始找，亞索不是…找到火男。 #### 小結 HashMap是由數組和鏈表組合構成的數據結構，Java8中鏈表長度超過8時會把長度超過8的鏈表轉化成紅黑樹；存取時都會根據鍵值計算出"類別"(hashCode)，再根據"類別"定位到數組中的位置并執行操作。 ### HashCode是什么 還是舉個栗子：一個工廠有500號人，下圖用兩種方案來存儲廠里員工的信件。 左右各有27個信箱，左邊保安大哥存信的時候不做處理，想放哪個信箱就放哪個信箱，當員工去找信的時候，只好挨個信箱找，再挨個比對信箱里信封的名字，萬一哥們臉黑，要找的放在最后一個信箱的最底下，悲劇…所以這種情況的時間復雜度為O(N)；右邊采用HashCode的方式將27個信箱分類，分類的規則是名字首字母(第一個箱子放不寫名字的哥們)，保安大哥將符合對應姓名的信件放在對應的信箱里，這樣員工就不用挨個找了，只需要比對一個信箱里的信件即可，大大提高了效率，這種情況的時間復雜度趨于一個常數O(1)。 例子中右圖其實就是hashCode的一個實現，每個員工都有自己的hashCode，比如李四的hashCode是L，王五的hashCode是W(這取決于你的hash算法怎么寫)，然后我們根據確定的hashCode值把信箱分類，hashCode匹配則存在對應信箱。在Java的Object中可以調用hashCode()方法獲取對象hashCode，返回一個int值。那么會出現兩個對象的hashCode一樣嗎?答案是會的，就像上上個例子中蓋倫和老王的hashCode就一樣，這種情況網上有人稱之為"hash碰撞"，出現這種所謂"碰撞"的處理上面已經介紹了解決思路，具體源碼后續介紹。 #### 小結 hashCode是一個對象的標識，Java中對象的hashCode是一個int類型值。通過hashCode來指定數組的索引可以快速定位到要找的對象在數組中的位置，之后再遍歷鏈表找到對應值，理想情況下時間復雜度為O(1)，并且不同對象可以擁有相同的hashCode。 ### HashMap的時間復雜度 通過上面信箱找信的例子來討論下HashMap的時間復雜度，在使用hashCode之后可以直接定位到一個箱子，時間的耗費主要是在遍歷鏈表上，理想的情況下(hash算法寫得很完美)，鏈表只有一個節點，就是我們要的 那么此時的時間復雜度為O(1)，那不理想的情況下(hash算法寫得很糟糕)，比如上面信箱的例子，假設hash算法計算每個員工都返回同樣的hashCode  所有的信都放在一個箱子里，此時要找信就要依次遍歷C信箱里的信，時間復雜度不再是O(1)，而是O(N)，因此HashMap的時間復雜度取決于算法的實現上，當然HashMap內部的機制并不像信箱這么簡單，在HashMap內部會涉及到擴容、Java8中會將長度超過8的鏈表轉化成紅黑樹，這些都在后續介紹。 #### 小結 HashMap的時間復雜度取決于hash算法，優秀的hash算法可以讓時間復雜度趨于常數O(1)，糟糕的hash算法可以讓時間復雜度趨于O(N)。 ### 負載因子是什么 我們知道HashMap中數組長度是16(什么？你說不知道，看下源碼你就知道)，假設我們用的是最優秀的hash算法，即保證我每次往HashMap里存鍵值對的時候，都不會重復，當hashmap里有16個鍵值對的時候，要找到指定的某一個，只需要1次；  之后繼續往里面存值，必然會發生所謂的"hash碰撞"形成鏈表，當hashmap里有32個鍵值對時，找到指定的某一個最壞情況要2次；當hashmap里有128個鍵值對時，找到指定的某一個最壞情況要8次  隨著hashmap里的鍵值對越來越多，在數組數量不變的情況下，查找的效率會越來越低。那怎么解決這個問題呢？只要增加數組的數量就行了，鍵值對超過16，相應的就要把數組的數量增加(HashMap內部是原來的數組長度乘以2)，這就是網上所謂的**擴容**，就算你有128個鍵值對，我們準備了128個坑，還是能保證"一個蘿卜一個坑"。  > 其實擴容并沒有那么風光，就像ArrayList一樣，擴容是件很麻煩的事情，要創建一個新的數組，然后把原來數組里的鍵值對"放"到新的數組里，這里的"放"不像ArrayList那樣用原來的index，而是根據新表的長度重新計算hashCode，來保證在新表的位置，老麻煩了，所以同一個鍵值對在舊數組里的索引和新數組中的索引通常是不一致的(火男："我以前是3號，怎么現在成了127號，給我個完美的解釋！"新表："大清亡了，現在你得聽我的")。另外，我們也可以看出這是典型的以空間換時間的操作。 說了這么多，那負載因子是個什么東西？負載因子其實就是規定什么時候擴容。上面我們說默認hashmap數組大小為16，存的鍵值對數量超過16則進行擴容，好像沒什么毛病。然而HashMap中并不是等數組滿了(達到16)才擴容，它會存在一個閥值(threshold)，只要hashmap里的鍵值對大于等于這個閥值，那么就要進行擴容。閥值的計算公式： > 閥值 = 當前數組長度?負載因子 hashmap中默認負載因子為**0.75**，默認情況下第一次擴容判斷閥值是16 ? 0.75 = 12；所以第一次存鍵值對的時候，在存到第13個鍵值對時就需要擴容了；或者另外一種理解思路：假設當前存到第12個鍵值對：12 / 16 = 0.75，13 / 16 = 0.8125(大于0.75需要擴容) 。肯定會有人有疑問，我要這鐵棒有何用？不，我要這負載因子有何用?直接規定超過數組長度再擴容不就行了，還省得每次擴容之后還要重新計算新的閥值，Google說取0.75是一個比較好的權衡，當然我們可以自己修改，HashMap初識化時可以指定數組大小和負載因子，你完全可以改成1。 ~~~ public HashMap(int initialCapacity, float loadFactor) ~~~ 我的理解是這負載因子就像人的飯量，有的人吃要7分飽，有的人要10分飽，穩妥起見默認讓我們7.5分飽。 #### 小結 在數組大小不變的情況下，存放鍵值對越多，查找的時間效率會降低，擴容可以解決該問題，而負載因子決定了什么時候擴容，負載因子是已存鍵值對的數量和總的數組長度的比值。默認情況下負載因子為0.75，我們可在初始化HashMap的時候自己修改。 ### hash與Rehash hash和rehash的概念其實上面已經分析過了，每次擴容后，轉移舊表鍵值對到新表之前都要重新rehash，計算鍵值對在新表的索引。如下圖火男這個鍵值對被存進hashmap到后面擴容，會經過hash和rehash的過程  第一次hash可以理解成'"分類"'，方便后續取、改等操作可以快速定位到具體的"坑"。那么為什么要進行rehash，按照之前元素在數組中的索引直接賦值，例如火男之前3號坑，現在跑到30號坑。  個人理解是，在未擴容前，可以看到如13號鏈的長度是3，為了保證我們每次查找的時間復雜度O趨于O(1)，理想的情況是"一個蘿卜一個坑"，那么現在"坑"多了，原來"3個蘿卜一個坑"的情況現在就能有效的避免了。 ### 源碼分析 #### Java7源碼分析 先看下Java7里的HashMap實現，有了上面的分析，現在在源碼中找具體的實現。 ~~~ //HashMap里的數組 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; //Entry對象，存key、value、hash值以及下一個節點 static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; } //默認數組大小，二進制1左移4位為16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4； //負載因子默認值 static final float DEFAULT_LOAD_FACTOR = 0.75f; //當前存的鍵值對數量 transient int size; //閥值 = 數組大小 * 負載因子 int threshold; //負載因子變量 final float loadFactor; //默認new HashMap數組大小16，負載因子0.75 public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //可以指定數組大小和負載因子 public HashMap(int initialCapacity, float loadFactor) { //省略一些邏輯判斷 this.loadFactor = loadFactor; threshold = initialCapacity; //空方法 init(); } ~~~ 以上就是HashMap的一些先決條件，接著看平時put操作的代碼實現，put的時候會遇到3種情況上面已分析過，看下Java7代碼： ~~~ public V put(K key, V value) { //數組為空時創建數組 if (table == EMPTY_TABLE) { inflateTable(threshold); } //key為空單獨對待 if (key == null) return putForNullKey(value); //①根據key計算hash值 int hash = hash(key); //②根據hash值和當前數組的長度計算在數組中的索引 int i = indexFor(hash, table.length); //遍歷整條鏈表 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //③情況1.hash值和key值都相同的情況，替換之前的值 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); //返回被替換的值 return oldValue; } } modCount++; //③情況2.坑位沒人,直接存值或發生hash碰撞都走這 addEntry(hash, key, value, i); return null; } ~~~ 先看上面key為空的情況(上面畫圖的時候總要在第一格留個空key的鍵值對)，執行 putForNullKey() 方法單獨處理，會把該鍵值對放在index0，所以HashMap中是允許key為空的情況。再看下主流程： 步驟①.根據鍵值算出hash值 — > hash(key) 步驟②.根據hash值和當前數組的長度計算在數組中的索引 — > indexFor(hash, table.length) ~~~ static int indexFor(int h, int length) { //hash值和數組長度-1按位與操作，聽著費勁？其實相當于h%length;取余數(取模運算) //如：h = 17，length = 16;那么算出就是1 //&運算的效率比%要高 return h & (length-1); } ~~~ 步驟③情況1.hash值和key值都相同，替換原來的值，并將被替換的值返回。 步驟③情況2.坑位沒人或發生hash碰撞 — > addEntry(hash, key, value, i) ~~~ void addEntry(int hash, K key, V value, int bucketIndex) { //當前hashmap中的鍵值對數量超過閥值 if ((size >= threshold) && (null != table[bucketIndex])) { //擴容為原來的2倍 resize(2 * table.length); hash = (null != key) ? hash(key) : 0; //計算在新表中的索引 bucketIndex = indexFor(hash, table.length); } //創建節點 createEntry(hash, key, value, bucketIndex); } ~~~ 如果put的時候超過閥值，會調用 resize() 方法將數組大小擴大為原來的2倍，并且根據新表的長度計算在新表中的索引(如之前17%16 =1，現在17%32=17)，看下resize方法 ~~~ void resize(int newCapacity) { //傳入新的容量 //獲取舊數組的引用 Entry[] oldTable = table; int oldCapacity = oldTable.length; //極端情況，當前鍵值對數量已經達到最大 if (oldCapacity == MAXIMUM_CAPACITY) { //修改閥值為最大直接返回 threshold = Integer.MAX_VALUE; return; } //步驟①根據容量創建新的數組 Entry[] newTable = new Entry[newCapacity]; //步驟②將鍵值對轉移到新的數組中 transfer(newTable, initHashSeedAsNeeded(newCapacity)); //步驟③將新數組的引用賦給table table = newTable; //步驟④修改閥值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } ~~~ 上面的重點是步驟②，看下它具體的轉移操作 ~~~ 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; } } } ~~~ 這段for循環的遍歷會使得轉移前后鍵值對的順序顛倒(Java7和Java8的區別)，畫個圖就清楚了，假設石頭的key值為5，蓋倫的key值為37,這樣擴容前后兩者還是在5號坑。第一次：  第二次  最后再看下創建節點的方法 ~~~ void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; } ~~~ 創建節點時，如果找到的這個坑里面沒有存值，那么直接把值存進去就行了，然后size++；如果是碰撞的情況，  前面說的以單鏈表頭插入的方式就是這樣(蓋倫：”老王已被我一腳踢開！“)，總結一下Java7 put流程圖  相比put，get操作就沒這么多套路，只需要根據key值計算hash值，和數組長度取模，然后就可以找到在數組中的位置(key為空同樣單獨操作)，接著就是遍歷鏈表，源碼很少就不分析了。 #### Java8源碼分析 基本思路是一樣的 ~~~ //定義長度超過8的鏈表轉化成紅黑樹 static final int TREEIFY_THRESHOLD = 8; //換了個馬甲還是認識你！！！ static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; } ~~~ 看下Java8 put的源碼 ~~~ public V put(K key, V value) { //根據key計算hash值 return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //步驟1.數組為空或數組長度為0，則擴容(咦，看到不一樣咯) if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //步驟2.根據hash值和數組長度計算在數組中的位置 //如果"坑"里沒人，直接創建Node并存值 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; //步驟3."坑"里有人，且hash值和key值都相等，先獲取引用，后面會用來替換值 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //步驟4.該鏈是紅黑樹 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //步驟5.該鏈是鏈表 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { //步驟5.1注意這個地方跟Java7不一樣，是插在鏈表尾部！！！ p.next = newNode(hash, key, value, null); //鏈表長度超過8，轉化成紅黑樹 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //步驟5.2鏈表中已存在且hash值和key值都相等，先獲取引用，后面用來替換值 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) //統一替換原來的值 e.value = value; afterNodeAccess(e); //返回原來的值 return oldValue; } } ++modCount; //步驟6.鍵值對數量超過閥值，擴容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } ~~~ 通過上面注釋分析，對比和Java7的區別，Java8一視同仁，管你key為不為空的統一處理，多了一步鏈表長度的判斷以及轉紅黑樹的操作，并且比較重要的一點，新增Node是插在尾部而不是頭部！！！。當然上面的主角還是擴容resize操作 ~~~ final Node<K,V>[] resize() { //舊數組的引用 Node<K,V>[] oldTab = table; //舊數組長度 int oldCap = (oldTab == null) ? 0 : oldTab.length; //舊數組閥值 int oldThr = threshold; //新數組長度、新閥值 int newCap, newThr = 0; if (oldCap > 0) { //極端情況，舊數組爆滿了 if (oldCap >= MAXIMUM_CAPACITY) { //閥值改成最大，放棄治療直接返回舊數組 threshold = Integer.MAX_VALUE; return oldTab; } //擴容咯，這里采用左移運算左移1位，也就是舊數組*2 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //同樣新閥值也是舊閥值*2 newThr = oldThr << 1; // double threshold } 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); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //更新閥值 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) //創建新數組 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; 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); //鏈表長度大于1，小于8的情況，下面高能，單獨拿出來分析 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; } ~~~ 可以看到，Java8把初始化數組和擴容全寫在resize方法里了，但是思路還是一樣的，擴容后要轉移，轉移要重新計算在新表中的位置，上面代碼最后一塊高能可能不太好理解，剛開始看的我一臉懵逼，看了一張[美團博客](https://link.juejin.im/?target=https%3A%2F%2Ftech.meituan.com%2Fjava-hashmap.html)的分析圖才豁然開朗，在分析前先捋清楚思路 > 下面我們講解下JDK1.8做了哪些優化。經過觀測可以發現，我們使用的是2次冪的擴展(指長度擴為原來2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置。看下圖可以明白這句話的意思，n為table的長度，圖（a）表示擴容前的key1(5)和key2(21)兩種key確定索引位置的示例，圖（b）表示擴容后key1和key2兩種key確定索引位置的示例，其中hash1是key1對應的哈希與高位運算結果。  > 圖a中key1(5)和key(21)計算出來的都是5，元素在重新計算hash之后，因為n變為2倍，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會發生這樣的變化：  > 圖b中計算后key1(5)的位置還是5，而key2(21)已經變成了21，因此，我們在擴充HashMap的時候，不需要像JDK1.7的實現那樣重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”。 有了上面的分析再回來看下源碼 ~~~ else { // preserve order //定義兩條鏈 //原來的hash值新增的bit為0的鏈，頭部和尾部 Node<K,V> loHead = null, loTail = null; //原來的hash值新增的bit為1的鏈，頭部和尾部 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; } } ~~~ 為了更清晰明了，還是舉個栗子，下面的表定義了鍵和它們的hash值(數組長度為16時，它們都在5號坑) | Key | Hash | | --- | --- | | 石頭 | 5 | | 蓋倫 | 5 | | 蒙多 | 5 | | 妖姬 | 21 | | 狐貍 | 21 | | 日女 | 21 | 假設一個hash算法剛好算出來的的存儲是這樣的，在存第13個元素時要擴容  那么流程應該是這樣的(只關注5號坑鍵值對的情況)，第一次：  第二次：  省略中間幾次，第六次  兩條鏈找出來后，最后轉移一波，大功告成。 ~~~ //擴容前后位置不變的鏈 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //擴容后位置加上原數組長度的鏈 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } ~~~  總結下Java8 put流程圖  #### 對比 1.發生hash沖突時，Java7會在鏈表頭部插入，Java8會在鏈表尾部插入 2.擴容后轉移數據，Java7轉移前后鏈表順序會倒置，Java8還是保持原來的順序 3.關于性能對比可以參考[美團技術博客](https://link.juejin.im/?target=https%3A%2F%2Ftech.meituan.com%2Fjava-hashmap.html)，引入紅黑樹的Java8大程度得優化了HashMap的性能 ### 感謝 [講的很詳細的外國小哥](https://link.juejin.im/?target=http%3A%2F%2Fjavabypatel.blogspot.ca%2F) [美團技術博客](https://link.juejin.im/?target=https%3A%2F%2Ftech.meituan.com%2Fjava-hashmap.html)