如果存在，查找的最佳数据结构是什么？

Question

我想保留一份我在递归循环中已经遇到的事情的列表，这样我就可以避免一遍又一遍地重新计算相同的事情。最有效的数据结构是什么？

从复杂性分析来看，哈希表似乎是查找效率最高的。但是，当我感兴趣的只是查找指定的键是否存在时，保存键值对的数据结构感觉效率低下。

我认为集合可能是个好主意，但它的复杂性似乎并不如此。

Answer 1

集合可能是正确的抽象数据类型，因为它编码的唯一信息实际上是项目是否在里面。

虽然使用集合并没有指定特定的实现。在大多数情况下，您应该能够找到使用散列或某种类型的树结构实现的集合类型。您选择哪一个取决于您插入的数据是否可以有效地散列或排序。

在某些库中，您会发现使用库的映射类型实现的集合类型，但其中的值被忽略了。例如在 Rust 中，标准库的 HashSet 类型是使用 HashMap 类型实现的。