java - 从 HashSet 中提取任意元素的性能(运行时)

Question

我在实现中使用 HashSets 来快速添加、删除和元素测试(摊销常数时间)。但是，我还想要一种从该集合中获取仲裁元素的方法。我知道的唯一方法是

Object arbitraryElement = set.iterator.next();

我的问题是 - 这有多快(渐近地讲)？这是否在集合大小的恒定时间内(未摊销)工作，或者 iterator().next() 方法是否执行一些较慢的操作？我问这个问题是因为正如实验所示，我似乎在实现中丢失了一个对数因子，这是受影响的少数几行之一。

非常感谢!

Answer 1

HashSet.iterator().next() 线性扫描表以查找下一个包含的项目。

对于 0.75 的默认负载系数，每个空槽位都会有 3 个满槽位。

当然，无法保证后备数组中对象的分布情况，并且该集合实际上永远不会那么满，因此扫描将花费更长的时间。

我认为你会得到固定时间摊销。

编辑:迭代器不会创建集合中任何内容的深拷贝。它仅引用HashSet中的数组。您的示例创建了一些对象，但仅此而已，并且没有大副本。