algorithm - Sets 和 hashmaps 没有固定的查找时间？

Question

我正在阅读有关尝试的文章，这篇 topcoder 文章 ( https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/) 说:

尝试可以在 O(L) 时间内插入和查找字符串(其中 L 表示单个单词的长度)。这比 set 快得多，但它比哈希表快一点吗。

我一直了解到集合和哈希表在查找内容方面非常快，而且它们的查找时间是恒定的。这不是真的吗？为什么它比集合“快得多”？而且它似乎也暗示哈希表的查找时间也与集合不同。我一直认为集合和哈希表的实现方式几乎相同，只是其中一个存储了一些对象。

Answer 1

引用的文章没有将 trie 与抽象的“集合”数据结构进行比较；它将 trie 与 C++ 标准库 std::set 进行比较，后者是搜索树，通常是红黑树，允许您按排序顺序迭代内容。 (C++ 也有 std::unordered_set，它是基于哈希表的，但这篇文章可能是在它成为标准库的一部分之前写的。)

仅当哈希可以在 O(1) 中计算时，哈希表(平均)为 O(1)，因为必须在完成任何查找之前计算键的哈希。对于字符串键，大多数哈希函数需要查看键中的每个字符，因此它们在字符串长度上是 O(L)。 (由于某种原因，这个相当明显的事实在讨论哈希表计算复杂性时经常被跳过。)由于 trie 和哈希表都必须最终验证提供的键是否等于容器中的候选键，所以有一个 O(L ) 两种情况下的因素。

但是，尝试还是有优势的。例如，它们可以按字典顺序迭代，如 std::set，但通常速度更快，而哈希表只能以某种不确定的顺序迭代。因此，如果您需要进行前缀搜索，哈希表不是合适的数据结构。