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

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

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

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

#### 红黑树引入 ####

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

这段代码显示，在扩容过程中，通过判断`(e.hash & oldCap) == 0`来决定元素是保留在原位置，还是移动到新的位置（原位置+旧容量）。这大大减少了扩容时的计算量。

这些优化显著提高了`HashMap`在不同场景下的性能，尤其是在处理大量数据时。通过使用红黑树减少查找时间，优化哈希值的计算以减少碰撞，以及提高扩容效率，JDK 8的`HashMap`成为了一个更加强大和高效的数据结构。