java - 使用填充的 ArrayList 初始化 HashSet 的时间复杂度是多少？

Question

我在网上看到 HashSet 使用 HashMap 作为它的底层数据结构。

而 HashMap 使用 ArrayList 作为其底层数据结构，列表中的每个项目都是 LinkedList 或 树的对象。

用这种方式初始化HashSet 的时间复杂度是多少？可以是O(1)吗？如果不是，为什么？

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(3);
list.add(2);
list.add(6);
list.add(0);
HashSet<Integer> set = new HashSet<>(list);

Answer 1

HashMap 不使用 ArrayList 作为其底层数据结构。

HashMap 维护一个由原始数组构建的哈希表，并使用链表或树的混合策略来处理冲突。您可以通过检查 source code for java.util.HashMap 来看到这一点.

因为要构建哈希表，您需要对每个条目调用哈希函数以确定哈希位置，最小界限为 O(N)。最坏的情况是病态分布的 key (例如，每个 key 都是冲突)，这比 O(N) 差很多。由于 Java 8 实现在最坏的情况下会降级为平衡树而不是链表，因此最坏情况下的运行时间将为 O(N log N)。 (在以前的 Java 版本中，使用线性探测，我相信最坏的情况是 O(N²))。