如何在哈希表和Trie（前缀树）之间进行选择？
因此，如果我必须在哈希表或前缀树之间进行选择，那么有哪些区分因素会导致我选择一个而不是另一个。从我自己的幼稚角度来看，使用trie似乎有一些额外的开销，因为它没有存储为数组，但是就运行时间而言（假设最长的键是最长的英语单词），它实际上可以是O
（1）（相对于上限）。也许最长的英语单词是50个字符？
一旦获得索引， 哈希表将立即查找。但是，散列密钥以获取索引似乎很容易采取近50个步骤。
有人可以为此提供更丰富的见解吗？谢谢！
回答：
尝试的优势：
基础：
- 可预测的O（k）查找时间，其中k是密钥的大小
- 如果不存在，查找时间可能少于k次
- 支持有序遍历
- 无需哈希函数
- 删除很简单
新操作：
- 您可以快速查找键的前缀，枚举具有给定前缀的所有条目，等等。
链接结构的优点：
- 如果有许多公共前缀，则它们所需的空间将共享。
- 不变的尝试可以共享结构。您可以构建一个新的仅在一个分支上不同的分支，而在其他分支上指向旧的trie，而不是在适当位置更新一个trie。这对于并发，表的多个同时版本等很有用。
- 不变的特里是可压缩的。也就是说，它也可以通过哈希约束共享 后缀 上的结构。
哈希表的优点：
- 每个人都知道哈希表，对不对？您的系统已经有一个很好的优化实现，比大多数情况下要快。
- 您的密钥不需要任何特殊的结构。
- 比明显的链接特里结构更节省空间（ ）
以上是 如何在哈希表和Trie（前缀树）之间进行选择？ 的全部内容， 来源链接： utcz.com/qa/422060.html
