關于HashMap的源碼,網上文章多如沙海,本文隻關注其中幾個有意思的地方!
JDK版本: 1.8.0_151
知識點盤點
1.
的二進制表示,隻有最高位是1,其餘的都是0,而
則全部二進制位都是1,如下圖所示
2. Java中的位運算符:
- &: 位與操作,全1則1,有0則0
- | : 位或操作, 有1則1,全0則0
- ^: 異或操作,相同則1,不同則0
- >> : 右移,如果這個數是正數,則高位補0,如果是負數,則高位補1
- >>>: 無符号右移,無論正負,高位補0
- <<: 左移,不分正負,低位補0
3. 一點兒結論:
- 一個任意的int值a對 進行&操作,即 a & (
HashMap中有意思的方法!關于HashMap的源碼,網上文章多如沙海,本文隻關注其中幾個有意思的地方! ),結果等同于 a%HashMap中有意思的方法!關于HashMap的源碼,網上文章多如沙海,本文隻關注其中幾個有意思的地方! 。就是取模值;HashMap中有意思的方法!關于HashMap的源碼,網上文章多如沙海,本文隻關注其中幾個有意思的地方! - 一個任意的int值a對 進行&操作,即 a &
HashMap中有意思的方法!關于HashMap的源碼,網上文章多如沙海,本文隻關注其中幾個有意思的地方! ,結果如果是0,那麼 a %HashMap中有意思的方法!關于HashMap的源碼,網上文章多如沙海,本文隻關注其中幾個有意思的地方! = a % (HashMap中有意思的方法!關于HashMap的源碼,網上文章多如沙海,本文隻關注其中幾個有意思的地方! *2),如果不是0,那麼 a % (HashMap中有意思的方法!關于HashMap的源碼,網上文章多如沙海,本文隻關注其中幾個有意思的地方! *2)= a %HashMap中有意思的方法!關于HashMap的源碼,網上文章多如沙海,本文隻關注其中幾個有意思的地方! +HashMap中有意思的方法!關于HashMap的源碼,網上文章多如沙海,本文隻關注其中幾個有意思的地方! HashMap中有意思的方法!關于HashMap的源碼,網上文章多如沙海,本文隻關注其中幾個有意思的地方!
HashMap中的方法
1. 取hash的方法
// put之前,先對key進行取hash操作
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 擾動函數,盡量避免hash碰撞
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
從取hash的方法中,可以看出如果key是null,則直接傳回0,是以map允許存null,
如果key不是null,則就取key的hashCode與hashCode >>> 16的 異或操作值。稱這個函數為擾動函數。
2. tableSizeFor(int cap) 根據傳入值擷取大于此值的最小的2的m次方。
/**
* 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;
}
首先 n |= n >>> 1 相當于 n = n | n >>> 1 。 首先n值的最高位肯定是1,右移1位,做位或操作的結果是,第1,2高位是1;然後右移2位,做位或操作的結果是,第1,2,3,4位是1,右移4位,同理,前8位一定是1, 最終理論上所有位上都會變成1, 最終在加上1,則是大于這個n值的最小2的m次方;(關于最大值校驗,則不再叙述)如圖
3. putVal()方法中的取模操作
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 {
...
}
我們關注在(n - 1) & hash這個操作上,首先n是tab.length(),也就是hashMap中的“哈希桶”的數量,這個值一定是2的m次方,hash值與(n-1)進行&操作後的結果就是 hash%n ,也就是這個key應該在的桶的索引。
4. resize()方法,2倍擴容方案
final Node<K,V>[] resize() {
...
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 清空原來的桶的node,此時原來的Node值已經賦給了e
oldTab[j] = null;
// 如果隻有這一個值,那麼直接進行和put方法中相同的hash操作即可。
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是紅黑樹,則進行紅黑樹的rehash操作,流程和下面的連結清單一樣。
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;
}
...
}
我們隻關注标注中有意思的部分,key的hash對oldCap進行 & 操作,結果是啥呢? 因為oldCap是2的m次方,是以它的二進制表示中,隻有最高位是1, 是以 hash & oldCap的結果不是0就是
。而對這兩種結果,有一下特點,如圖:
如果不對之處,請大家指出,謝謝!!