使用填充的 ArrayList 初始化哈希集的时间复杂度是多少?

Question

我在网上读到HashSet使用HashMap作为其底层数据结构。

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

以这种方式初始化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维护由基元数组构建的哈希表，并使用链表或树的混合策略来处理冲突。您可以通过检查 java.util.HashMap 的源代码来查看这一点。

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

Answer 2

您的List可以包含n数量的对象，这些对象可能是全部重复的，也可能都是唯一的或混合的。

HashSet集合的属性是它不包含重复的对象。

因此，遍历List并将每个对象添加到HashSet的时间复杂度将O(n)