HashMap JDK8 优化

// 链表转红黑树
static final int TREEIFY_THRESHOLD = 8;
 
// 红黑树转链表
static final int UNTREEIFY_THRESHOLD = 6;
 
// 转红黑树的最小数组容量
static final int MIN_TREEIFY_CAPACITY = 64;

// 同时满足两个条件才转红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) {  // 链表长度 >= 8
    if (tab.length >= MIN_TREEIFY_CAPACITY)  // 数组容量 >= 64
        treeifyBin(tab, hash);
    else
        resize();  // 容量不够，先扩容
}

// JDK7 头插法
void transfer(Entry[] newTable) {
    for (Entry<K,V> e : table) {
        while (null != e) {
            Entry<K,V> next = e.next;
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];  // 头插
            newTable[i] = e;
            e = next;
        }
    }
}

// JDK8 尾插法
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

// 每个元素重新计算位置
int index = hash(key) % newCapacity;

// 扩容后元素位置：原位置 或 原位置 + 旧容量
if ((e.hash & oldCap) == 0) {
    // 位置不变
} else {
    // 位置 = 原位置 + 旧容量
}

// 示例：hash = 18 (10010)
// 旧数组：18 & 15 = 2 (位置 2)
// 新数组：18 & 31 = 18 (位置 18)
// 实际：2 + 16 = 18
 
// 示例：hash = 2 (00010)
// 旧数组：2 & 15 = 2 (位置 2)
// 新数组：2 & 31 = 2 (位置 2)
// 实际：位置不变

// 9次扰动
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

// 1次扰动：高16位异或低16位
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 1. 数组为空，初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 2. 计算位置，为空则直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        
        // 3. key 相同，直接覆盖
        if (p.hash == hash && 
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        
        // 4. 红黑树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        // 5. 链表节点
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 链表转红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 6. 找到相同 key，覆盖 value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            return oldValue;
        }
    }
    
    ++modCount;
    // 7. 检查是否需要扩容
    if (++size > threshold)
        resize();
    return null;
}