HashMap源碼分析
1.概述
HashMap是一種基于雜湊演算法的散列查找集合.其實作方式主要是數組+連結清單. 其存儲鍵值對, 并根據鍵的哈希值作運算進行鍵值對的存儲和查詢. 當一個鍵的hash值與另一個鍵的hash值做運算後得到的在數組中位置相同, 這就說明出現了"哈希沖突", 是以采用連結清單, 将他們鍊成一條連結清單. 當這個連結清單長度過長時, 就會将該連結清單轉化為紅黑樹提高性能
而HashMap的内部數組長度初始為16, 如果需要擴充數組, 那麼規定是2的次方. 例如16會擴充到32->64->128->256…
這樣擴充是因為 :
- 1.選擇足夠大的數組, 讓鍵值對更均勻的分布在各個索引位, 盡量減少連結清單長度
- 2.當使用除留餘數法時, 能使用位運算代替模運算, 很大程度上提高效率. N % M等價于N & (M-1), M為2的次方
2.繼承關系
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
}
3.主要成員
//數組預設的初始長度, java規定hashMap的數組長度必須是2的次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//數組的最大長度
static final int MAXIMUM_CAPACITY = 1 << 30;
//預設負載因子, 當元素在數組中的個數超過這個比例就會執行數組擴容操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//樹形化臨界值, 當連結清單節點個數大于等于TREEIFY_THRESHOLD-1時, 會将該連結清單轉換為紅黑樹
static final int TREEIFY_THRESHOLD = 8;
//結束樹形化臨界值, 當連結清單節點長度小于等于這個值時, 會将該紅黑樹轉化為普通的連結清單
static final int UNTREEIFY_THRESHOLD = 6;
//最小樹形化的容量, 即:當内部數組長度小于等于這個值時, 會将紅黑樹轉化為普通的連結清單
static final int MIN_TREEIFY_CAPACITY = 64;
//HashMap内部的數組, Node是連結清單節點對象
transient Node<K,V>[] table;
//存放映射對象的set
transient Set<Map.Entry<K,V>> entrySet;
//元素個數
transient int size;
//容器結構的修改次數, fail-fast機制
transient int modCount;
//臨界值, 超過這個值時擴充數組
int threshold;
//負載因子
final float loadFactor;
3.Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//該節點的哈希值
final K key;//該節點的鍵值
V value;//該節點的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;
}
}
4.構造函數
//帶兩個參數的構造函數, 第一個是初始數組長度, 第二個是負載因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//這個方法可以将任意一個整數轉化為第一個比它大的2的次方的數
this.threshold = tableSizeFor(initialCapacity);
}
//使用預設的負載因子0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//使用預設的初始長度16
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
5.核心方法
1>tableSizeFor方法
這個方法的作用就是将一個整數轉化成一個2的次方的整數, 因為前面說過HashMap中的數組大小必須是2的次方
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;
}
2>hash方法
hash方法負責将hashCode轉化為要放在數組中的具體下标
static final int hash(Object key) {
int h;
//若key為null, 則放在下标為0的位置, 是以HashMap中key可以為null
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
那是通過哪個公式獲得數組下标呢
i = (n - 1) & hash
其中的hash就是通過hash()方法或得到的hash值.
3>put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//oblyIfAbsent : 當存入鍵值對時, 如果該key已經存在, 是否覆寫他的value. false為覆寫, true為不覆寫
//evict : 用于子類LinkedHashMap
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab : 内部數組
//p : hash對應索引位的首節點
//n : 内部數組的長度
//i : hash對應的索引位
Node<K,V>[] tab; Node<K,V> p; int n, i;
//首次put時, 内部數組為空, 進行擴充
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;
如果首節點的key和要存入的key相同, 那麼直接覆寫value的值
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 {
//從連結清單的首節點後面開始,如果存在該鍵值對, 直接覆寫舊的value
//如果不存在, 則插入在連結清單末端, 然後判斷連結清單長度書否大于7, 嘗試轉成紅黑樹
//treeifyBin會判斷數組容量是否達到64, 如果沒有則會先擴充數組
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;
}
}
//覆寫value
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方法, 流程是這樣的 :
- 1.檢查是否數組為空, 執行resize()擴充
- 2.通過hash值計算數組索引, 擷取該索引位的首節點
- 3.如果首節點為nul, 直接添加該節點到該索引位
- 4.如果首節點不為null, 那麼有三種情況
- a.key和首節點的key相同, 覆寫value
- b.如果首節點是紅黑樹節點, 添加該節點到紅黑樹
- c.如果首節點是連結清單, 将鍵值對添加到連結清單末尾, 之後會判斷長度是否達到了樹形化的臨界值, 嘗試将連結清單轉為紅黑樹
- 5.最後判斷目前元素個數是否大于threshold, 擴充數組
4>resize方法
擴充數組不隻是将數組長度翻倍, 然後将數組中的元素放進新數組那麼簡單
因為數組元素的索引是通過 hash & (n-1) 得到的, 那麼數組的長度由n變為2n, 重新計算的索引可能和原來的不一樣了
在jdk1.7中, 是通過周遊每一個元素, 每一個節點, 重新計算他們的索引值, 存入新的數組中, 稱為rehash操作
而在jdk1.8中,對此進行了優化 : 由于n變成了2n, 是以, 那麼n-1會在高位多出一位, 是以隻需要看hash值新增的那一位是0還是1就可以了. 如果是0 ,那麼索引不變; 如果是1, 那麼索引變成"原索引+oldCap"
這個優化既省去了計算hash的時間, 并且會把之前沖突的節點分散到新的索引位上
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
//無參構造: 容量為預設的16
//擴容臨界值為 容量*負載因子
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
//擴容之後可能會丢失最高位, 變為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) {
//友善GC
oldTab[j] = null;
//如果連結清單隻有一個節點, 計算出索引并放進去
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果是紅黑樹節點,執行split方法
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//此時節點是連結清單
//loHead,loTail是原連結清單的節點
Node<K,V> loHead = null, loTail = null;
//hiHead,hiTail是新連結清單的節點
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//周遊連結清單
do {
next = e.next;
//新增bit位為0的節點, 存入原連結清單
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//新增bit位為1的節點, 存入新連結清單
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;
}
總結 :
- jdk1.7中, 擴容時是依次計算數組每個索引上連結清單各節點的hash, 并以倒置的方式放進新的數組.
- jdk1.8中, 使用位運算巧妙的避開了計算哈希值, 并且能夠按本來頭到尾的順序放進新的數組中
5>get方法
//從這裡我們也可以看到, 每個鍵值對的value是可以為null的
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;
}
6.modCount值
我們注意到HashMap和其他很多集合都有一個modCount值, 這個值是用來做什麼的呢?
該字段表示list結構上被修改的次數。結構上的修改指的是那些改變了list的長度大小或者使得周遊過程中産生不正确的結果的其它方式。。作用是在使用疊代器Iterator對集合進行周遊時，用modCount來判斷集合内資料沒有發生變化，如果該值被意外更改，Iterator或者ListIterator 将抛出ConcurrentModificationException異常.
這是jdk在面對疊代周遊的時候為了避免不确定性而采取的快速失敗原則(fail-fast)。
7.jdk1.7和jdk1.8的差別
- 首先, HashMap中的key和value都是可以為空的, 如果key為空, 則hash函數傳回值為0.
- jdk1.7時, 在某一位置上出現沖突, 使用頭插法, 但是jdk1.8中使用尾插, 因為需要周遊連結清單檢測是否需要樹形化
- jdk1.7時的雜湊演算法較為複雜, 而jdk1.8比較簡單, 即key的hash值的高16位和低16位取與.
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)