摘要：觀光線路圖將涉及到的源碼全局變量哈希表初始化長(zhǎng)度默認(rèn)值是負(fù)載因子默認(rèn)表示的填滿程度。根據(jù)是否為零將原鏈表拆分成個(gè)鏈表，一部分仍保留在原鏈表中不需要移動(dòng)，一部分移動(dòng)到原索引的新鏈表中。
前言
本文以jdk1.8中HashMap.putAll()方法為切入點(diǎn)，分析其中難理解、有價(jià)值的源碼片段（類似ctrl+鼠標(biāo)左鍵查看的源碼過程）。?觀光線路圖：putAll() --> putMapEntries() --> tableSizeFor() --> resize() --> hash() --> putVal()...
將涉及到的源碼全局變量：
transient Node[] table; 哈希表,初始化長(zhǎng)度length(默認(rèn)值是16)
final float loadFactor; 負(fù)載因子（默認(rèn)0.75）,表示table的填滿程度。
static final int MAXIMUM_CAPACITY = 1 << 30; 最大容量
int threshold; 閾值 = table.length loadFactor(160.75=12)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 初始16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
前置知識(shí)：
? extends K: 泛型通配符
好了，帶全設(shè)備、干糧，準(zhǔn)備出發(fā)~
putAll
public void putAll(Map m) {
putMapEntries(m, true); // ↓
}
putMapEntries
final void putMapEntries(Map m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F; // ft即table此時(shí)所需capacity，“+1.0F”為什么，個(gè)人理解彌補(bǔ)float與int轉(zhuǎn)換、比較精度彌補(bǔ)，加二也未嘗不可?
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t); // ↓
}
else if (s > threshold)
resize(); // ↓
// 筆者疑問：原map加上m后可能需要擴(kuò)容的判斷在putVal中，在此是不是更佳呢？答：因?yàn)槌酥膺€有其他函數(shù)調(diào)用了putVal
for (Map.Entry e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
tableSizeFor
// 找到大于等于cap的最小的2的冪（3的最小2的冪=4；4->4；5->8...）
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;
}
這里的“-1”可以理解為是為了++保證結(jié)果值≥原值++。舉個(gè)栗子，假如cap=8（1000）。計(jì)算結(jié)果為16(10000)。這顯然不是我們想要的最小的2的冪。
關(guān)于抑或、右移的計(jì)算過程，我以size=3為例，可以參考便于理解：
不對(duì)啊，圖里算出來的結(jié)果等于7啊，說好的2的冪呢？別忘了這里return最后在返回值進(jìn)行了+1。
那么問題來了。為什么要遵循“2的冪次方”的套路呢？不僅tableSizeFor如此，連一些參數(shù)初始值也暗含類似意圖（如DEFAULT_INITIAL_CAPACITY = 1 << 4）。
根本目的為了提高效率，為了使用借助以下規(guī)律：
取余(%)操作中如果除數(shù)是2的冪次方，則等同于與其除數(shù)減一的與(&)操作
因此在源碼中會(huì)看到大量的“(n - 1) & hash”語句，也就是為什么要按“2的冪次方”的套路出牌了。
resize
// hash table擴(kuò)容至原來2倍，并將原table數(shù)據(jù)重新映射到新table中
final Node[] resize() {
Node[] 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
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[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 清空原table
if (e.next == null) // 哈希表只有一個(gè)節(jié)點(diǎn)，直接賦值
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap); // 紅黑樹情況
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node 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起初使用鏈表法避免哈希沖突（相同hash值），當(dāng)鏈表長(zhǎng)度大于TREEIFY_THRESHOLD（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)換為紅黑樹，當(dāng)然小于UNTREEIFY_THRESHOLD（默認(rèn)為6）時(shí)，又會(huì)轉(zhuǎn)回鏈表以達(dá)到性能均衡。
根據(jù)“e.hash & oldCap”是否為零將原鏈表拆分成2個(gè)鏈表，一部分仍保留在原鏈表中不需要移動(dòng)，一部分移動(dòng)到“原索引+oldCap”的新鏈表中。
那么問題來了，“e.hash & oldCap”從何而來！？
因?yàn)閿U(kuò)容前后hash(key)不變，oldCap與newCap皆為“2的冪次方”，則++newCap-1的二進(jìn)制最高位與oldCap最高位相同++。結(jié)合上文“index=(n-1)&hash”可知：新的index的取決于：++(n-1)二進(jìn)制最高位上是0還是1++；因此源碼作者巧妙的拉關(guān)系，以“oldCap等價(jià)于newTab的(n-1)的最高位”推出“e.hash & oldCap”！
假設(shè)我們length從16resize到32（以下僅寫出8位，實(shí)際32位）,hash(key)是不變的。下面來計(jì)算一下index：
????n-1： 0000 1111-----》0001 1111【高位全0，&不影響】
hash1： 0000 0101-----》0000 0101
index1： 0000 0101-----》0000 0101【index不變】
hash2： 0001 0101-----》0001 0101
index2： 0000 0101-----》0001 0101【新index=5+16即原index+oldCap】
hash
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
異或運(yùn)算：(h = key.hashCode()) ^ (h >>> 16)原 來 的 hashCode : 1111 1111 1111 1111 0100 1100 0000 1010
移位后的hashCode: 0000 0000 0000 0000 1111 1111 1111 1111
進(jìn)行異或運(yùn)算 結(jié)果：1111 1111 1111 1111 1011 0011 1111 0101
這樣做的好處是，可以將hashcode高位和低位的值進(jìn)行混合做異或運(yùn)算，而且混合后，低位的信息中加入了高位的信息，這樣高位的信息被變相的保留了下來。摻雜的元素多了，那么生成的hash值的隨機(jī)性會(huì)增大。
putVal
參考文獻(xiàn)：
HashMap源碼注解 之 靜態(tài)工具方法hash()、tableSizeFor()（四）；201604
源碼分析之HashMap；201704
【集合詳解】HashMap源碼解析；201608
HashMap源碼分析（jdk1.8）;201604
更多有意思的內(nèi)容，歡迎訪問筆者小站： rebey.cn
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/70005.html
