作者： 一字馬胡
轉(zhuǎn)載標志 【2017-11-03】
更新日志
| 日期 | 更新內(nèi)容 | 備注 |
|---|---|---|
| 2017-11-03 | 添加轉(zhuǎn)載標志 | 持續(xù)更新 |
導入
HashMap是一種使用最為頻繁的<K,V>容器，本文將基于jdk8中HashMap的源碼來分析它的實現(xiàn)細節(jié)，來探索HashMap是如何為提升效率不斷優(yōu)化設計的，但是，無論HashMap怎么優(yōu)化怎么高效，都是在單線程環(huán)境的前提下，HashMap是不支持并發(fā)環(huán)境下使用的，因為它線程不安全，至于為什么它線程不安全，可以參考文章為什么HashMap線程不安全，這篇文章詳細說明了HashMap為什么不是線程安全的，而且該文章也粗略的分析了一下HashMap的實現(xiàn)細節(jié)，但是描述還不太充分，介于HashMap的重要性，本文將對HashMap做深度解析，并結(jié)合源碼分析來深入其內(nèi)部實現(xiàn)，希望通過分析總結(jié)，可以很好的掌握HashMap的特性，以及學習HashMap的精巧設計。
首先，HashMap是一種Map，HashMap僅是一種Map的實現(xiàn)版本，下面的圖片展示了java中Map的一些實現(xiàn)版本：
- HashMap： HashMap將根據(jù)key的hashCode值來找到存儲value的位置，如果hash函數(shù)比較完美的話，因為可以很快的找到key對應的value存儲的位置，所以具有很高的效率，需要注意的一點是，HashMap因為是基于key的hashCode值來存儲value的，所以遍歷HashMap不會保證它的順序和插入時的順序一致，可以說很大概率這個順序是不一致的，所以如果需要保持插入順序，你不可以選擇HashMap。還要一點是HashMap允許key為null，但是只允許有一個key為null，再次說明，HashMap不是線程安全的，并發(fā)環(huán)境下你應該首選ConcurrentHashMap，ConcurrentHashMap是一種高效的并發(fā)Map，它是線程安全版本的HashMap，至于它的實現(xiàn)細節(jié)分析與總結(jié)將在其他的文章中進行，本文不對它做分析。
- LinkedHashMap： LinkedHashMap是HashMap的子類，它將保持記錄的插入順序。
- TreeMap：TreeMap實現(xiàn)了SortedMap接口，很明顯，他將對插入的記錄排序，在遍歷TreeMap的時候，得到的是經(jīng)過排序的記錄，所以，如果你需要對插入的記錄做排序的話，選擇TreeMap，然后指定比較器就可以了。
介于篇幅限制，本文僅對HashMap做分析，其他的Map將安排在未來適宜的時刻進行。
HashMap內(nèi)部結(jié)構(gòu)
首先來看一下HashMap內(nèi)部結(jié)構(gòu)是什么樣子的。通過觀察源碼，可以發(fā)現(xiàn)HashMap在實現(xiàn)上使用了數(shù)組+鏈表+紅黑樹三種數(shù)據(jù)結(jié)構(gòu)，可以說在實現(xiàn)上HashMap是比較復雜的，但是這種復雜性帶來的收益是很大的，HashMap是一種非常高效的Map，這也是它為什么這么受歡迎的主要原因。下圖展示了HashMap的存儲結(jié)構(gòu)：
上文中講到，HashMap是通過計算key的hashCode來找到記錄的存儲位置的，那因為hash函數(shù)不會臺完美的原因，勢必要造成多個記錄的key的hashCode一樣的情況，上圖展示了這種情況，完美情況下，我們希望每一個數(shù)組位置上僅有一個記錄，但是很多情況下一個數(shù)組位置上會落入多個記錄，也就是哈希沖突，解決哈希沖突的方法主要有開發(fā)地址和鏈地址，HashMap采用了后者，將hashCode相同的記錄放在同一個數(shù)組位置上，多個hashCode相同的記錄被存儲在一條鏈表上，我們知道，鏈表上的查詢復雜的為O(N)，當這個N很大的時候也就成了瓶頸，所以HashMap在鏈表的長度大于8的時候就會將鏈表轉(zhuǎn)換為紅黑樹這種數(shù)據(jù)結(jié)構(gòu)，紅黑樹的查詢效率高達O(lgN)，也就是說，復雜度降了一個數(shù)量級，完全可以適用于實際生產(chǎn)環(huán)境。下面是鏈表節(jié)點數(shù)據(jù)結(jié)構(gòu)的代碼：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //哈希值，HashMap用這個值來確定記錄的位置
final K key; //記錄key
V value; //記錄value
Node<K,V> next;//鏈表下一個節(jié)點
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
下面是上面圖中展示的數(shù)組：
transient Node<K,V>[] table;
這個table就是存儲數(shù)據(jù)的數(shù)組，上面圖中的每個黑色的球是一個Node。下面展示了幾個重要的成員變量：
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
/**
* 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;
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
需要注意的一點是，HashMap的哈希桶table的大小必須為2的n次方，初始大小為16，下文中將會說明為什么一定要是2的n次方。size字段的意思是當前記錄數(shù)量，loadFactor是負載因子，默認為0.75，而threshold是作為擴容的閾值而存在的，它是由負載銀子決定的。下面的方法是返回與給定數(shù)值最接近的2的n次方的值：
/**
* 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;
}
HashMap如何確定記錄的table位置
在理解了HashMap的基本存儲結(jié)構(gòu)之后，首先來分析一下HashMap是如何確定記錄的table位置的。這是至關(guān)重要的一步，也是眾多HashMap操作的第一步，因為要想找到記錄，首先要確定記錄在table中的index，然后才能去table的index上的鏈表或者紅黑樹里面去尋找記錄。下面的方法hash展示了HashMap是如何計算記錄的hashCode值的方法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
上面的hash方法僅僅是第一步，它只是計算出了hashCode值，但是還可以確定table中的index，接下來的一步需要做的就是根據(jù)hashCode來定位index，也就是需要對hashCode取模（hashCode % length），length是table的長度，但是我們知道，取模運算是較為復雜的計算，是非常耗時的計算，那有沒有方法不通過取模計算而達到取模的效果呢，答案是肯定的，上文中提到，table的長度必然是2的n次方，這點很重要，HashMap通過設定table的長度為2的n次方，在取模的時候就可以通過下面的算法來進行：
int index = hashCode & (length -1)
在length總是2的n次方的前提下，上面的算法等效于hashCode%length，但是現(xiàn)在通過使用&代替了%，而&的效率要遠比%高，為了說明上面的算法是成立的，下面進行試驗：
hashCode = 8
length = 4
index = (8 % 4) = 0
index = 8 & (4-1) = (1000&0011) = 0
當然這種證明是沒有意義的，更為嚴謹?shù)淖C明請參考更多的資料。
HashMap插入元素的過程詳解
上面分析了HashMap計算記錄在table中的index的方法，下面來分析一下HashMap是如何將一個新的記錄插入到HashMap中去的。也就是HashMap中非常重要的方法put，下面展示了它的實現(xiàn)細節(jié)：
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<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
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))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
下面流程圖展示了put方法的執(zhí)行邏輯：
- 首先判斷table是否為null或者長度為0，如果是，那么調(diào)用方法resize來初始化table，resize的細節(jié)將在下文中進行分析，這個方法用來對HashMap的table數(shù)組擴容，它將發(fā)生在初始化table以及table中的記錄數(shù)量達到閾值之后。
- 然后計算記錄的hashCode，以及根據(jù)上文中提到的方法來計算記錄在table中的index，如果發(fā)現(xiàn)index未知上為null，則調(diào)用newNode來創(chuàng)建一個新的鏈表節(jié)點，然后放在table的index位置上，此時表面沒有哈希沖突。
- 如果table的index位置不為空，那么說明造成了哈希沖突，這時候如果記錄和index位置上的記錄相等，則直接覆蓋，否則繼續(xù)判斷
- 如果index位置上的節(jié)點TreeNode，如果是，那么說明此時的index位置上是一顆紅黑樹，需要調(diào)用putTreeVal方法來將這新的記錄插入到紅黑樹中去。否則走下面的邏輯。
- 如果index位置上的節(jié)點類型不是TreeNode，那么說明此位置上的哈希沖突還沒有達到閾值，還是一個鏈表結(jié)構(gòu)，那么就根據(jù)插入鏈表插入新節(jié)點的算法來找到合適的位置插入，這里面需要注意的是，新插入的記錄會覆蓋老的記錄，如果這個新的記錄是首次插入，那么就會插入到該index位置上鏈表的最尾部，這里面還需要一次判斷，如果插入了新的節(jié)點之后達到了閾值，那么就需要調(diào)用方法treeifyBin來講鏈表轉(zhuǎn)化為紅黑樹。
- 在插入完成之后，哈希桶中記錄的數(shù)量是否達到了哈希桶設置的閾值，如果達到了，那么就需要調(diào)用方法resize來擴容。
HashMap擴容resize方法詳解
上文分析了HashMap的put方法的細節(jié)，其中提到，當初始化table以及記錄數(shù)量達到閾值之時會觸發(fā)HashMap的擴容，而擴容是通過方法resize來進行的，下面來分析一下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;
}
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 { // 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);
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;
}
上面展示了resize方法的細節(jié)，可以看到擴容的實現(xiàn)時較為復雜的，但是我們知道所謂擴容，就是新申請一個較大容量的數(shù)組table，然后將原來的table中的內(nèi)容都重新計算哈希落到新的數(shù)組table中來，然后將老的table釋放掉。這里面有兩個關(guān)鍵點，一個是新哈希數(shù)組的申請以及老哈希數(shù)組的釋放，另外一個是重新計算記錄的哈希值以將其插入到新的table中去。首先第一個問題是，擴容會擴大到多少，通過觀察上面的代碼可以確定，每次擴容都會擴大table的容量為原來的兩倍，當然有一個最大值，如果HashMap的容量已經(jīng)達到最大值了，那么就不會再進行擴容操作了。第二個問題是HashMap是如何在擴容之后將記錄從老的table遷移到新的table中來的。上文中已經(jīng)提到，table的長度確保是2的n次方，那么有意思的是，每次擴容容量變?yōu)樵瓉淼膬杀?，那么一個記錄在新table中的位置要么就和原來一樣，要么就需要遷移到(oldCap + index)的位置上。下面簡單來證明一下這個算法的正確性：
假設原來的table大小為4，那么擴容之后會變?yōu)?，那么對于一個元素A來說，如果他的hashCode值為3，那么他在原來的table
上的位置為(3 & 3) = 3,那么新位置呢？(3 & 7) = 3,這種情況下元素A的index和原來的index是一致的不用變。再來看一個
元素B，他的hashCode值為47，那么在原來table中的位置為(47 & 3) = 3，在新table中的位置為(47 & 7) = 7，也就
是（3 + 4），正好偏移了oldCap個單位。
那么如何快速確定一個記錄遷移的位置呢？因為我們的計算方法為:(hashCode & (length - 1))，而擴容將導致(length - 1)會新增一個1，也就是說，hashCode將會多一位來做判斷，如果這個需要新判斷的位置上為0，那么index不變，否則變?yōu)樾枰w移到(oldIndex + oldCap)這個位置上去，下面舉個例子吧：
還是上面的兩個元素A和B，哈希值分別為3和47，在table長度為4的情況下，因為(3) = (11)，所以A和B會有兩位參與運算來
獲得index，A和B的二進制分別為：
3 ： 11
47： 101111
在table的length為4的前提下：
3-> 11 & 11 = 3
47-> 000011 & 101111 = 3
在擴容后，length變?yōu)?：
3-> 011 & 111 = 3
47-> 10111 & 00111 = 7
對于3來說，新增的參與運算的位為0，所以index不變，而對于47來說，新增的參與運算的位為1，所以
index需要變?yōu)?index + oldCap)
HashMap獲取記錄操作詳解
上面分析了插入記錄的操作流程，下面來分析一下HashMap是如何支持獲取記錄的操作的。我們既然知道了HashMap的結(jié)果，就應該大概猜到HashMap需要在我們獲取記錄的時候要做什么，首先，因為可能會發(fā)生哈希沖突，所以我們需要獲取的記錄可能會存儲在一個鏈表上，也可能存儲在一棵紅黑樹上，這需要實際判斷，所以，獲取操作首先應該就算記錄的hashCode，然后根據(jù)hashCode來計算在table中的index，然后判斷該數(shù)組位置上是一條鏈表還是一棵紅黑樹，如果是鏈表，那么就遍歷鏈表來找到我們需要的記錄，否則如果是一棵紅黑樹，那么就通過遍歷這棵紅黑樹找到我們需要的記錄，當然，尋找記錄可能會找不到，因為可能我們獲取的記錄根本就不存在，那么就要返回null暗示用戶，當然，HashMap返回null不僅可以代表沒有這個記錄的信息之外，還可以代表該記錄key對應著的value就是null，所以你不能通過HashMap是否返回null來判斷HashMap中是否有相應的記錄，如果你有類似的需求，你應該調(diào)用HashMap的方法：containsKey，這個方法將在下文中進行分析。
上面的分析是我們的猜測，下面來看一下HashMap是如何做的，獲取元素是通過調(diào)用HashMap的get方法來進行的，下面展示了get方法的代碼：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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;
}
首先會獲得當前table的一個快照，然后根據(jù)需要查找的記錄的key的hashCode來定位到table中的index，如果該位置為null，說明沒有沒有記錄落到該位置上，也就不存在我們查找的記錄，直接返回null。如果該位置不為null，說明至少有一個記錄落到該位置上來，那么就判斷該位置的第一個記錄是否使我們查找的記錄，如果是則直接返回，否則，根據(jù)該index上是一條鏈表還是一棵紅黑樹來分別查找我們需要的記錄，找到則返回記錄，否則返回null。下面來看一下如何判斷HashMap中是否有一個記錄的方法：
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
這個方法調(diào)用了getNode來從table中獲得一個Node，返回null，說明不存在該記錄，否則存在，containsKey方法和get方法都是通過調(diào)用getNode方法來進行的，但是他們的區(qū)別在于get方法在判斷得到的Node不為null的情況下任然可能返回null，因為Node的value可能為null，所以應該在合適的時候調(diào)用合適的方法。
HashMap刪除記錄詳解
現(xiàn)在來看一下HashMap是如何實現(xiàn)刪除一個記錄的。下面首先展示了相關(guān)的代碼：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
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 &&
((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 {
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;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
首先，通過記錄的hashCode來找到他在table中的index，因為最后需要返回被刪除節(jié)點的值，所以需要記錄被刪除的節(jié)點。當然記錄被刪除的節(jié)點也是有意義的，比如對于table中的index位置上為一條鏈表的情況來說，我們只需要記住需要刪除的Node，然后真正刪除的時候就可以只需要操作該node就可以了，當然對于鏈表的相關(guān)操作詳解將在另外的篇章中進行。以及紅黑樹等高級數(shù)據(jù)結(jié)構(gòu)的分析總結(jié)也會在新的篇章中介紹，目前只需要知道HashMap通過在合適的時候使用不同的數(shù)據(jù)結(jié)構(gòu)來達到高效的目的就可以了。
HashMap的線程安全詳解
本部分的內(nèi)容請參考為什么HashMap線程不安全，在此不再贅述。大概的意思就是因為在并發(fā)環(huán)境下，可能同一時刻有多個線程在操作HashMap，因為HashMap中沒有任何措施來保護table，所以在并發(fā)環(huán)境下多個線程是可以同時操作table的，那么比如在put的時候觸發(fā)了HashMap擴容，那么在擴容的過程中多個線程的原因可能在某個table的index上會形成一個鏈表的環(huán)，那么此后如果有線程通過get來獲取記錄的時候，如果剛好這個記錄在這個環(huán)之后，那么獲取記錄的線程就會造成死循環(huán)，更為具體的分析請參考全文。
本文分析了jdk8中的HashMap，從HashMap是如何計算記錄的hashCode的，然后到記錄插入操作，以及查詢記錄操作、刪除記錄操作等，本文的分析是更像是一種概述，并沒有深入到細節(jié)中去，比如文中提到了table中的某個index上可能是鏈表，也可能是一棵紅黑樹，但是點到為止，并沒有詳細分析HashMap是如何維護這棵紅黑樹的，在我看來，分析問題有時候需要聯(lián)想很多內(nèi)容，但是一定要有重點，本文的重點是分析HashMap的實現(xiàn)，而HashMap中用到的紅黑樹只是一種類似工具的內(nèi)容，況且這涉及到了一些更為復雜的內(nèi)容，在這種情況下，如果將多種重要且難以理解的內(nèi)容柔和在一篇文章中，會造成閱讀不順暢等問題，所以，我的做法是，在每篇文章中盡量只提到一個重要或者難以理解的內(nèi)容，這樣就可以在輕松愉快的前提下快速閱讀一篇文章。當然，類似本文中實現(xiàn)的紅黑樹的原理，實現(xiàn)等分析將一定會在另外的篇章中進行分析。
