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

StackOverflow https://stackoverflow.com/questions/245878

题

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

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

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

有帮助吗？

解决方案

尝试的优点：

基础知识：

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

新业务：

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

链式结构的优点：

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

哈希表的优点：

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

其他提示

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

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

在大多数甚至小延迟/可扩展性都很重要的工业场景中（例如：高频交易），创建用于高效查找的巨大哈希表并不是一种优雅的解决方案。您必须关心要在内存中占用的空间进行优化的数据结构，以减少缓存未命中。

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

使用树：

  1. 如果您需要自动完成功能
  2. 找到以'a'或'ax'开头的所有单词。
  3. 后缀树是树的特殊形式。后缀树有一大堆优点，哈希无法覆盖。
与基本 Trie 实施相比，

HashTable 实施具有空间效率。但是对于字符串，在大多数实际应用中都需要排序。但是HashTable完全扰乱了词法秩序。现在，如果您的应用程序正在执行基于词法顺序的操作（如部分搜索，具有给定前缀的所有字符串，所有按排序顺序排列的单词），则应使用Tries。对于仅查找，应该使用HashTable（可以说，它提供了最少的查找时间）。

P.S。：除此之外，三元搜索树（TST）将是一个很好的选择。它的查找时间不仅仅是HashTable，而且在所有其他操作中都具有时间效率。此外，它比尝试更节省空间。

有些东西我没有看到任何人明确提到我认为重要的是要记住。散列表和各种尝试通常都具有 O（k）操作，其中 k 是以位为单位的字符串的长度（或等效于字符）。

这假设你有一个很好的哈希函数。如果你不想要“农场”和“农场动物”为了散列到相同的值，则散列函数将必须使用密钥的所有位，因此散列“农场动物”。应该花费大约两倍于“农场”的时间。 （除非你处于某种滚动哈希方案中，但是有一些类似的操作保存方案也有尝试）。通过香草尝试，很清楚为什么要插入“农场动物”。将花费大约两倍于“农场”的时间。从长远来看，压缩尝试也是如此。

trie上的插入和查找与输入字符串O（s）的长度呈线性关系。

哈希将为您提供查找和插入的O（1），但首先您必须根据输入字符串计算哈希值，该字符串也是O（s）。

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

从数据的角度来看，trie有一些额外的开销，但你可以选择一个压缩的trie，它会或多或少地与你的哈希表联系起来。

打破领带问自己这个问题：我是否只需要查找完整的单词？或者我是否需要返回与前缀匹配的所有单词？ （如在预测文本输入系统中）。对于第一种情况，请寻找哈希值。它更简单，更清晰。更容易测试和维护。对于更加精心设计的前缀或后缀很重要的用例，请选择特里。

如果你这样做只是为了好玩，实施一个特里会使周日下午得到很好的利用。

某些（通常是嵌入式，实时）应用程序要求处理时间与数据无关。在这种情况下，哈希表可以保证已知的执行时间，而特里结构则根据数据而变化。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top