Java基础（9）jdk1.8对HashMap的优化-蒲公英云

Java基础（9）jdk1.8对HashMap的优化

た入场券 2024-05-06 23:23 122阅读 0赞

Java 8为HashMap带来了显著的性能优化，主要体现在以下几个方面：

引入红黑树： 当链表长度超过一定阈值（默认为8）时，链表会转换成红黑树，以减少查找时间。
优化哈希碰撞的处理： 通过结合高位和低位的哈希值，减少碰撞。
优化扩容操作： 在扩容时，元素的位置要么在原位置，要么在原位置加上旧容量的位置，这减少了重新计算哈希值的需求。

红黑树引入

在JDK 8之前，HashMap中解决哈希冲突的唯一方法是链表。但是，当哈希表变得非常大时，如果哈希函数不够好，或者数据分布不均匀，链表可能会变得很长，这会导致查找效率降低至O(n)。JDK 8引入了红黑树结构来优化这一点，当链表长度超过阈值时，链表会转换成红黑树，此时查找的时间复杂度能降低到O(log n)。

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

哈希值的优化

JDK 8对哈希值的计算方式也做了优化，通过将高位参与运算，减少碰撞。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

此处，hashCode()的高16位通过与低16位进行异或运算，加入了更多的随机性，减少了哈希碰撞。

扩容的优化

在JDK 8中，HashMap的扩容逻辑也得到了优化。扩容时，元素要么保持在原索引位置，要么移动到原索引位置加上旧容量的位置。这种方法避免了重新计算哈希值。

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