自定义HashMap扩容测试超时问题求助

我从零实现了一个HashMap，在运行扩容测试时出现超时错误，测试用例插入100万条数据后10秒内无法完成。以下是我的核心实现代码、测试代码及错误栈，希望找到问题原因并解决。

核心实现代码 #

构造方法 #

public MyHashMap(int initialCapacity) {
    resizeFactor = 2;
    loadFactor = 0.75;
    bucketSize = initialCapacity;
    size = 0;
    buckets = createBucket();
    hashTable = createTable(bucketSize);
    for (int i = 0; i < bucketSize; i++) {
        hashTable[i] = buckets;
    }
}

put方法 #

public void put(K key, V value) {
    if (key == null) throw new IllegalArgumentException("first argument to put() is null");

    // Get hash code
    Integer hashCode = key.hashCode();
    // Compute index by modulo
    Integer index = Math.floorMod(hashCode, bucketSize);
    // Check if the item exists in the bucket
    for (Node node : hashTable[index]) {
        if (node.key.equals(key)) {
            node.value = value;
            return;
        }
    }
    hashTable[index].add(createNode(key, value));
    size += 1;

    if ( 1.0 * size/ bucketSize > loadFactor) {
        int newTableSize = bucketSize * resizeFactor;
        resize(newTableSize);
    }
}

resize方法 #

private void resize(int newTableSize) {
    MyHashMap hashMap = new MyHashMap(newTableSize);
        // Loop through each bucket(/index) in the current hash table
        for (int i = 0; i < bucketSize; i++) {
            // Loop through each item in current hash table's buckets
            for (Node node : hashTable[i]) {
                hashMap.put(node.key, node.value);
            }
        }
    this.size = hashMap.size;
    this.bucketSize = newTableSize;
    this.hashTable = hashMap.hashTable;
}

测试代码 #

public void testResize() {
    sanityResizeTest(new MyHashMap<>(), 16, 0.75);
    sanityResizeTest(new MyHashMap<>(32), 32, 0.75);
    sanityResizeTest(new MyHashMap<>(64, 0.5), 64, 0.5);
}

public static void sanityResizeTest(MyHashMap<String, Integer> m, int initialCapacity, double loadFactor) {
    // Times out after 10 seconds
    assertTimeoutPreemptively(Duration.ofSeconds(10), () -> {
        int backingArrayCapacity = sizeOfBackingArray(m);
        assertThat(backingArrayCapacity).isEqualTo(initialCapacity);
        for (int i = 0; i < 1000000; i++) {
            m.put("hi" + i, i);
            if (1.0 * i / backingArrayCapacity > loadFactor) {
                assertThat(sizeOfBackingArray(m)).isGreaterThan(backingArrayCapacity);
                backingArrayCapacity = sizeOfBackingArray(m);
            }
        }
    });
}

错误栈信息 #

org.opentest4j.AssertionFailedError: execution timed out after 10000 ms
    at org.junit.jupiter.api.AssertTimeout.assertTimeoutPreemptively(AssertTimeout.java:158)
    at org.junit.jupiter.api.AssertTimeout.assertTimeoutPreemptively(AssertTimeout.java:119)
    at org.junit.jupiter.api.AssertTimeout.assertTimeoutPreemptively(AssertTimeout.java:101)
    at org.junit.jupiter.api.AssertTimeout.assertTimeoutPreemptively(AssertTimeout.java:97)
    at org.junit.jupiter.api.Assertions.assertTimeoutPreemptively(Assertions.java:3398)
    at hashmap.TestMyHashMap.sanityResizeTest(TestMyHashMap.java:182)
    at hashmap.TestMyHashMap.testResize(TestMyHashMap.java:175)
    at java.base/jdk.internal.reflect.DirectMethodHandleAccessor.invoke(DirectMethodHandleAccessor.java:104)
    at java.base/java.lang.reflect.Method.invoke(Method.java:577)
    at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:59)
    at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
    at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:56)
    at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
    at org.junit.runners.ParentRunner$3.evaluate(ParentRunner.java:306)
    at org.junit.runners.BlockJUnit4ClassRunner$1.evaluate(BlockJUnit4ClassRunner.java:100)
    at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:366)
    at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:103)
    at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:63)
    at org.junit.runners.ParentRunner$4.run(ParentRunner.java:331)
    at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:79)
    at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:329)
    at org.junit.runners.ParentRunner.access$100(ParentRunner.java:66)
    at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:293)
    at org.junit.runners.ParentRunner$3.evaluate(ParentRunner.java:306)
    at org.junit.runners.ParentRunner.run(ParentRunner.java:413)
    at org.junit.runner.JUnitCore.run(JUnitCore.java:137)

问题原因分析 #

构造方法里存在致命逻辑错误：所有哈希表的bucket都指向同一个buckets实例。代码中hashTable[i] = buckets;这一行把同一个集合对象赋值给了哈希表的每个索引位置，导致所有插入的元素都存储在同一个集合里，完全失去了哈希表分桶的意义。

这会导致两个关键性能问题：

1. put方法时间复杂度退化：每次插入元素时，都要遍历整个集合（所有已插入元素）来检查是否存在重复key，时间复杂度从O(1)变成O(n)。
2. resize方法时间复杂度爆炸：扩容时需要遍历原哈希表的每个bucket，而每个bucket都是同一个集合，相当于重复遍历所有元素bucketSize次，时间复杂度直接变成O(n * bucketSize)，插入100万条数据时，这个操作会极其耗时，最终触发超时。

解决方案 #

修改构造方法，为哈希表的每个索引位置创建独立的bucket实例，而不是复用同一个对象：

public MyHashMap(int initialCapacity) {
    resizeFactor = 2;
    loadFactor = 0.75;
    bucketSize = initialCapacity;
    size = 0;
    hashTable = createTable(bucketSize);
    for (int i = 0; i < bucketSize; i++) {
        hashTable[i] = createBucket(); // 每个索引创建新的bucket
    }
}

这样每个bucket都是独立的集合，元素会均匀分布到不同的桶中，put和resize操作的时间复杂度会恢复到预期的O(1)（平均情况）和O(n)，百万级数据插入也能在规定时间内完成。

内容的提问来源于stack exchange，提问作者w97802