java - 在Java中，调用set.iterator()，这个方法的内部流程是怎样的？

Question

我刚刚注意到 Method Set.iterator() 的时间复杂度是恒定的。

如果是这样，说明java生成集合并向其中添加元素时，该元素已经和光标连接起来了。否则，当调用Set.iterator()时，它必须迭代该集合中的所有元素，这会花费线性时间复杂度。

所以我想知道Java中集合是如何保存元素的，以及调用Set.iterator()时，集合如何返回迭代器？

谢谢!

Answer 1

Java 中有不同类型的集合。主要的两个可用的是 HashSet 和 TreeSet。两者都使用映射来实现:HashMap 和 TreeMap。因此，当您添加一个项目时，它会通过进行映射查找来检查该项目是否已经存在，这对于 HashMap 来说接近恒定时间，对于 TreeMap 来说是日志时间。

添加到集合中不是常数时间，这取决于后台映射，但一般 HashMap 接近常数时间，TreeMap 是日志时间。

为了返回迭代器，集合使用映射的键迭代器。背景映射使用集合元素作为键。迭代 HashMap 的键相当简单，您只需遍历数组和每个元素的 bin 即可。可以使用各种已知的遍历算法来迭代二叉树。