HashMap源碼分析，看一遍就懂！
作者：PlayInJava
HashMap最早出現(xiàn)在JDK1.2中，底層基于散列算法實現(xiàn)。HashMap 允許 null 鍵和 null 值，是非線程安全類，在多線程環(huán)境下可能會存在問題。
簡介
HashMap最早出現(xiàn)在JDK1.2中，底層基于散列算法實現(xiàn)。HashMap 允許 null 鍵和 null 值，是非線程安全類，在多線程環(huán)境下可能會存在問題。
1.8版本的HashMap數(shù)據(jù)結(jié)構(gòu)：
為什么有的是鏈表有的是紅黑樹？
默認(rèn)鏈表長度大于8時轉(zhuǎn)為樹。
結(jié)構(gòu)
Node是HhaspMap中的一個靜態(tài)內(nèi)部類 ：
//Node是單向鏈表，實現(xiàn)了Map.Entry接口
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//構(gòu)造函數(shù)
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
// getter and setter ... toString ...
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 是紅黑樹的數(shù)據(jù)結(jié)構(gòu)。
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);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}類定義
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable變量
/**
* 默認(rèn)初始容量16(必須是2的冪次方)
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* 最大容量，2的30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默認(rèn)加載因子，用來計算threshold
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 鏈表轉(zhuǎn)成樹的閾值，當(dāng)桶中鏈表長度大于8時轉(zhuǎn)成樹
threshold = capacity * loadFactor
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 進行resize操作時，若桶中數(shù)量少于6則從樹轉(zhuǎn)成鏈表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 桶中結(jié)構(gòu)轉(zhuǎn)化為紅黑樹對應(yīng)的table的最小大小
當(dāng)需要將解決 hash 沖突的鏈表轉(zhuǎn)變?yōu)榧t黑樹時，
需要判斷下此時數(shù)組容量，
若是由于數(shù)組容量太?。ㄐ∮凇IN_TREEIFY_CAPACITY?。? 導(dǎo)致的 hash 沖突太多，則不進行鏈表轉(zhuǎn)變?yōu)榧t黑樹操作，
轉(zhuǎn)為利用 resize() 函數(shù)對 hashMap 擴容
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
保存Node<K,V>節(jié)點的數(shù)組
該表在首次使用時初始化，并根據(jù)需要調(diào)整大小。 分配時，
長度始終是2的冪。
*/
transient Node<K,V>[] table;
/**
* 存放具體元素的集
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* 記錄 hashMap 當(dāng)前存儲的元素的數(shù)量
*/
transient int size;
/**
* 每次更改map結(jié)構(gòu)的計數(shù)器
*/
transient int modCount;
/**
* 臨界值 當(dāng)實際大小(容量*填充因子)超過臨界值時，會進行擴容
*/
int threshold;
/**
* 負(fù)載因子：要調(diào)整大小的下一個大小值（容量*加載因子）。
*/
final float loadFactor;構(gòu)造方法
/**
* 傳入初始容量大小，使用默認(rèn)負(fù)載因子值 來初始化HashMap對象
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 默認(rèn)容量和負(fù)載因子
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* 傳入初始容量大小和負(fù)載因子 來初始化HashMap對象
*/
public HashMap(int initialCapacity, float loadFactor) {
// 初始容量不能小于0，否則報錯
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 初始容量不能大于最大值，否則為最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//負(fù)載因子不能小于或等于0，不能為非數(shù)字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 初始化負(fù)載因子
this.loadFactor = loadFactor;
// 初始化threshold大小
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 找到大于或等于 cap 的最小2的整數(shù)次冪的數(shù)。
*/
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;
}tableSizeFor方法詳解：
用位運算找到大于或等于 cap 的最小2的整數(shù)次冪的數(shù)。比如10，則返回16
- 讓cap-1再賦值給n的目的是使得找到的目標(biāo)值大于或等于原值。例如二進制0100,十進制是4,若不減1而直接操作，答案是0001 0000十進制是16，明顯不符合預(yù)期。
- 對n右移1位：001xx…xxx，再位或：011xx…xxx
- 對n右移2位：00011…xxx，再位或：01111…xxx
- 對n右移4位…
- 對n右移8位…
- 對n右移16位,因為int最大就2^32所以移動1、2、4、8、16位并取位或,會將最高位的1后面的位全變?yōu)?。
- 再讓結(jié)果n+1，即得到了2的整數(shù)次冪的值了。
附帶一個實例：
loadFactor 負(fù)載因子
對于 HashMap 來說，負(fù)載因子是一個很重要的參數(shù)，該參數(shù)反應(yīng)了 HashMap 桶數(shù)組的使用情況。通過調(diào)節(jié)負(fù)載因子，可使 HashMap 時間和空間復(fù)雜度上有不同的表現(xiàn)。
當(dāng)我們調(diào)低負(fù)載因子時，HashMap 所能容納的鍵值對數(shù)量變少。擴容時，重新將鍵值對存儲新的桶數(shù)組里，鍵的鍵之間產(chǎn)生的碰撞會下降，鏈表長度變短。此時，HashMap 的增刪改查等操作的效率將會變高，這里是典型的拿空間換時間。相反，如果增加負(fù)載因子（負(fù)載因子可以大于1），HashMap 所能容納的鍵值對數(shù)量變多，空間利用率高，但碰撞率也高。這意味著鏈表長度變長，效率也隨之降低，這種情況是拿時間換空間。至于負(fù)載因子怎么調(diào)節(jié)，這個看使用場景了。
一般情況下，我們用默認(rèn)值就可以了。大多數(shù)情況下0.75在時間跟空間代價上達到了平衡所以不建議修改。
查找
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 獲取hash值
static final int hash(Object key) {
int h;
// 拿到key的hash值后與其五符號右移16位取與
// 通過這種方式，讓高位數(shù)據(jù)與低位數(shù)據(jù)進行異或，以此加大低位信息的隨機性，變相的讓高位數(shù)據(jù)參與到計算中。
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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) {
// 判斷桶中第一項(數(shù)組元素)相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 桶中不止一個結(jié)點
if ((e = first.next) != null) {
// 是否是紅黑樹，是的話調(diào)用getTreeNode方法
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;
}注意：
- HashMap的hash算法(hash()方法)。
- (n - 1) & hash等價于對 length 取余。
添加
public V put(K key, V value) {
// 調(diào)用hash(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;
// 容量初始化：當(dāng)table為空，則調(diào)用resize()方法來初始化容器
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//確定元素存放在哪個桶中，桶為空，新生成結(jié)點放入桶中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 比較桶中第一個元素(數(shù)組中的結(jié)點)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果鍵的值以及節(jié)點 hash 等于鏈表中的第一個鍵值對節(jié)點時，則將 e 指向該鍵值對
e = p;
// 如果桶中的引用類型為 TreeNode，則調(diào)用紅黑樹的插入方法
else if (p instanceof TreeNode)
// 放入樹中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//對鏈表進行遍歷，并統(tǒng)計鏈表長度
for (int binCount = 0; ; ++binCount) {
// 到達鏈表的尾部
if ((e = p.next) == null) {
//在尾部插入新結(jié)點
p.next = newNode(hash, key, value, null);
// 如果結(jié)點數(shù)量達到閾值，轉(zhuǎn)化為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 判斷鏈表中結(jié)點的key值與插入的元素的key值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//判斷要插入的鍵值對是否存在 HashMap 中
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 表示是否僅在 oldValue 為 null 的情況下更新鍵值對的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 鍵值對數(shù)量超過閾值時，則進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}事實上，new HashMap();完成后，如果沒有put操作，是不會分配存儲空間的。
- 當(dāng)桶數(shù)組 table 為空時，通過擴容的方式初始化 table。
- 查找要插入的鍵值對是否已經(jīng)存在，存在的話根據(jù)條件判斷是否用新值替換舊值。
- 如果不存在，則將鍵值對鏈入鏈表中，并根據(jù)鏈表長度決定是否將鏈表轉(zhuǎn)為紅黑樹。
- 判斷鍵值對數(shù)量是否大于閾值，大于的話則進行擴容操作。
擴容機制
在 HashMap 中，桶數(shù)組的長度均是2的冪，閾值大小為桶數(shù)組長度與負(fù)載因子的乘積。當(dāng) HashMap 中的鍵值對數(shù)量超過閾值時，進行擴容。
HashMap 按當(dāng)前桶數(shù)組長度的2倍進行擴容，閾值也變?yōu)樵瓉淼?倍（如果計算過程中，閾值溢出歸零，則按閾值公式重新計算）。擴容之后，要重新計算鍵值對的位置，并把它們移動到合適的位置上去。
final Node<K,V>[] resize() {
// 拿到數(shù)組桶
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果數(shù)組桶的容量大與0
if (oldCap > 0) {
// 如果比最大值還大，則賦值為最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果擴容后小于最大值 而且 舊數(shù)組桶大于初始容量16， 閾值左移1(擴大2倍)
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 如果數(shù)組桶容量<=0 且 舊閾值 >0
else if (oldThr > 0) // initial capacity was placed in threshold
// 新容量=舊閾值
newCap = oldThr;
// 如果數(shù)組桶容量<=0 且 舊閾值 <=0
else { // zero initial threshold signifies using defaults
// 新容量=默認(rèn)容量
newCap = DEFAULT_INITIAL_CAPACITY;
// 新閾值= 負(fù)載因子*默認(rèn)容量
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新閾值為0
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"})
// 創(chuàng)建新數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 覆蓋數(shù)組桶
table = newTab;
// 如果舊數(shù)組桶不是空，則遍歷桶數(shù)組，并將鍵值對映射到新的桶數(shù)組中
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;
// 遍歷鏈表，并將鏈表節(jié)點按原順序進行分組
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;
}整體步驟：
- 計算新桶數(shù)組的容量 newCap 和新閾值 newThr
- 根據(jù)計算出的 newCap 創(chuàng)建新的桶數(shù)組，桶數(shù)組 table 也是在這里進行初始化的
- 將鍵值對節(jié)點重新映射到新的桶數(shù)組里。如果節(jié)點是 TreeNode 類型，則需要拆分紅黑樹。如果是普通節(jié)點，則節(jié)點按原順序進行分組。
總結(jié)起來，一共有三種擴容方式：
- 使用默認(rèn)構(gòu)造方法初始化HashMap。從前文可以知道HashMap在一開始初始化的時候會返回一個空的table，并且thershold為0。因此第一次擴容的容量為默認(rèn)值DEFAULT_INITIAL_CAPACITY也就是16。同時threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。
- 指定初始容量的構(gòu)造方法初始化HashMap。那么從下面源碼可以看到初始容量會等于threshold，接著threshold = 當(dāng)前的容量（threshold） * DEFAULT_LOAD_FACTOR。
- HashMap不是第一次擴容。如果HashMap已經(jīng)擴容過的話，那么每次table的容量以及threshold量為原有的兩倍。
細(xì)心點的人會很好奇，為什么要判斷l(xiāng)oadFactor為0呢？
loadFactor小數(shù)位為 0，整數(shù)位可被2整除且大于等于8時，在某次計算中就可能會導(dǎo)致 newThr 溢出歸零。
疑問和進階
1、JDK1.7是基于數(shù)組+單鏈表實現(xiàn)（為什么不用雙鏈表）
首先，用鏈表是為了解決hash沖突。
單鏈表能實現(xiàn)為什么要用雙鏈表呢?(雙鏈表需要更大的存儲空間)
2、為什么要用紅黑樹，而不用平衡二叉樹？
插入效率比平衡二叉樹高，查詢效率比普通二叉樹高。所以選擇性能相對折中的紅黑樹。
3、重寫對象的Equals方法時，要重寫hashCode方法，為什么？跟HashMap有什么關(guān)系？
equals與hashcode間的關(guān)系:
- 如果兩個對象相同（即用equals比較返回true），那么它們的hashCode值一定要相同。
- 如果兩個對象的hashCode相同，它們并不一定相同(即用equals比較返回false)。
因為在 HashMap 的鏈表結(jié)構(gòu)中遍歷判斷的時候，特定情況下重寫的 equals 方法比較對象是否相等的業(yè)務(wù)邏輯比較復(fù)雜，循環(huán)下來更是影響查找效率。所以這里把 hashcode 的判斷放在前面，只要 hashcode 不相等就玩兒完，不用再去調(diào)用復(fù)雜的 equals 了。很多程度地提升 HashMap 的使用效率。
所以重寫 hashcode 方法是為了讓我們能夠正常使用 HashMap 等集合類，因為 HashMap 判斷對象是否相等既要比較 hashcode 又要使用 equals 比較。而這樣的實現(xiàn)是為了提高 HashMap 的效率。
附上源碼圖：
4、HashMap為什么不直接使用對象的原始hash值呢?
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}我們發(fā)現(xiàn)，HashMap的哈希值是通過上面的方式獲取，而不是通過key.hashCode()方法獲取。
原因：
通過移位和異或運算，可以讓 hash 變得更復(fù)雜，進而影響 hash 的分布性。
5、既然紅黑樹那么好，為啥hashmap不直接采用紅黑樹，而是當(dāng)大于8個的時候才轉(zhuǎn)換紅黑樹？
因為紅黑樹需要進行左旋，右旋操作， 而單鏈表不需要。
以下都是單鏈表與紅黑樹結(jié)構(gòu)對比。
如果元素小于8個，查詢成本高，新增成本低。
如果元素大于8個，查詢成本低，新增成本高。
至于為什么選數(shù)字8，是大佬折中衡量的結(jié)果-.-，就像loadFactor默認(rèn)值0.75一樣。
責(zé)任編輯：姜華
來源：
今日頭條
