HashSet iterator() 是线性的而不是恒定的复杂度？

Question

我发现 HashSet 的 iterator() 花费了太多时间。这是一些证明观察结果的代码示例：

import java.text.SimpleDateFormat;
import java.util.*;
import java.util.stream.IntStream;

public class Main {

    public static final int LENGTH = 100000;

    public static void calculate() {
        Set<Integer> set = new HashSet<>();
        int part1 = 0;
        int part2 = 0;

        for (int i = 0; i < LENGTH; i++) {
            set.add(i);
        }

        for (int i = 0; i < LENGTH; i++) {
            long cur1 = System.currentTimeMillis();

            Iterator<Integer> it = set.iterator();

            long cur2 = System.currentTimeMillis();
            part1 += cur2 - cur1;

            int elem = it.next();
            set.remove(elem);

            long cur3 = System.currentTimeMillis();
            part2 += cur3 - cur2;
        }

        System.out.println("Total milliseconds to execute iterator() code: " + part1);
        System.out.println("Total milliseconds to execute remove() code: " + part2);
    }

    public static void main(String[] args) {
        System.out.println(new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date()));
        calculate();
        System.out.println(new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date()));
    }
}

运行结果为：

2023-08-28 14:05:51.080
Total milliseconds to execute iterator() code: 9477
Total milliseconds to execute remove() code: 18
2023-08-28 14:06:00.595

我检查了 iterator() 的文档和实现，只看到它应该是一个常数时间，但似乎并非如此。

有人知道为什么需要这么长时间吗？

Answer 1

您误读了文档，其中 说（例如，在版本 8 中）：

此类为基本操作提供恒定时间性能 （添加、删除、包含和大小），假设散列函数分散 将元素正确地放置在桶中。

换句话说，在集合中添加或删除一个元素，或者评估一个元素是否在集合中，或者检查集合的大小所花费的时间是恒定的。与您在代码中使用

set.iterator()

所做的那样构造迭代器（如果您想一次遍历每个元素），您会这样做，这是不同的事情；这就像将制造一辆自行车所需的时间与骑它一英里所需的时间进行比较。