HashSet 代码意外运行次

Question

所以最初，我有这个代码：

import java.util.*;

public class sandbox {
    public static void main(String[] args) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < 100_000; i++) {
            hashSet.add(i);
        }

        long start = System.currentTimeMillis();

        for (int i = 0; i < 100_000; i++) {
            for (Integer val : hashSet) {
                if (val != -1) break;
            }

            hashSet.remove(i);
        }

        System.out.println("time: " + (System.currentTimeMillis() - start));
    }
}

在我的计算机上运行嵌套 for 循环大约需要 4 秒，我不明白为什么要花这么长时间。外部循环运行s 100,000 次，内部 for 循环应该运行 1 次（因为 hashSet 的任何值永远不会是 -1）并且从 HashSet 中删除一个项目是 O(1) ，因此应该有大约 200,000 次操作。如果一秒钟通常有 100,000,000 次操作，为什么我的代码需要 4 秒才能运行？

此外，如果注释掉hashSet.remove(i);行，代码只需要16ms。如果内部for循环被注释掉（但不是hashSet.remove(i);），代码只需要8ms。

Answer 1

您创建了一个 HashSet 的边际用例，其中算法降级为二次复杂度。

这是耗时很长的简化循环：

for (int i = 0; i < 100_000; i++) {
    hashSet.iterator().next();
    hashSet.remove(i);
}

async-profiler shows that almost all time is spent inside java.util.HashMap$HashIterator()构造函数：

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
--->        do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

突出显示的行是一个线性循环，用于搜索散列中的第一个非空桶 table。

由于 Integer 具有简单的 hashCode（即 hashCode 等于数字本身），结果表明连续整数主要占据哈希 table 中的连续桶：数字 0 进入第一个桶，数字 1 进入第二个桶，依此类推

现在您删除从 0 到 99999 的连续数字。在最简单的情况下（当存储桶包含单个键时），删除一个键是通过清空存储桶数组中的相应元素来实现的。请注意，table 在删除后不会被压缩或重新散列。

因此，从桶数组的开头删除的键越多，HashIterator 找到第一个非空桶所需的时间就越长。

尝试从另一端移除密钥：

hashSet.remove(100_000 - i);

算法将变得更快！

HashSet 代码意外运行次

Unexpected running times for HashSet code

java

performance

for-loop

hashset

HashSet 代码意外 运行 次

Unexpected running times for HashSet code

java

performance

for-loop

hashset

HashSet 代码意外运行次