algorithm - 如何在哈希表和Trie(前缀树)之间进行选择？

Question

因此，如果我必须在哈希表或前缀树之间做出选择，那么导致我选择一个而不是另一个的区别因素是什么。从我自己天真的观点来看，似乎使用 trie 有一些额外的开销，因为它没有存储为数组，但就运行时间而言(假设最长的键是最长的英文单词)它基本上可以是 O (1)(关于上限)。也许最长的英文单词是 50 个字符？

哈希表是即时查询一旦你得到索引。然而，散列 key 以获取索引似乎很容易需要将近 50 步。

有人可以提供我对此更有经验的观点吗？谢谢!

Answer 1

尝试的优点:

基础知识:

• 可预测的 O(k) 查找时间，其中 k 是键的大小
• 如果不存在，查找可能需要不到 k 时间
• 支持有序遍历
• 不需要哈希函数
• 删除很简单

新操作:

• 您可以快速查找键的前缀，枚举具有给定前缀的所有条目等。

链接结构的优点:

• 如果有很多公共(public)前缀，则共享它们所需的空间。
• 不可变尝试可以共享结构。您可以构建一个仅在一个分支上不同的新树，而不是就地更新树，而在其他地方指向旧树。这对于并发、表的多个同时版本等很有用。
• 不可变的 trie 是可压缩的。也就是说，它也可以通过散列运算在后缀 上共享结构。

哈希表的优点:

• 每个人都知道哈希表，对吧？您的系统将已经有一个很好的优化实现，比大多数目的的尝试更快。
• 您的 key 不需要任何特殊结构。
• 比明显的链接 trie 结构更节省空间(请参阅下面的评论)