三元树与哈希表

Question

我需要知道三元树是否比哈希表更好.

我在回答另一个问题时遇到了这个问题,有人说三元树通常比哈希表更快.我发现很难相信,所以我决定研究一下.

普林斯顿的这个网站似乎是信仰的源泉.我看了一下算法,它被描述为O(log n + k),其中n是存储的字数,k是密钥的长度.

在我看来,如果你经常搜索尚未存储的元素,那么唯一的方法就是更快.困扰我的另一件事是,trie的非连续爬行会导致你击中已被换掉的页面,但这是否是一个主要影响只能通过基准来看.

现在我知道两者都有利有弊,如果是的话,我想知道它们是什么.基准测试也很有帮助.

Answer 1

以下是我从Dr. Prince Dobbs文章中收集的内容,您可以从普林斯顿链接获得:

1. 在某些搜索问题上,三元搜索树比哈希表快10%.它们有时会变慢 - 主要取决于所使用的机器.
2. TRT是由计算机科学的两位最优秀的人才调整的自定义数据结构 - Jon Bentley和Robert Sedgewick都编写了优秀的 教科书,并完成了实际编程的一部分.哈希表被认为是普通的.
3. 正如Hao Wooi Lin所说,所涉及的常数非常重要.
4. 总的来说,这取决于您正在解决的问题.在许多编程语言中,更快的开发时间和几乎无处不在的哈希表支持通常比运行时间提高10%更重要.

Answer 2

这对我来说也很有趣。但从我读到的维基百科来看，它声称三叉树在大多数搜索问题上速度更快。这并不奇怪，因为即使哈希表具有 O(1) 查找，您仍然需要时间进行哈希处理。所以它并不是真正的 O(1)，而是更像 O(k)，其中 k 不依赖于 N（数据结构中的项数）。这可能给人的印象是哈希表更快。然而，如果您处理的是大型结构，k 会快速增加，并且哈希表的搜索速度会变得比三叉树慢。