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