data-structures - 哈希表设计以在恒定时间内实现 nextElement()

Question

有人问我如何设计一个允许我在恒定时间内实现 nextElement() 的哈希表。

我的回答是，为了避免检查那些为空的桶，我们可以将添加到哈希中的元素添加到双链表中。

如果我们被要求遍历哈希表的元素，我们只需要从头到尾遍历列表。当从散列中删除一个元素时，从列表中删除也是在恒定时间内完成的。

当然，这需要额外的空间用于列表和指向下一个/上一个的指针。

这种方法可以吗？更好的选择？

谢谢你。

编辑： 我更改了标题以使其更准确

Answer 1

我不明白这个问题。
遍历所有元素当然是一种O(N)操作，不能在恒定时间内完成。
使用您的列表，您说您只是保存了一系列table[i]==null操作，这些操作并没有真正增加循环的任何开销。