哈希 Table 实现迭代和 findMin

Question

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

但是，我想实现某种迭代器。除了遍历数组中的所有索引并忽略那些为空的索引之外，还有其他方法吗？因为我的散列 table 可能包含数百个空条目，并且只有少数元素已被散列和插入。当 n<

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

谢谢！

您可以存储非空桶的排序列表，并在向散列中插入内容时将桶的 ID 插入列表（如果它不存在）table。

但是，如果没有在循环中埋得太深，搜索几百个空桶的成本可能不会太高。有点低效可能比更复杂的设计更好。

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

或者你可以让你的散列table确保容量总是最多kn，对于k的一些suitable值。这将确保迭代在 n.

中是线性的

如果顺序对您很重要，您应该考虑使用二叉搜索树（例如左倾红黑树）或跳跃列表来实现您的词典。在这些情况下，他们更适合这份工作。

©2023 WhoseBug

Answer 1

您可以存储非空桶的排序列表，并在向散列中插入内容时将桶的 ID 插入列表（如果它不存在）table。

但是，如果没有在循环中埋得太深，搜索几百个空桶的成本可能不会太高。有点低效可能比更复杂的设计更好。

Answer 2

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

或者你可以让你的散列table确保容量总是最多kn，对于k的一些suitable值。这将确保迭代在 n.

中是线性的

Answer 3

如果顺序对您很重要，您应该考虑使用二叉搜索树（例如左倾红黑树）或跳跃列表来实现您的词典。在这些情况下，他们更适合这份工作。