HashMap源碼分析（2）
這幾天沒法出門，一直待在家裡，想着在家也要保持好狀态，好好學習，就想給自己找點事幹。剛好之前的一篇部落格對hashmap分析的不是很透徹，剛好趁現在的時間，好好寫寫部落格，同時也提高一下自己。學疏才淺，有不當之處，望指出。
java version ：jdk 1.8
1. 構造方法
慣例，先看源碼
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;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
在分析這四個構造方法之前，還需要了解hashmap中的幾個屬性，
- loadFactor : 裝載因子
- threshold : 擴容門檻值，也就是說當hashmap中的資料個數超過這個門檻值，就擴容
hashmap前三個構造方法都是初始化參數，在這些構造方法中并沒有初始化節點數組，而是初始化了裝載因子和擴容門檻值這兩個參數，在
put
方法中根據擴容門檻值來初始化數組。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
由此可以看出初始化數組使用的是
resize()
方法。
final Node<K,V>[] resize() {
// 這段代碼中關于擴容的分支被我删除了，留下的都是初始化數組的分支
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;// 舊容量，初始化數組時為0
int oldThr = threshold;
int newCap, newThr = 0;
if (oldThr > 0) // 是否指定了數組大小
newCap = oldThr;
else { //使用預設參數
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;
return newTab;
}
構造方法一中還使用了另一個方法
this.threshold = tableSizeFor(initialCapacity)
，也就是說既指定了初始容量又指定了裝載因子時，使用這個方法确定擴容門檻值。
static final int tableSizeFor(int cap) {
// Integer.numberOfLeadingZeros(cap - 1)`方法傳回32位int類型數高位的0的個數。這裡的源碼巧妙地使用了二分法使用了四次右移操作，找出了高位0個數
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
這個方法的作用是找到大于等于
initialCapacity
的最小的 2 的幂。假設輸入的值是10
cap = 10,cap - 1 = 9,高位的0有28個
n = -1 >>> 28
源碼 10000000000000000000000000000001
反碼 11111111111111111111111111111110
補碼 11111111111111111111111111111111
右移 00000000000000000000000000001111
n = 8 + 4 + 2 + 1 = 15
n + 1 = 16
分析以上源碼我們知道，如果預設不傳入參數，那麼hashmap初始化為大小為16，裝載因子為0.75的數組。如果傳入的有初始容量，那麼數組大小會被初始化為大于等于給定值的最小的2的幂。之是以是2的幂，在之後求數組索引時會用到。
2. put方法
慣例，先看源碼
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)
// 數組未初始化則調用resize初始化
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;
}
具體的代碼執行流程上一篇部落格裡已經分析了，這裡隻分析幾點。
- hash方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hashmap的
hash
方法會首先調用key的
hashCode()
方法，得到一個int類型的值，然後将其右移16位，并于原來的值按位異或運算。這麼做的原因是，為了有更好的散列性同時又有較好的性能。因為計算數組下标時（
p = tab[i = (n - 1) & hash]
）是僅有hash值的低位參與運算，而這個方法将原來的值高位與低位異或之後放到低位，将高位也參與到運算中，是以具有較好的散列性。同時隻是進行異或運算，也減小了系統開銷。1
-
插入null鍵值對
從
hash
p = tab[i = (n - 1) & hash]
3. 擴容操作
慣例，先看源碼
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
}
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;
}
因為hashmap擴容之後大小為原來的二倍，舊數組中的元素在新數組中會重新計算下标。計算的方法是數組容量的值減一後與元素key的hash值做與運算。是以對于每個元素會有兩種情況。
- 假設數組容量為16
cap - 1 = 15 = 1111
key1 00000000000000000000000000011001
cap-1 00000000000000000000000000001111
hash1 00000000000000000000000000001001 = 9
key1 00000000000000000000000000001001
cap-1 00000000000000000000000000001111
hash1 00000000000000000000000000001001 = 9
- 擴容之後數組容量為32
cap - 1 = 31 = 11111
key1 00000000000000000000000000011001
cap-1 00000000000000000000000000011111
hash1 00000000000000000000000000011001 = 25
key1 00000000000000000000000000001001
cap-1 00000000000000000000000000011111
hash1 00000000000000000000000000001001 = 9
也就是說，擴容後每個元素，要麼在原來的位置，要麼移動到原來的位置加上oldcap所在的位置。
4. hashmap線程不安全的原因
- 因為hashmap的put方法不是同步的，假如有兩個線程同時put兩個hash值相同的資料，那麼不管是頭插法還是尾插法，最終一定會有一個資料丢失。
- jdk1.8之前，hahsmap插入元素使用頭插法，多線程操作時，會出現循環連結清單，此時get資料時會造成死循環。
-
p = tab[i = (n - 1) & hash]
00001111
![java HashMap 與HashTable的差別[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)