哈希表和Trie（前缀树）如何选择？

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

哈希表是即时查找的一旦你得到索引。然而，对密钥进行哈希处理来获取索引似乎很容易需要近 50 个步骤。

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

尝试的优点：

基础知识：

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

新业务：

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

链式结构的优点：

• 如果有许多公共前缀，则它们所需的空间是共享的。
• 不可变尝试可以共享结构。您可以构建一个仅在一个分支上不同的新特里树，而在其他地方指向旧特里树，而不是就地更新特里树。这对于并发、表的多个同时版本等非常有用。
• 不可变的 trie 是可压缩的。也就是说，它可以共享结构suffixes也可以通过哈希consing。

哈希表的优点：

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