algorithm - 三叉树与哈希表

Question

我需要知道 ternary tree比 hash table 好.

我在回复 another question I had 时遇到了这个问题有人说三元树通常比哈希表快。我发现这很难相信，所以我决定稍微研究一下。

This one website from Princeton似乎是信仰的来源。我看了一下被描述为 O(log n + k) 的算法，其中 n 是存储的单词数，k 是 key 的长度。

在我看来，如果您经常搜索尚未存储的元素，唯一可能更快的方法是。另一件困扰我的事情是，不连续抓取 trie 会导致您访问已被换出的页面，但这是否是主要影响只能通过基准测试才能看出。

现在我知道它们可能各有利弊，如果有的话，我想知道它们是什么。基准测试也很有帮助。

Answer 1

这是我从 Dr. Dobbs Article 收集到的信息可从您提供的普林斯顿链接访问:

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