【java源码一带一路系列】之HashMap.putAll()

摘要：观光线路图将涉及到的源码全局变量哈希表初始化长度默认值是负载因子默认表示的填满程度。根据是否为零将原链表拆分成个链表，一部分仍保留在原链表中不需要移动，一部分移动到原索引的新链表中。

本文以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: 泛型通配符

好了，带全设备、干粮，准备出发~

public void putAll(Map m) {
    putMapEntries(m, true); // ↓
}

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);
        }
    }
}

// 找到大于等于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的幂次方”的套路出牌了。

// 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】

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值的随机性会增大。

HashMap源码注解 之 静态工具方法hash()、tableSizeFor()（四）；201604

源码分析之HashMap；201704

【集合详解】HashMap源码解析；201608

HashMap源码分析（jdk1.8）;201604

更多有意思的内容，欢迎访问笔者小站： rebey.cn