HashMap 底層資料結構
- JDK 8 之前：
- JDK 8 以前 HashMap 的實作是 數組+連結清單，即使哈希函數取得再好，也很難達到元素百分百均勻分布。
- 當 HashMap 中有大量的元素都存放到同一個桶中時，這個桶下有一條長長的連結清單，極端情況HashMap 就相當于一個單連結清單，假如單連結清單有 n 個元素，周遊的時間複雜度就是 O(n)，完全失去了它的優勢。
- JDK 8:
- JDK7與JDK8中HashMap實作的最大差別就是對于沖突的處理方法。JDK 1.8 中引入了紅黑樹（查找時間複雜度為 O(logn)）,用數組+連結清單+紅黑樹的結構來優化這個問題。
代碼實作：
基于JDK8的HashMap源碼解析 - 連結清單Node節點的定義：
/** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */ static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; 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; } }- TreeNode 紅黑樹節點的定義：
// Tree bins /** * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn * extends Node) so can be used as extension of either regular or * linked node. */ static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } - 整體結構：
/** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */ 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;
常見概念解釋
- 根據結構圖來了解常見概念：
基于JDK8的HashMap源碼解析 - 一般将數組中的每一個元素稱作桶（segment），桶中連的連結清單或者紅黑樹中的每一個元素成為bin
-
capacity： 源碼中沒有将它作為屬性，但是為了友善，引進了這個概念，是指HashMap中桶的數量。預設值為16。擴容是按照原容量的2倍進行擴。如果在構造函數中指定了Map的大小，那麼進行put操作時，初始化後的容量為離傳入值最近的2的整數幂，是通過tableSizeFor() 函數達到該目的。總之，容量都是2的幂。
設計成16的好處在《全網把Map中的hash()分析的最透徹的文章，别無二家。》中也簡單介紹過，主要是可以使用按位與替代取模來提升hash的效率。
關于此方法，具體解析見HashMap源碼注解 之 靜态工具方法hash()、tableSizeFor()（四）/** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = cap - ; n |= n >>> ; n |= n >>> ; n |= n >>> ; n |= n >>> ; n |= n >>> ; return (n < ) ? : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + ; } - loadFactor: 譯為裝載因子。裝載因子用來衡量HashMap滿的程度。loadFactor的預設值為0.75f。計算HashMap的實時裝載因子的方法為：size/capacity，而不是占用桶的數量去除以capacity。
- threshold: threshold表示當HashMap的size大于threshold時會執行resize操作。
- DEFAULT_INITIAL_CAPACITY : 預設初始化容量 16。容量必須為2的次方。預設的hashmap大小為16.
- MAXIMUM_CAPACITY :最大的容量大小2^30
-
DEFAULT_LOAD_FACTOR: 預設resize的因子。0.75，即實際數量超過總數DEFAULT_LOAD_FACTOR的數量即會發生resize動作。
為什麼是0.75，網上有些答案說是，因為capcity是2的次方，那麼與之相乘會得到整數。還有一種說法更為可靠，負載因子0.75是對空間和時間效率的一個平衡選擇，建議大家不要修改，除非在時間和空間比較特殊的情況下，如果記憶體空間很多而又對時間效率要求很高，可以降低負載因子Load factor的值；相反，如果記憶體空間緊張而對時間效率要求不高，可以增加負載因子loadFactor的值，這個值可以大于1。
- TREEIFY_THRESHOLD: 樹化門檻值 8。當單個segment的容量超過門檻值時，将連結清單轉化為紅黑樹。
- UNTREEIFY_THRESHOLD :連結清單化門檻值 6。當resize後或者删除操作後單個segment的容量低于門檻值時，将紅黑樹轉化為連結清單。
- MIN_TREEIFY_CAPACITY ：最小樹化容量 64。當桶中的bin被樹化時最小的hash表容量，低于該容量時不會樹化。
HashMap擴容及其樹化的具體過程
-
如果在建立 HashMap 執行個體時沒有給定capacity、loadFactor則預設值分别是16和0.75。
當好多bin被映射到同一個桶時，如果這個桶中bin的數量小于等于TREEIFY_THRESHOLD當然不會轉化成樹形結構存儲；如果這個桶中bin的數量大于了 TREEIFY_THRESHOLD ，但是capacity小于MIN_TREEIFY_CAPACITY 則依然使用連結清單結構進行存儲，此時會對HashMap進行擴容；如果capacity大于了MIN_TREEIFY_CAPACITY ，才有資格進行樹化(當bin的個數大于8時)。
- 具體示範見 HashMap的擴容及樹化過程
hash 值的計算
- 根據存入的key-value對中的key計算出對應的hash值，然後放入對應的桶中，是以好的hash值計算方法十分重要，可以大大避免哈希沖突。
- HashMap是以hash操作作為散列依據。但是又與傳統的hash存在着少許的優化。其hash值是key的hashcode與其hashcode右移16位的異或結果。在put方法中，将取出的hash值與目前的hashmap容量-1進行與運算。得到的就是位桶的下标。那麼為何需要使用key.hashCode() ^ h>>>16的方式來計算hash值呢。其實從微觀的角度來看，這種方法與直接去key的哈希值傳回在功能實作上沒有差别。但是由于最終擷取下表是對二進制數組最後幾位的與操作。是以直接取hash值會丢失高位的資料，進而增大沖突引起的可能。由于hash值是32位的二進制數。将高位的16位于低位的16位進行異或操作，即可将高位的資訊存儲到低位。是以該函數也叫做擾亂函數。目的就是減少沖突出現的可能性。而官方給出的測試報告也驗證了這一點。直接使用key的hash算法與擾亂函數的hash算法沖突機率相差10%左右。
static final int hash(Object key) {
int h;
return (key == null) ? : (h = key.hashCode()) ^ (h >>> );
}
n = table.length;
index = （n-） & hash;
- 根據以上可知，hashcode是一個32位的值，用高16位與低16位進行異或，原因在于求index是是用
（n-1） & hash
-
為什麼capcity是2的幂？
因為 算index時用的是
（n-1） & hash
- 在算index時，用位運算
（n-1） & hash
hash % n
- 位運算消耗資源更少，更有效率
- 避免了hashcode為負數的情況
- jdk 7中hash的計算方式有所不同：
基于JDK8的HashMap源碼解析
- hashtable， hashmap,以及concurrentHashMap的hash值計算方法都不一樣，具體請參閱 全網把Map中的hash()分析的最透徹的文章，别無二家。
put 操作
- put 操作的主要流程如下：
基于JDK8的HashMap源碼解析 ①.判斷鍵值對數組table[i]是否為空或為null，否則執行resize()進行擴容；
②.根據鍵值key計算hash值得到插入的數組索引i，如果table[i]==null，直接建立節點添加，轉向⑥，如果table[i]不為空，轉向③；
③.判斷table[i]的首個元素是否和key一樣，如果相同直接覆寫value，否則轉向④，這裡的相同指的是hashCode以及equals；
④.判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向⑤；
⑤.周遊table[i]，判斷連結清單長度是否大于8，大于8的話把連結清單轉換為紅黑樹，在紅黑樹中執行插入操作，否則進行連結清單的插入操作；周遊過程中若發現key已經存在直接覆寫value即可；
⑥.插入成功後，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，進行擴容。
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//初始化時，map中還沒有key-value
if ((tab = table) == null || (n = tab.length) == )
//利用resize生成對應的tab[]數組
n = (tab = resize()).length;
if ((p = tab[i = (n - ) & 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))))
//桶内第一個元素的key等于待放入的key，用
e = p;
else if (p instanceof TreeNode)
//如果此時桶内已經樹化
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//桶内還是一個連結清單，則插傳入連結尾（尾插）
for (int binCount = ; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - ) // -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;
}
resize 擴容操作
- resize擴容操作主要用在兩處：
- 向一個空的HashMap中執行put操作時，會調用resize()進行初始化，要麼預設初始化，capacity為16，要麼根據傳入的值進行初始化
- put操作後，檢查到size已經超過threshold，那麼便會執行resize，進行擴容，如果此時capcity已經大于了最大值，那麼便把threshold置為int最大值，否則，對capcity,threshold進行擴容操作。
- 發生了擴容操作，那麼必須Map中的所有的數進行再散列，重新裝入。
具體擴容圖如下：将一個原先capcity為16的擴容成32的：
在擴充HashMap的時候，不需要像JDK1.7的實作那樣重新計算hash，隻需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變（因為任何數與0與都依舊是0），是1的話index變成“原索引+oldCap”。
例如：n為table的長度，圖（a）表示擴容前的key1和key2兩種key确定索引位置的示例，圖（b）表示擴容後key1和key2兩種key确定索引位置的示例，其中hash1是key1對應的哈希與高位運算結果。
元素在重新計算hash之後，因為n變為2倍，那麼n-1的mask範圍在高位多1bit(紅色)，是以新的index就會發生這樣的變化：
jdk 7 與 jdk 8 中關于HashMap的對比
- 8時紅黑樹+連結清單+數組的形式，當桶内元素大于8時，便會樹化
- hash值的計算方式不同
- 1.7 table在建立hashmap時配置設定空間，而1.8在put的時候配置設定，如果table為空，則為table配置設定空間。
- 在發生沖突，插傳入連結中時，7是頭插法，8是尾插法。
- 在resize操作中，7需要重新進行index的計算，而8不需要，通過判斷相應的位是0還是1，要麼依舊是原index，要麼是oldCap + 原index
同類文章
- Java8源碼-HashMap
- 相關面試題：
基于JDK8的HashMap源碼解析