深入剖析 Java HashMap：扩容机制与链表转红黑树

引言

在 Java 的数据结构中，HashMap 是一个使用频率极高的哈希表实现。它提供了快速的插入、查找和删除操作，但其内部的实现机制却并不简单。其中，扩容机制和链表转红黑树的特性对于理解 HashMap 的性能和应用场景至关重要。本文将深入探讨 HashMap 的这两个关键特性，并介绍红黑树的相关知识。

一、HashMap 扩容机制

1.1 关键参数

• initialCapacity：HashMap 数组的初始大小，默认值为 16。它决定了 HashMap 初始时能容纳的元素数量。
• loadFactor：负载因子，默认值是 0.75。它控制着 HashMap 在元素数量达到多少比例时进行扩容。
• threshold：阈值，计算方式为 threshold = initialCapacity * loadFactor。当 HashMap 中存储的元素数量超过该值时，会触发扩容操作。

1.2 扩容过程

• 判断扩容条件：每次向 HashMap 插入元素时，会检查当前元素数量是否超过阈值 threshold，若超过则触发扩容。
• 创建新数组：扩容时，会创建一个大小为原数组两倍的新数组。
• 重新哈希元素：将原数组中的所有元素重新计算哈希值，并插入到新数组中。

1.3 示例代码及解释

import java.util.HashMap;

public class HashMapResizeExample {
    public static void main(String[] args) {
        // 创建一个初始容量为 4，负载因子为 0.75 的 HashMap
        HashMap<Integer, String> hashMap = new HashMap<>(4, 0.75f);

        // 打印初始容量和阈值
        System.out.println("Initial capacity: " + getCapacity(hashMap));
        System.out.println("Initial threshold: " + getThreshold(hashMap));

        // 插入元素
        for (int i = 0; i < 4; i++) {
            hashMap.put(i, "Value " + i);
            System.out.println("After inserting key " + i + ":");
            System.out.println("  Size: " + hashMap.size());
            System.out.println("  Capacity: " + getCapacity(hashMap));
            System.out.println("  Threshold: " + getThreshold(hashMap));
        }
    }

    // 通过反射获取 HashMap 的容量
    private static int getCapacity(HashMap<?, ?> hashMap) {
        try {
            java.lang.reflect.Field field = HashMap.class.getDeclaredField("table");
            field.setAccessible(true);
            Object[] table = (Object[]) field.get(hashMap);
            return table != null ? table.length : 0;
        } catch (Exception e) {
            e.printStackTrace();
            return -1;
        }
    }

    // 通过反射获取 HashMap 的阈值
    private static int getThreshold(HashMap<?, ?> hashMap) {
        try {
            java.lang.reflect.Field field = HashMap.class.getDeclaredField("threshold");
            field.setAccessible(true);
            return (int) field.get(hashMap);
        } catch (Exception e) {
            e.printStackTrace();
            return -1;
        }
    }
}

在这个示例中，初始容量为 4，负载因子为 0.75，所以初始阈值为 4 * 0.75 = 3。插入元素时，当元素数量达到 4 超过阈值，HashMap 会进行扩容，新数组容量变为 8，新阈值为 8 * 0.75 = 6。

二、HashMap 链表转红黑树

2.1 相关参数

• TREEIFY_THRESHOLD：链表转红黑树的阈值，默认值为 8。当链表长度达到 8 时，会尝试将链表转化为红黑树。
• MIN_TREEIFY_CAPACITY：最小树形化容量阈值，默认值为 64。在将链表转化为红黑树之前，会检查 HashMap 的容量是否达到 64，如果未达到，则优先进行扩容操作。
• UNTREEIFY_THRESHOLD：红黑树转链表的阈值，默认值为 6。当红黑树中的节点数量减少到 6 时，红黑树会转化为链表。

2.2 转化过程

当向 HashMap 插入元素，某个桶中的链表长度达到 TREEIFY_THRESHOLD（8）时：

• 若数组容量未达到 64，HashMap 会进行扩容操作。
• 若数组容量达到 64，HashMap 会将该链表转化为红黑树。

2.3 示例代码及解释

import java.lang.reflect.Field;
import java.util.HashMap;
import java.util.Map;

public class HashMapTreeifyExample {
    public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
        // 创建一个初始容量为 4，负载因子为 0.75 的 HashMap
        HashMap<Integer, String> hashMap = new HashMap<>(4, 0.75f);

        // 插入元素，让某个链表长度达到 8
        for (int i = 0; i < 10; i++) {
            // 这里通过自定义的哈希函数，让元素都落到同一个桶中
            int key = customHash(i);
            hashMap.put(key, "Value " + i);

            System.out.println("After inserting key " + key + ":");
            System.out.println("  Size: " + hashMap.size());
            System.out.println("  Capacity: " + getCapacity(hashMap));
            System.out.println("  Is tree node: " + isTreeNode(hashMap, key));
        }
    }

    // 自定义哈希函数，让元素都落到同一个桶中
    private static int customHash(int key) {
        return 0;
    }

    // 通过反射获取 HashMap 的容量
    private static int getCapacity(HashMap<?, ?> hashMap) throws NoSuchFieldException, IllegalAccessException {
        Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);
        Object[] table = (Object[]) tableField.get(hashMap);
        return table != null ? table.length : 0;
    }

    // 判断指定桶中的节点是否为树节点
    private static boolean isTreeNode(HashMap<?, ?> hashMap, int key) throws NoSuchFieldException, IllegalAccessException {
        Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);
        Object[] table = (Object[]) tableField.get(hashMap);
        int index = (table.length - 1) & key;
        Object node = table[index];
        if (node != null) {
            Class<?> nodeClass = node.getClass();
            return nodeClass.getName().endsWith("TreeNode");
        }
        return false;
    }
}

通过自定义哈希函数让所有元素落到同一个桶中，模拟链表长度增加的情况。当链表长度达到 8 且数组容量达到 64 时，链表会转化为红黑树，Is tree node 会从 false 变为 true。

三、红黑树简介

3.1 定义与特性

红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色（红色或黑色）。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。红黑树具有以下特性：

• 每个节点要么是红色，要么是黑色。
• 根节点是黑色。
• 每个叶子节点（NIL 节点，空节点）是黑色的。
• 如果一个节点是红色的，则它的两个子节点都是黑色的。
• 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

3.2 优势

红黑树的主要优势在于其插入、删除和查找操作的时间复杂度都是O(logn)，这使得它在处理大量数据时具有较高的效率。在 HashMap 中，当链表长度过长时，将链表转化为红黑树可以显著提高查找效率，避免了链表查找的O(n)时间复杂度。

四、总结

HashMap 的扩容机制和链表转红黑树特性是为了在不同的数据规模下保持高效的性能。扩容机制可以在元素数量增加时，通过扩大数组容量来减少哈希冲突；链表转红黑树则在链表过长时，将查找时间复杂度O(n)从 降低到O(logn)