在自定义 HashMap 中调整大小 - 测试超时

Question

我正在从头开始实现 hashmap。 我有我的构造函数：

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

我的放置方法：

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

我的调整大小方法有一些问题，因为调整大小测试失败，我似乎不明白为什么

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

sizeOfBackingArray:
    /** Returns the length of the backing array of the given map.
     *  Be sure that you only use one instance variable to hold the buckets,
     *  otherwise this will not work properly.

我不明白的地方

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)

我不太确定为什么会超时，因为

put

和

resize

方法对我来说看起来不错。 任何帮助将不胜感激。

Answer 1

所以你的测试是这样做的：

for (int i = 0; i < 1000000; i++) {
    m.put("hi" + i, i);

这意味着在 10000 毫秒内，您需要进行 100 万次迭代，这意味着每次迭代可用 0.01 毫秒，即您需要每毫秒处理该循环 100 次迭代。

是不是很惊讶它可能会超时？请记住，在此期间也可能会花费一些时间进行垃圾收集。

虽然可能真正的原因是：
您的

put

调用

resize

，后者创建一个新的 MyHashMap，然后使用

put

，然后它可以调用

resize

并可能进入循环。

附注
我注意到，在您的

put

方法中，您似乎不必要地使用

Integer

而不是

int

，这会增加少量的开销，对值进行装箱和拆箱。