java - 哈希表实现 iterate 和 findMin

Question

我已经用 java 编写了一个标准的哈希表类。它有大量的桶，要插入、检索或删除元素，我只需计算元素的哈希值并查看数组中的适当索引以获得正确的桶。

但是，我想实现某种迭代器。除了遍历数组中的所有索引并忽略那些为空的索引之外，还有其他方法吗？因为我的哈希表可能包含数百个空条目，并且只有少数元素已被哈希和插入。当 n<<表的大小时，是否有 O(n) 的迭代方式而不是 O(表的大小)？

为了实现 findMin，我可以在每次插入新元素时简单地保存最小的元素，但我想使用迭代器方法。

谢谢!

Answer 1

您可以维护映射条目的链接列表，就像标准库中的 LinkedHashMap 一样。

或者您可以让您的哈希表确保容量始终最多为 kn，对于某个合适的 k 值。这将确保迭代在 n 中是线性的。