徹底理解HashMap及LinkedHashMap

下面基于JDK 1.8的源碼來學習HashMap及LinkedHashMap的數(shù)據(jù)結構、原理。不同JDK版本之間也許會有些許差異，但不影響原理學習，JDK8相比以前對HashMap的修改比較大。

1、HashMap概述

Map是 Key-Value鍵值對映射的抽象接口，該映射不包括重復的鍵，即一個鍵對應一個值。HashMap是Java Collection Framework的重要成員，也是Map族(如下圖所示)中我們最為常用的一種。簡單地說，HashMap是基于哈希表的Map接口的實現(xiàn)，以Key-Value的形式存在，即存儲的對象是 Node (同時包含了Key和Value) 。在HashMap中，其會根據(jù)hash算法來計算key-value的存儲位置并進行快速存取。特別地，HashMap最多只允許一條Node的key為Null，但允許多條Node的value為Null。此外，HashMap是Map 的一個非同步的實現(xiàn)。

以下是HashMap的類繼承圖

必須指出的是，雖然容器號稱存儲的是 Java 對象，但實際上并不會真正將 Java 對象放入容器中，只是在容器中保留這些對象的引用。也就是說，Java 容器實際上包含的是引用變量，而這些引用變量指向了我們要實際保存的 Java 對象。

1.1、HashMap定義及構造函數(shù)

JDK中的定義為

public?class?HashMap<K,V>?extends?AbstractMap<K,V>?implements?Map<K,V>,?Cloneable,?Serializable?{
????//...
}

HashMap 一共提供了四個構造函數(shù)，其中 默認無參的構造函數(shù) 和 參數(shù)為Map的構造函數(shù) 為 Java Collection Framework 規(guī)范的推薦實現(xiàn)，其余兩個構造函數(shù)則是 HashMap 專門提供的。

public?HashMap(int?initialCapacity)?{
????this(initialCapacity,?DEFAULT_LOAD_FACTOR);
}
//僅僅將負載因子初始化為默認值
public?HashMap()?{
????this.loadFactor?=?DEFAULT_LOAD_FACTOR;?
????//?all?other?fields?defaulted
}

HashMap(int initialCapacity, float loadFactor)構造函數(shù)意在構造一個指定初始容量和指定負載因子的空HashMap，其源碼如下：

public?HashMap(int?initialCapacity,?float?loadFactor)?{
????if?(initialCapacity?0)
????????throw?new?IllegalArgumentException("Illegal?initial?capacity:?"?+
???????????????????????????????????????????initialCapacity);
????//容量最大為2的30次方
????if?(initialCapacity?>?MAXIMUM_CAPACITY)
????????initialCapacity?=?MAXIMUM_CAPACITY;
????if?(loadFactor?<=?0?||?Float.isNaN(loadFactor))
????????throw?new?IllegalArgumentException("Illegal?load?factor:?"?+
???????????????????????????????????????????loadFactor);
????this.loadFactor?=?loadFactor;
????//這里調用函數(shù)計算觸發(fā)擴容的閾值，threshold/loadFactor就是容量
????this.threshold?=?tableSizeFor(initialCapacity);
}

以上構造函數(shù)的最后一行就是jdk8的修改，實際上在jdk7之前的版本，這個構造方法最后一行就是：

table?=?new?Entry[capacity];

但是jdk8的最后一行并沒有立刻new出一個數(shù)組，而是調用了tableSizeFor方法，將結果賦值給了threshold變量。tableSizeFor方法源碼如下，從注釋就可以看出來，其目的是要獲得大于cap的最小的2的冪。比如cap=10，則返回16。

/**
?*?Returns?a?power?of?two?size?for?the?given?target?capacity.
?*/
?static?final?int?tableSizeFor(int?cap)?{
????int?n?=?cap?-?1;
????n?|=?n?>>>?1;
????n?|=?n?>>>?2;
????n?|=?n?>>>?4;
????n?|=?n?>>>?8;
????n?|=?n?>>>?16;
????return?(n?0)???1?:?(n?>=?MAXIMUM_CAPACITY)???MAXIMUM_CAPACITY?:?n?+?1;
?}

1.2、HashMap的數(shù)據(jù)結構

我們知道，在Java中最常用的兩種結構是數(shù)組和鏈表，幾乎所有的數(shù)據(jù)結構都可以利用這兩種來組合實現(xiàn)，HashMap就是這種應用的一個典型。實際上，經典的HashMap就是一個鏈表數(shù)組，只是jdk1.8再次對經典hashMap的數(shù)據(jù)結構作了小幅調整，如下是當前HaspMap的數(shù)據(jù)結構：

在JDK1.6和JDK1.7中，HashMap采用數(shù)組+鏈表實現(xiàn)，即使用鏈表處理沖突，同一hash值的key-value鍵值對都存儲在一個鏈表里。但是當數(shù)組中一個位置上的元素較多，即hash值相等的元素較多時，通過key值依次查找的效率較低。而在JDK1.8中，HashMap采用數(shù)組+鏈表+紅黑樹實現(xiàn)，當鏈表長度超過閾值8時，并且數(shù)組總容量超過64時，將鏈表轉換為紅黑樹，這樣大大減少了查找時間。從鏈表轉換為紅黑樹后新加入鍵值對的效率降低，但查詢、刪除的效率都變高了。而當發(fā)生擴容或remove鍵值對導致原有的紅黑樹內節(jié)點數(shù)量小于6時，則又將紅黑樹轉換成鏈表。

每一個HashMap都有一個Node類型的table數(shù)組，其中Node類型的定義如下：

static?class?Node<K,V>?implements?Map.Entry<K,V>?{
????final?int?hash;?????????//?聲明?hash?值為?final?的
????final?K?key;????????????//?聲明?key?為?final?的
????V?value;????????????????//?鍵值對的值
????Node?next;?????????//?指向下一個節(jié)點的引用

????Node(int?hash,?K?key,?V?value,?Node?next)?{
????????this.hash?=?hash;
????????this.key?=?key;
????????this.value?=?value;
????????this.next?=?next;
????}
}

Node為HashMap的內部類，實現(xiàn)了Map.Entry接口，其包含了鍵key、值value、下一個節(jié)點next，以及hash值四個屬性。事實上，Node是構成哈希表的基石，是哈希表所存儲的元素的具體形式。值得注意的是，int類型的hash值及引用變量key都被聲明成final，即不可變。

1.3、HashMap的快速存取

在HashMap中，我們最常用的兩個操作就是：put(Key,Value)和get(Key)。我們都知道，HashMap中的Key是唯一的，那它是如何保證唯一性的呢？我們首先想到的是用equals比較，沒錯，這樣是可以實現(xiàn)的，但隨著元素的增多，put和get的效率將越來越低，這里的時間復雜度是O(n)。也就是說，假如HashMap有1000個元素，那么put時就需要比較1000次，這是相當耗時的，遠達不到HashMap快速存取的目的。

實際上，HashMap很少會用到equals方法，因為其內通過一個哈希表管理所有元素，利用哈希算法可以快速的存取元素。當我們調用put方法存值時，HashMap首先會調用Key的hashCode方法，然后基于此值獲取Key的哈希碼，通過哈希碼快速找到某個位置，這個位置可以被稱之為bucketIndex。根據(jù)equals方法與hashCode的協(xié)定可以知道，如果兩個對象的hashCode不同，那么equals一定為 false；如果其hashCode相同，equals也不一定為true。所以，理論上，hashCode 可能存在碰撞的情況，當碰撞發(fā)生時，這時會取出bucketIndex桶內已存儲的元素（如果該桶next引用不空，即有了鏈表也要遍歷鏈表），并通過hashCode()和equals()來逐個比較以判斷Key是否已存在。如果已存在，則使用新Value值替換舊Value值，并返回舊Value值；如果不存在，則存放新的鍵值對到鏈表中。因此，在HashMap中，equals()方法只有在哈希碼碰撞時才會被用到。

結合源碼來看HashMap的put操作：

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

final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,
???????????????boolean?evict)?{
????Node[]?tab;?Node?p;?int?n,?i;
????//第一次put元素時，table數(shù)組為空，先調用resize生成一個指定容量的數(shù)組
????if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)
????????n?=?(tab?=?resize()).length;
????//hash值和n-1的與運算結果為桶的位置，如果該位置空就直接放置一個Node
????if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)
????????tab[i]?=?newNode(hash,?key,?value,?null);
????//如果計算出的bucket不空，即發(fā)生哈希沖突，就要進一步判斷
????else?{
????????Node?e;?K?k;
????????//判斷當前Node的key與要put的key是否相等
????????if?(p.hash?==?hash?&&
????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????e?=?p;
????????//判斷當前Node是否是紅黑樹的節(jié)點
????????else?if?(p?instanceof?TreeNode)
????????????e?=?((TreeNode)p).putTreeVal(this,?tab,?hash,?key,?value);
????????//以上都不是，說明要new一個Node，加入到鏈表中
????????else?{
????????????for?(int?binCount?=?0;?;?++binCount)?{
?????????????//在鏈表尾部插入新節(jié)點，注意jdk1.8是在鏈表尾部插入新節(jié)點
????????????????if?((e?=?p.next)?==?null)?{
????????????????????p.next?=?newNode(hash,?key,?value,?null);
????????????????????//?如果當前鏈表中的元素大于樹化的閾值，進行鏈表轉樹的操作
????????????????????if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1st
????????????????????????treeifyBin(tab,?hash);
????????????????????break;
????????????????}
????????????????//在鏈表中繼續(xù)判斷是否已經存在完全相同的key
????????????????if?(e.hash?==?hash?&&
????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????????break;
????????????????p?=?e;
????????????}
????????}
????????//走到這里，說明本次put是更新一個已存在的鍵值對的value
????????if?(e?!=?null)?{?//?existing?mapping?for?key
????????????V?oldValue?=?e.value;
????????????if?(!onlyIfAbsent?||?oldValue?==?null)
????????????????e.value?=?value;
????????????//在hashMap中，afterNodeAccess方法體為空，交給子類去實現(xiàn)
????????????afterNodeAccess(e);
????????????return?oldValue;
????????}
????}
????++modCount;
????//如果當前size超過臨界值，就擴容。注意是先插入節(jié)點再擴容
????if?(++size?>?threshold)
????????resize();
????//在hashMap中，afterNodeInsertion方法體為空，交給子類去實現(xiàn)
????afterNodeInsertion(evict);
????return?null;
}

通過上述源碼我們可以清楚了解到HashMap保存數(shù)據(jù)的過程。先計算key的hash值，然后根據(jù)hash值搜索在table數(shù)組中的索引位置，如果table數(shù)組在該位置處有元素，則查找是否存在相同的key，若存在則覆蓋原來key的value，否則將該元素保存在鏈表尾部，注意JDK1.7中采用的是頭插法，即每次都將沖突的鍵值對放置在鏈表頭，這樣最初的那個鍵值對最終就會成為鏈尾，而JDK1.8中使用的是尾插法。此外，若table在該處沒有元素，則直接保存。

對于hash函數(shù)，具體的來看下源碼

static?final?int?hash(Object?key)?{
????int?h;
????return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);
}

以上可以看到key==null時，直接返回0，所以HashMap中鍵為NULL的鍵值對，一定在第一個桶中。

h >>> 16是用來取出h的高16位(>>>是無符號右移) 如下展示：

0000?0100?1011?0011??1101?1111?1110?0001

>>>?16?

0000?0000?0000?0000??0000?0100?1011?0011

通過之前putVal的源碼可以知道，HashMap是用(length - 1) & hash來計算數(shù)組下標的。絕大多數(shù)情況下length一般都小于2^16即小于65536。所以hash & (length-1)；結果始終是hash的低16位與（length-1）進行&運算。要是能讓hash的高16位也參與運算，會讓得到的下標更加散列。

如何讓高16也參與運算呢。方法就是讓hashCode()和自己的高16位進行^運算。由于與運單和或運單都會使得結果偏向0或者1，并不是均勻的概念，所以用異或。

結合源碼來看HashMap的get操作：

public?V?get(Object?key)?{
????Node?e;
????return?(e?=?getNode(hash(key),?key))?==?null???null?:?e.value;
}

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

在這里能夠根據(jù)key快速的取到value，除了和HashMap的數(shù)據(jù)結構密不可分外，還和Node有莫大的關系。在前面就已經提到過，HashMap在存儲過程中并沒有將key/value分開來存儲，而是當做一個整體key-value來處理的，這個整體就是Node對象。

1.4 為什么HashMap的底層數(shù)組長度總是2的n次方

當?shù)讓訑?shù)組的length為2的n次方時， hash & (length - 1)就相當于對length取模，其效率要比直接取模高得多，這是HashMap在效率上的一個優(yōu)化。

我們希望HashMap中的元素存放的越均勻越好。最理想的效果是，Node數(shù)組中每個位置都只有一個元素，這樣，查詢的時候效率最高，不需要遍歷單鏈表，也不需要通過equals去比較Key，而且空間利用率最大。

那如何計算才會分布最均勻呢？正如上一節(jié)提到的，HashMap采用了一個分兩步走的哈希策略：

使用hash()方法對Key的hashCode進行重新計算，以防止質量低下的hashCode()函數(shù)實現(xiàn)。由于HashMap的支撐數(shù)組長度總是2的倍數(shù)，通過右移可以使低位的數(shù)據(jù)盡量的不同，從而使Key的hash值的分布盡量均勻；使用hash & (length - 1)方法進行取余運算，以使每個鍵值對的插入位置盡量分布均勻；由于length是2的整數(shù)冪，length-1的低位就全是1，高位全部是0。在與hash值進行低位&運算時，低位的值總是與原來hash值相同，高位&運算時值為0。這就保證了不同的hash值發(fā)生碰撞的概率比較小，這樣就會使得數(shù)據(jù)在table數(shù)組中分布較均勻，查詢速度也較快。

1.5 HashMap的擴容

隨著HashMap中元素的數(shù)量越來越多，發(fā)生碰撞的概率將越來越大，所產生的子鏈長度就會越來越長，這樣勢必會影響HashMap的存取速度。為了保證HashMap的效率，系統(tǒng)必須要在某個臨界點進行擴容處理，該臨界點就是HashMap中元素的數(shù)量在數(shù)值上等于threshold（table數(shù)組長度*加載因子）。但是，不得不說，擴容是一個非常耗時的過程，因為它需要重新計算這些元素在新table數(shù)組中的位置并進行復制處理。

首先回答一個問題，在插入一個臨界節(jié)點時，HashMap是先擴容后插入還是先插入后擴容？這樣選取的優(yōu)勢是什么？

答案是：先插入后擴容。通過查看putVal方法的源碼可以發(fā)現(xiàn)是先執(zhí)行完新節(jié)點的插入后，然后再做size是否大于threshold的判斷的。

final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,
???????????????boolean?evict)?{
??...
????//如果插入新結點后的size超過了臨界值，就擴容，注意是先插入節(jié)點再擴容
????if?(++size?>?threshold)
????????resize();
????//在hashMap中，afterNodeInsertion方法體為空，交給子類去實現(xiàn)
????afterNodeInsertion(evict);
????return?null;
}

為什么是先插入后擴容？源碼已經很清楚的表達了擴容原因，調用put不一定是新增數(shù)據(jù)，還可能是覆蓋掉原來的數(shù)據(jù)，這里就存在一個key的比較問題。以先擴容為例，先比較是否是新增的數(shù)據(jù)，再判斷增加數(shù)據(jù)后是否要擴容，這樣比較會浪費時間，而先插入后擴容，就有可能在中途直接通過return返回了（本次put是覆蓋操作，size不變不需要擴容），這樣可以提高效率的。

JDK1.8相對于JDK1.7對HashMap的實現(xiàn)有較大改進，做了很多優(yōu)化，鏈表轉紅黑樹是其中的一項，其實擴容方法JDK1.8也有優(yōu)化，與JDK1.7有較大差別。

JDK1.8中resize方法源碼如下：

final?Node[]?resize()?{
????Node[]?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;
????????}
????????//?沒超過最大值，就擴容為原來的2倍
????????else?if?((newCap?=?oldCap?<1)??????????????????oldCap?>=?DEFAULT_INITIAL_CAPACITY)
????????????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);
????}
????//?計算新的resize上限，即新的threshold值
????if?(newThr?==?0)?{
????????float?ft?=?(float)newCap?*?loadFactor;
????????newThr?=?(newCap?float)MAXIMUM_CAPACITY??
??????????????????(int)ft?:?Integer.MAX_VALUE);
????}
????threshold?=?newThr;
????@SuppressWarnings({"rawtypes","unchecked"})
????????Node[]?newTab?=?(Node[])new?Node[newCap];
????table?=?newTab;
????if?(oldTab?!=?null)?{
?????//?把舊的bucket都移動到新的buckets中
????????for?(int?j?=?0;?j?????????????Node?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)e).split(this,?newTab,?j,?oldCap);
????????????????else?{?//?preserve?order
????????????????????Node?loHead?=?null,?loTail?=?null;
????????????????????Node?hiHead?=?null,?hiTail?=?null;
????????????????????Node?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);
????????????????????//?擴容后，鍵值對在新table數(shù)組中的位置與舊數(shù)組中一樣
????????????????????if?(loTail?!=?null)?{
????????????????????????loTail.next?=?null;
????????????????????????newTab[j]?=?loHead;
????????????????????}
????????????????????//?擴容后，鍵值對在新table數(shù)組中的位置與舊數(shù)組中不一樣
????????????????????//?新的位置=原來的位置?+?oldCap
????????????????????if?(hiTail?!=?null)?{
????????????????????????hiTail.next?=?null;
????????????????????????newTab[j?+?oldCap]?=?hiHead;
????????????????????}
????????????????}
????????????}
????????}
????}
????return?newTab;
}

必要的位置已經加了注釋。最讓人疑惑的有兩個點：

為什么（e.hash & oldCap）== 0時就放入lo鏈表，否則就是hi鏈表; 為什么 j + oldCap就是鍵值對在新的table數(shù)組中的位置；其實這里包含著一些數(shù)學技巧。類似于上一小節(jié)為什么HashMap中數(shù)組的長度總是取2的整數(shù)次冪。

查看源碼，我們發(fā)現(xiàn)擴容時，使用的是2次冪的擴展即長度擴為原來2倍，所以，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置?？聪聢D可以明白這句話的意思，n為table的長度，圖中上半部分表示擴容前的key1和key2兩個Node的索引位置，圖中下半部分表示擴容后key1和key2兩個Node新的索引位置。

元素在重新計算hash之后，因為n變?yōu)?倍，那么n-1在高位多1bit，因此新的index就會發(fā)生這樣的變化：

因此，我們在擴充HashMap的時候，不需要像JDK1.7的實現(xiàn)那樣重新hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”，這個設計確實非常的巧妙，既省去了重新hash值的時間，而且同時，由于新增的1bit是0還是1可以認為是隨機的，因此resize的過程，均勻的把之前的沖突的節(jié)點分散到新的bucket了，這一塊就是JDK1.8新增的優(yōu)化點。

1.6 HashMap為什么引入紅黑樹而不是AVL樹

首先要說明的是引入紅黑樹是了防止多次發(fā)生hash沖突時，鏈表長度過長，查找的時間復雜度會變成O(N)，同時同一位置再次發(fā)生hash沖突時采用尾插法插入的時間復雜度也會變成O(N)。用了紅黑樹可以把查找以及插入的時間復雜度都降低成O(logN)。

那么接下來問題就變成了：有了二叉查找樹、平衡樹（AVL）為啥還需要紅黑樹？

二叉查找樹，也稱有序二叉樹（ordered binary tree），或已排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：

若任意節(jié)點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；若任意節(jié)點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；任意節(jié)點的左、右子樹也分別為二叉查找樹; 沒有鍵值相等的節(jié)點（no duplicate nodes） 因為一棵由N個結點隨機構造的二叉查找樹的高度為logN，所以順理成章，二叉查找樹的一般操作的執(zhí)行時間為O(logN)。但二叉查找樹若退化成了一棵具有N個結點的線性鏈后，則這些操作最壞情況運行時間為O(N)。可想而知，我們不能讓這種情況發(fā)生，為了解決這個問題，于是我們引申出了平衡二叉樹，即AVL樹，它對二叉查找樹做了改進，在我們每插入一個節(jié)點的時候，必須保證每個節(jié)點對應的左子樹和右子樹的樹高度差不超過1。如果超過了就對其進行左旋或右旋，使之平衡。

雖然平衡樹解決了二叉查找樹退化為近似鏈表的缺點，能夠把查找時間控制在 O(logN)，不過卻不是最佳的，因為平衡樹要求每個節(jié)點的左子樹和右子樹的高度差至多等于1，這個要求實在是太嚴了，導致每次進行插入/刪除節(jié)點的時候，幾乎都會破壞平衡樹的規(guī)則，進而我們都需要通過左旋和右旋來進行調整，使之再次成為一顆符合要求的平衡樹。

顯然，如果在那種插入、刪除很頻繁的場景中，平衡樹需要頻繁著進行調整，這會使平衡樹的性能大打折扣，為了解決這個問題，于是有了紅黑樹。紅黑樹是不符合AVL樹的平衡條件的，即每個節(jié)點的左子樹和右子樹的高度最多差1的二叉查找樹，但是提出了為節(jié)點增加顏色，紅黑樹是用非嚴格的平衡來換取增刪節(jié)點時候旋轉次數(shù)的降低，任何不平衡都會在三次旋轉之內解決，相較于AVL樹為了維持平衡的開銷要小得多。

AVL樹是嚴格平衡樹，因此在增加或者刪除節(jié)點的時候，根據(jù)不同情況，旋轉的次數(shù)比紅黑樹要多，所以紅黑樹的插入效率相對于AVL樹更高。單單在查找方面比較效率的話，由于AVL高度平衡，因此AVL樹的查找效率比紅黑樹更高。

對主要的幾種平衡樹作個比較，發(fā)現(xiàn)紅黑樹有著良好的穩(wěn)定性和完整的功能，性能表現(xiàn)也很不錯，綜合實力強，在諸如STL的場景中需要穩(wěn)定表現(xiàn)。實際應用中，若搜索的頻率遠遠大于插入和刪除，那么選擇AVL，如果發(fā)生搜索和插入刪除操作的頻率差不多，應該選擇紅黑樹。

1.7 HashMap的線程不安全

所有人都知道HashMap是線程不安全的，我們應該使用ConcurrentHashMap。但是為什么HashMap是線程不安全的呢？

首先需要強調一點，HashMap的線程不安全體現(xiàn)在會造成死循環(huán)、數(shù)據(jù)丟失、數(shù)據(jù)覆蓋這些問題。其中死循環(huán)和數(shù)據(jù)丟失是在JDK1.7中出現(xiàn)的問題，在JDK1.8中已經得到解決，然而1.8中仍會有數(shù)據(jù)覆蓋的問題，即在并發(fā)執(zhí)行HashMap的put操作時會發(fā)生數(shù)據(jù)覆蓋的情況。

首先擴容會造成HashMap的線程不安全，根源就在JDK1.7的transfer函數(shù)中。transfer方法將原有Entry數(shù)組的元素拷貝到新的Entry數(shù)組里。JDK1.7中HashMap的transfer函數(shù)源碼如下：

void?transfer(Entry[]?newTable)?{
?//src引用了舊的Entry數(shù)組
?Entry[]?src?=?table;?
?int?newCapacity?=?newTable.length;
?//遍歷舊的Entry數(shù)組
?for?(int?j?=?0;?j???//取得舊Entry數(shù)組的每個元素
??Entry?e?=?src[j];?
??if?(e?!=?null)?{
??src[j]?=?null;
??//釋放舊Entry數(shù)組的對象引用（for循環(huán)后，舊的Entry數(shù)組不再引用任何對象）
??do?{
???Entry?next?=?e.next;
???int?i?=?indexFor(e.hash,?newCapacity);?
???//重新計算每個元素在數(shù)組中的位置
???e.next?=?newTable[i];?//標記[1]
???newTable[i]?=?e;?//將元素放在數(shù)組上
???e?=?next;?
???//訪問下一個Entry鏈上的元素
???}?while?(e?!=?null);
??}
?}
}

這段代碼是HashMap的擴容操作，重新定位每個桶的下標，并采用頭插法將元素遷移到新數(shù)組中。頭插法會將鏈表的順序翻轉，這也是在多線程環(huán)境下會形成死循環(huán)的關鍵點。擴容造成死循環(huán)和數(shù)據(jù)丟失的詳細過程這里不再贅述，可以搜索很多分析這個過程的文章。

JDK1.8的源碼中已經沒有transfer函數(shù)，因為JDK1.8直接在resize函數(shù)中完成了數(shù)據(jù)遷移。此外JDK1.8在進行元素插入時使用的是尾插法。為什么多線程環(huán)境下JDK1.8的HashMap會出現(xiàn)數(shù)據(jù)覆蓋的情況呢，我們來看一下JDK1.8中的putVal源碼：

final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,
???????????????boolean?evict)?{
????Node[]?tab;?Node?p;?int?n,?i;
????//第一次put元素時，table數(shù)組為空，先調用resize生成一個指定容量的數(shù)組
????if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)
????????n?=?(tab?=?resize()).length;
????//hash值和n-1的與運算結果為桶的位置，如果該位置空就直接放置一個Node
????if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)
????????tab[i]?=?newNode(hash,?key,?value,?null);
????//如果計算出的bucket不空，即發(fā)生哈希沖突，就要進一下判斷
????else?{
????????Node?e;?K?k;
????????//判斷當前Node的key與要put的key是否相等
????????if?(p.hash?==?hash?&&
????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????e?=?p;
????????//判斷當前Node是否是紅黑樹的節(jié)點
????????else?if?(p?instanceof?TreeNode)
????????????e?=?((TreeNode)p).putTreeVal(this,?tab,?hash,?key,?value);
????????//以上都不是，說明要new一個Node，加入到鏈表中
????????else?{
????????????for?(int?binCount?=?0;?;?++binCount)?{
?????????????//進入這個if說明是到達鏈表尾部
????????????????if?((e?=?p.next)?==?null)?{
????????????????????p.next?=?newNode(hash,?key,?value,?null);
????????????????????if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1st
????????????????????????treeifyBin(tab,?hash);
????????????????????break;
????????????????}
????????????????//在鏈表中繼續(xù)判斷是否已經存在完全相同的key
????????????????if?(e.hash?==?hash?&&
????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????????break;
????????????????p?=?e;
????????????}
????????}
????????//走到這里，說明本次put是更新一個已存在的鍵值對的value
????????if?(e?!=?null)?{?//?existing?mapping?for?key
????????????V?oldValue?=?e.value;
????????????if?(!onlyIfAbsent?||?oldValue?==?null)
????????????????e.value?=?value;
????????????//在hashMap中，afterNodeAccess方法體為空，交給子類去實現(xiàn)
????????????afterNodeAccess(e);
????????????return?oldValue;
????????}
????}
????//下面兩個自增操作都不是原子的
????++modCount;
????if?(++size?>?threshold)
????????resize();
????//在hashMap中，afterNodeInsertion方法體為空，交給子類去實現(xiàn)
????afterNodeInsertion(evict);
????return?null;
}

其中if((p = tab[i = (n - 1) & hash]) == null)是判斷是否出現(xiàn)hash碰撞，假設兩個線程A、B都在進行put操作，并且hash函數(shù)計算出的插入下標是相同的，當線程A執(zhí)行完這行代碼后由于時間片耗盡導致被掛起，而線程B得到時間片后在該下標處插入了元素，完成了正常的插入，然后線程A獲得時間片，由于之前已經進行了hash碰撞的判斷，所以此時不會再進行判斷，而是直接進行插入，這就導致了線程B插入的數(shù)據(jù)被線程A覆蓋了，從而線程不安全。

除此之外，還有就是代碼的末尾部分有個++size，我們這樣想，還是線程A、B，這兩個線程同時進行put操作時，假設當前HashMap的size大小為10，當線程A執(zhí)行到size自增這行代碼時，從主內存中獲得size的值為10后準備進行+1操作，但是由于時間片耗盡只好讓出CPU，線程B拿到CPU還是從主內存中拿到size的值10進行+1操作，完成了put操作并將size=11寫回主內存，由于size不是volatile修改的變量，然后線程A再次拿到CPU后不會再從主內存中加載一次size的值，而是使用自己工作內存中的副本，繼續(xù)執(zhí)行加1，當執(zhí)行完put操作后，還是將size=11寫回主內存，此時，線程A、B都執(zhí)行了一次put操作，但是size的值只增加了1，所有說還是由于數(shù)據(jù)覆蓋又導致了線程不安全。

2、LinkedHashMap概述

HashMap是Java Collection Framework的重要成員，也是Map族中我們最為常用的一種。不過遺憾的是，HashMap是無序的，也就是說，迭代HashMap所得到的元素順序并不是它們最初放置到HashMap的順序。HashMap的這一缺點往往會造成諸多不便，因為在有些場景中，我們確需要用到一個可以保持插入順序的Map。慶幸的是，JDK為我們解決了這個問題，它為HashMap提供了一個子類 —— LinkedHashMap。雖然LinkedHashMap增加了時間和空間上的開銷，但是它通過維護一個額外的雙向鏈表保證了迭代順序==。特別地，==該迭代順序可以是插入順序，也可以是訪問順序。因此，根據(jù)鏈表中元素的順序可以將LinkedHashMap分為：保持插入順序的LinkedHashMap和保持訪問順序的LinkedHashMap，其中LinkedHashMap的默認實現(xiàn)是按插入順序排序的。

更直觀地，下圖很好地還原了LinkedHashMap的原貌：HashMap和雙向鏈表的密切配合和分工合作造就了LinkedHashMap。特別需要注意的是，next用于維護HashMap各個桶中的Entry鏈，before、after用于維護LinkedHashMap的雙向鏈表，雖然它們的作用對象都是Entry，但是各自分離，是兩碼事兒。

特別地，由于LinkedHashMap是HashMap的子類，所以LinkedHashMap自然會擁有HashMap的所有特性。比如，LinkedHashMap也最多只允許一條Entry的鍵為Null(多條會覆蓋)，但允許多條Entry的值為Null。此外，LinkedHashMap 也是 Map 的一個非同步的實現(xiàn)。此外，LinkedHashMap還可以用來實現(xiàn)LRU (Least recently used, 最近最少使用)算法。

2.1、LinkedHashMap定義及構造函數(shù)

本質上，HashMap和雙向鏈表合二為一即是LinkedHashMap。JDK1.8中LinkedHashMap的定義源碼如下：

public?class?LinkedHashMap<K,V>
????extends?HashMap<K,V>
????implements?Map<K,V>
{
?/**
??*?HashMap.Node?subclass?for?normal?LinkedHashMap?entries.
??*/
?static?class?Entry<K,V>?extends?HashMap.Node<K,V>?{
??//再加兩個引用，分別指向前一個插入的Entry與后一個插入的Entry
?????Entry?before,?after;
?????Entry(int?hash,?K?key,?V?value,?Node?next)?{
?????????super(hash,?key,?value,?next);
?????}
?}
?
?/**
??*?The?head?(eldest)?of?the?doubly?linked?list.
??*?頭節(jié)點引用
??*/
?transient?LinkedHashMap.Entry?head;
?
?/**
??*?The?tail?(youngest)?of?the?doubly?linked?list.
??*?尾節(jié)點引用
??*/
?transient?LinkedHashMap.Entry?tail;
?
?/**
??*?The?iteration?ordering?method?for?this?linked?hash?map:?true
??*?for?access-order,?false?for?insertion-order.
??*?true表示按照訪問順序迭代，false時表示按照插入順序?
??*?@serial
??*/
?final?boolean?accessOrder;
?
?...?
}

LinkedHashMap采用的hash算法和HashMap相同，但是它重新定義了Entry。LinkedHashMap中的Entry繼承了HashMap.Node，但增加了兩個指針before 和 after，它們分別用于維護雙向鏈接列表。特別需要注意的是，next用于維護HashMap各個Node的連接順序，before、after用于維護Entry插入的先后順序。

LinkedHashMap的5大構造函數(shù)都是在HashMap的構造函數(shù)的基礎上實現(xiàn)的，分別如下：

public?LinkedHashMap(int?initialCapacity,?float?loadFactor)?{
????super(initialCapacity,?loadFactor);
????accessOrder?=?false;
}


public?LinkedHashMap(int?initialCapacity)?{
????super(initialCapacity);
????accessOrder?=?false;
}


public?LinkedHashMap()?{
????super();
????accessOrder?=?false;
}


public?LinkedHashMap(Map?m)?{
????super();
????accessOrder?=?false;
????putMapEntries(m,?false);
}

public?LinkedHashMap(int?initialCapacity,
?????????????????????float?loadFactor,
?????????????????????boolean?accessOrder)?{
????super(initialCapacity,?loadFactor);
????this.accessOrder?=?accessOrder;
}

2.2、LinkedHashMap的快速存取

在HashMap中最常用的兩個操作就是：put(Key,Value) 和 get(Key)。同樣地，在 LinkedHashMap 中最常用的也是這兩個操作。對于put(Key,Value)方法而言，LinkedHashMap完全繼承了HashMap的 put(Key,Value) 方法，只是對putVal(hash,key, value, onlyIfAbsent,evict)方法所調用的afterNodeAccess方法和afterNodeInsertion方法進行了重寫；對于get(Key)方法，LinkedHashMap則直接對它進行了重寫。下面我們結合JDK源碼看 LinkedHashMap 的存取實現(xiàn)。

HashMap的putVal源碼，上一節(jié)中已經分析過，直接來看LinkedHashMap對afterNodeAccess和afterNodeInsertion方法的實現(xiàn)：

void?afterNodeInsertion(boolean?evict)?{?//?possibly?remove?eldest
????LinkedHashMap.Entry?first;
????if?(evict?&&?(first?=?head)?!=?null?&&?removeEldestEntry(first))?{
????????K?key?=?first.key;
????????removeNode(hash(key),?key,?null,?false,?true);
????}
}

/**
?*?如果map應該刪除最老的節(jié)點，返回true
?*?這個方法在被put和putAll方法被調用，當向map中插入一個新的entry時被執(zhí)行。這個方法提供了當一個新的entry被添加到linkedHashMap中，刪除最老節(jié)點的機會。
?*?
?*?這個方法是很有用的，可以通過刪除最老節(jié)點來減少內存消耗，避免溢出。
?*?
?*?簡單的例子：這個方法的重寫將map的最大值設為100，到100時，每次增一個entry，就刪除一次最老節(jié)點。
?*?
?*?????private?static?final?int?MAX_ENTRIES?=?100;
?*
?*?????protected?boolean?removeEldestEntry(Map.Entry?eldest)?{
?*????????return?size()?>?MAX_ENTRIES;
?*?????}
?*
?*?這個方法一般不會直接修改map，而是通過返回true或者false來控制是否修改map。
?*
??*
?*?@param????eldest?最老的節(jié)點（即頭節(jié)點）
?*?@return???如果map應該刪除頭節(jié)點就返回true，否則返回false
?*/
?protected?boolean?removeEldestEntry(Map.Entry?eldest)?{
????return?false;
?}

以上afterNodeInsertion方法由于removeEldestEntry方法默認一直返回的false而無執(zhí)行意義。也就意味著如果想要讓它有意義必須重寫removeEldestEntry方法。

void?afterNodeAccess(Node?e)?{?//?move?node?to?last
????LinkedHashMap.Entry?last;
????if?(accessOrder?&&?(last?=?tail)?!=?e)?{
????????LinkedHashMap.Entry?p?=
????????????(LinkedHashMap.Entry)e,?b?=?p.before,?a?=?p.after;
????????p.after?=?null;
????????if?(b?==?null)
????????????head?=?a;
????????else
????????????b.after?=?a;
????????if?(a?!=?null)
????????????a.before?=?b;
????????else
????????????last?=?b;
????????if?(last?==?null)
????????????head?=?p;
????????else?{
????????????p.before?=?last;
????????????last.after?=?p;
????????}
????????tail?=?p;
????????++modCount;
????}
}

可見僅有accessOrder為true時，且訪問節(jié)點不等于尾節(jié)點時，該方法才有意義。通過before/after重定向，將新訪問節(jié)點鏈接為鏈表尾節(jié)點。

LinkedHashMap的get操作：

public?V?get(Object?key)?{
????Node?e;
????if?((e?=?getNode(hash(key),?key))?==?null)
????????return?null;
????//當accessOrder為true時，才會出現(xiàn)個性化邏輯
????if?(accessOrder)
????????afterNodeAccess(e);
????return?e.value;
}


//以下是HashMap中的getNode方法
final?Node?getNode(int?hash,?Object?key)?{
????Node[]?tab;?Node?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)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;
}

在LinkedHashMap的get方法中，通過HashMap中的getNode方法獲取Node對象。注意這里的afterNodeAccess方法，如果鏈表中元素的排序規(guī)則是按照插入的先后順序排序的話，該方法什么也不做；如果鏈表中元素的排序規(guī)則是按照訪問的先后順序排序的話，則將e移到鏈表的末尾處。

2.3、LinkedHashMap與LRU算法

到此為止，我們已經分析完了LinkedHashMap的存取實現(xiàn)，這與HashMap大體相同。LinkedHashMap區(qū)別于HashMap最大的一個不同點是，前者是有序的，而后者是無序的。為此，LinkedHashMap增加了兩個屬性用于保證順序，分別是雙向鏈表頭結點header和標志位accessOrder。我們知道，header是LinkedHashMap所維護的雙向鏈表的頭結點，而accessOrder用于決定具體的迭代順序。

我們知道，當accessOrder標志位為true時，表示雙向鏈表中的元素按照訪問的先后順序排列，可以看到，雖然Entry插入鏈表的順序依然是按照其put到LinkedHashMap中的順序，但put和get方法均有判斷accessOrder的值。如果accessOrder為true，put時將新插入的元素放入到雙向鏈表的尾部，get時將當前訪問的Entry移到雙向鏈表的尾部。當標志位accessOrder的值為false時，表示雙向鏈表中的元素按照Entry插入LinkedHashMap到中的先后順序排序，即每次put到LinkedHashMap中的Entry都放在雙向鏈表的尾部，這樣遍歷雙向鏈表時，Entry的輸出順序便和插入的順序一致，這也是默認的雙向鏈表的存儲順序。

測試代碼

@Test
public?void?testLinkedHashMap()?{
????Map?map?=?new?HashMap<>(128);
????System.out.println("------HashMap------");
????map.put("first",?"a");
????map.put("second",?"b");
????map.put("third",?"c");
????map.put("fourth",?"d");
????map.put("fifth",?"e");
????map.put("sixth",?"f");
????map.forEach((key,value)?->?{
????????System.out.println("key="?+?key?+?",value="?+?value);
????});

????map.clear();
????System.out.println("------LinkedHashMap------");
????map?=?new?LinkedHashMap<>(128);
????map.put("first",?"a");
????map.put("second",?"b");
????map.put("third",?"c");
????map.put("fourth",?"d");
????map.put("fifth",?"e");
????map.put("sixth",?"f");
????
????map.forEach((key,value)?->?{
????????System.out.println("key="?+?key?+?",value="?+?value);
????});
}

運行結果如下，HashMap不保證有序而LinkedHashMap默認按迭代順序和插入的順序一致。

前面介紹的LinkedHashMap的五種構造方法，前四個構造方法都將accessOrder設為false，說明默認是按照插入順序排序的；而第五個構造方法可以自定義傳入的accessOrder的值。當我們要用LinkedHashMap實現(xiàn)LRU算法時，就需要調用該構造方法并將accessOrder置為true。

使用LinkedHashMap實現(xiàn)LRU的必要前提是將accessOrder標志位設為true以便開啟按訪問順序排序的模式。我們可以看到，無論是put方法還是get方法，都會導致目標Entry成為最近訪問的Entry，因此就把該Entry加入到了雙向鏈表的末尾。這樣，我們便把最近使用的Entry放入到了雙向鏈表的后面。多次操作后，雙向鏈表前面的Entry便是最近沒有使用的，這樣當節(jié)點個數(shù)滿的時候，刪除最前面的Entry即可，因為它就是最近最少使用的Entry。

public?class?SomeTest?{
????@Test
????public?void?testLru()?{
????????LRU?lru?=?new?LRU<>(8);
????????String?s?=?"abcdefghijkl";
????????for?(int?i?=?0;?i?????????????lru.put(s.charAt(i),?i?+?1);
????????}
????????System.out.println("LRU的大?。?"?+?lru.size());
????????System.out.println(lru);
????????System.out.println("LRU的中key為h的value值：?"?+?lru.get('h'));
????????System.out.println(lru);
????????lru.put('z',?26);
????????System.out.println(lru);
????}

????public?static?class?LRU<K,?V>?extends?LinkedHashMap<K,?V>?{
????
????????private?int?cacheSize;
????
????????public?LRU(int?cacheSize)?{
????????????super(cacheSize,?0.75f,?true);
????????????this.cacheSize?=?cacheSize;
????????}
????
????????/**
?????????*?重寫LinkedHashMap中的removeEldestEntry方法，當LRU中元素多余cacheSize個時，刪除最老的節(jié)點（即最不經常使用的元素）
?????????*?@param?eldest
?????????*?@return
?????????*/
????????protected?boolean?removeEldestEntry(Map.Entry?eldest)?{
????????????return?size()?>?getCacheSize();
????????}
????
????????public?int?getCacheSize()?{
????????????return?cacheSize;
????????}
????
????}
}

運行結果：

LRU的大?。? {e=5, f=6, g=7, h=8, i=9, j=10, k=11, l=12} LRU的中key為h的value值：8 {e=5, f=6, g=7, i=9, j=10, k=11, l=12, h=8} {f=6, g=7, i=9, j=10, k=11, l=12, h=8, z=26}

推薦閱讀：
世界的真實格局分析，地球人類社會底層運行原理
不是你需要中臺，而是一名合格的架構師（附各大廠中臺建設PPT）
企業(yè)IT技術架構規(guī)劃方案
論數(shù)字化轉型——轉什么，如何轉？
企業(yè)10大管理流程圖，數(shù)字化轉型從業(yè)者必備！
【中臺實踐】華為大數(shù)據(jù)中臺架構分享.pdf
華為的數(shù)字化轉型方法論
華為如何實施數(shù)字化轉型（附PPT）
超詳細280頁Docker實戰(zhàn)文檔！開放下載
華為大數(shù)據(jù)解決方案（PPT）