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

Question

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

获得索引后,哈希表会立即查找.然而,散列获得索引的关键似乎很容易接近50步.

有人能为我提供更有经验的观点吗？谢谢!

Answer 1

尝试的优点:

基础:

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

新业务:

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

链接结构的优点:

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

哈希表的优点:

• 每个人都知道哈希表,对吗？您的系统已经有一个很好的优化实现,比大多数目的尝试更快.
• 您的钥匙不需要任何特殊结构.
• 比明显的链接结构更节省空间(见下面的评论)

Answer 2

这一切都取决于你想要解决的问题.如果您只需要插入和查找,请使用哈希表.如果您需要解决更复杂的问题,例如与前缀相关的查询,那么trie可能是更好的解决方案.

Answer 3

每个人都知道哈希表及其用途,但它不是完全恒定的查找时间,它取决于哈希表的大小,哈希函数的计算复杂性.

在大多数工业场景中创建大量哈希表以实现高效查找并不是一个优雅的解决方案,即使很小的延迟/可扩展性也很重要(例如:高频交易).您必须关心要在内存中占用的空间进行优化的数据结构,以减少缓存未命中.

一个非常好的例子,其中trie更符合要求的是消息传递中间件.您有一百万订阅者和各种类别的消息发布者(以JMS术语 - 主题或交换),在这种情况下,如果您想根据主题(实际上是字符串)过滤掉消息,您绝对不希望创建哈希表百万主题的百万订阅.更好的方法是将主题存储在trie中,因此当基于主题匹配进行过滤时,其复杂性与主题/订阅/发布者的数量无关(仅取决于字符串的长度).我喜欢它,因为您可以通过这种数据结构创造性地优化空间要求,从而降低缓存未命中率.

Answer 4

使用树:

1. 如果您需要自动完成功能
2. 查找以'a'或'ax'开头的所有单词.
3. 后缀树是树的特殊形式.后缀树具有哈希无法涵盖的一系列优点.

Answer 5

trie 上的插入和查找与输入字符串 O(s) 的长度成线性关系。

哈希将为您提供 O(1) 的查找和插入时间，但首先您必须根据输入字符串计算哈希，这也是 O(s)。

结论是，两种情况下的渐近时间复杂度都是线性的。

从数据角度来看，特里结构有一些更多的开销，但是您可以选择压缩特里结构，这将再次或多或少地与哈希表打成平手。

要打破平局，请问自己这个问题：我是否只需要查找完整的单词？或者我是否需要返回与前缀匹配的所有单词？（如在预测文本输入系统中）。对于第一种情况，请进行哈希处理。它的代码更简单、更清晰。更容易测试和维护。对于前缀或后缀很重要的更详细的用例，请使用 trie。

如果你这样做只是为了好玩，那么实现一个 trie 会让周日下午得到很好的利用。

Answer 6

有些事情我没有看到任何人明确提到，我认为要记住这一点很重要。哈希表和各种类型的尝试通常都有O(k)操作，其中k是以位为单位的字符串长度（或等效的以字符为单位）。

这是假设你有一个很好的散列函数。如果您不希望“农场”和“农场动物”散列到相同的值，那么散列函数将不得不使用密钥的所有位，因此散列“农场动物”应该花费大约两倍的时间“农场”（除非您处于某种滚动哈希场景中，但也有一些类似的尝试节省操作的场景）。使用香草树，很明显为什么插入“农场动物”所需的时间大约是“农场”的两倍。从长远来看，压缩尝试也是如此。