logo标签列表

我该如何在哈希表和Trie（前缀树）之间选择？（关于IT技术）

algorithmdata-structureshashtabletrie
165
如果我必须选择哈希表或前缀树，那么会有哪些区别因素会让我选择其中之一呢？从我的幼稚观点来看，使用 Trie 存储并不像数组那样高效，但就运行时间而言（假设最长的键是最长的英文单词），它基本上可以是 O(1)（相对于上限）。也许最长的英文单词是50个字符？
哈希表是瞬间查找一旦您获取索引。然而，通过哈希键来获取索引似乎可能需要近50个步骤。
能否有经验丰富的人提供更多角度的观点？谢谢！
2
值得注意的是，Radix树比普通Trie更高效，因为您不需要为每个字符串字节创建新分支。此外，Radix树比哈希表更好地支持“模糊”搜索，因为在沿着路径向下工作时，您正在查看单个位。例如，00110010可能是输入字节，但您要包含相差仅一位的匹配项00111010。 - Xeoncross
8个回答
141

Trie的优点：

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

新操作：

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

链接结构的优点：

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

哈希表的优点：

  • 每个人都知道哈希表，对吧？您的系统已经有一个不错的、经过优化的实现，对大多数用途而言比Trie更快。
  • 您的键不需要任何特殊结构。
  • 比明显的链接Trie结构更节省空间（请参见下面的评论）。
32
对于“比明显的链式字典树结构更节省空间”这句话，我并不能完全同意。在一般的散列表实现中，为了保持键值，需要占用更多的空间，而在字典树中，每个节点代表一个单词。从这个意义上讲，字典树更加节省空间。 - galactica
1
如何从一个结构访问数据，而不是另一个结构？我在考虑缓存和位置。 - Horia Toma
14
@ galactica，这与我的经验相矛盾：例如，在此答案中，我测量了所有结构的空间，但 trie 的表现最差。这很有道理，因为一个指针比一个字节大得多。是的，共享前缀有所帮助，但它必须克服很多开销才能达到平衡。更省空间的表示方法可以很大程度上帮助，但这时我们就不再谈论显然的链式结构了。 - Darius Bacon
1
@DariusBacon，处理电话号码计划似乎是Tries的一个合理场景。示例场景：电话号码与运营商匹配，包括从一个运营商转移到另一个运营商的号码。对于通常的字典，这可能取决于语言（普通话 vs 英语），您需要n-gram和/或其他统计数据。对于韵书，后缀树也似乎是一个不错的选择。 - mbx
数据的多样性非常重要。如果您的数据值中有大量唯一值，由于使用了额外的空指针，您的空间复杂度将会比哈希表增加。 - Union find
显示剩余2条评论
50

这完全取决于你要解决的问题。如果你只需要进行插入和查找操作，那么使用哈希表可能是更好的选择。如果你需要解决更复杂的问题，比如前缀相关的查询，那么使用trie树可能是更好的解决方案。

11
如果哈希表和字典树在查询时具有相同的复杂度，对于长度为k的字符串O(k)，那么为什么我们应该选择哈希表呢？你能解释一下吗？ - Sazzad Hissain Khan
2
在我看来，哈希表对字符串输入进行_计算_，而字典树则对字符串输入进行_地址查找_。地址查找可能会错过缓存，而计算速度更快，因为它们不会命中缓存。这是我的理解哈哈。 - Lance
36
大家都知道哈希表及其用途，但它并不完全具有恒定的查找时间；它取决于哈希表的大小以及哈希函数的计算复杂度。
在大多数工业场景中，为了实现高效的查找，创建庞大的哈希表并不是一个优雅的解决方案，即使是微小的延迟/可扩展性也很重要（例如：高频交易）。您必须关注数据结构，以优化其在内存中占用的空间，以减少缓存未命中。
一个非常好的例子是消息中间件，其中前缀树更适合需求：您有一百万个订阅者和发布者，发布各种类别的消息（在JMS术语中-主题或交换），在这种情况下，如果您想根据主题（实际上是字符串）过滤消息，绝对不希望为百万个订阅与数百万个主题创建哈希表。更好的方法是将主题存储在前缀树中，因此当基于主题匹配进行过滤时，其复杂度与主题/订阅/发布者的数量无关（仅取决于字符串的长度）。我喜欢它，因为您可以在这种数据结构上发挥创造力，以优化空间需求，从而减少缓存未命中。
14

使用树：

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

有一些重要的事情，我认为需要明确指出，这是与哈希表和各种尝试相关的。它们通常具有O(k)操作，其中k是以位（或等效字符）为单位的字符串长度。

这是假设您拥有一个良好的哈希函数。如果您不希望“农场”和“农场动物”散列到相同的值，则哈希函数将必须使用密钥的所有位，因此散列“农场动物”应该比“农场”慢大约两倍（除非您处于某种滚动哈希方案中，但是在尝试中也有类似的操作节省方案）。对于普通尝试，很明显插入“农场动物”将需要大约两倍的时间，就像只有“农场”一样。长期来看，压缩尝试也是如此。

6

在trie上进行插入和查找的时间复杂度与输入字符串的长度成正比，为O(s)。

哈希表可以实现O(1)的插入和查找，但首先要根据输入字符串计算哈希值，这也是O(s)的。

总之，两种情况的渐近时间复杂度都是线性的。

从数据角度来看，trie有一些额外的开销，但您可以选择压缩trie，这将使您再次与哈希表处于相同的水平。

要解决这个问题，请问自己一个问题：我只需要查找完整单词吗？还是我需要返回所有匹配前缀的单词（如预测文本输入系统）？对于第一种情况，请使用哈希表。它具有更简单和更清晰的代码。易于测试和维护。对于更复杂的用例，前缀或后缀很重要，请使用Trie。

如果您只是为了好玩而这样做，请实现Trie，这将使星期天下午得到很好的利用。

一个哈希表可以在查找和插入时给你O(1)的时间复杂度，但首先你需要基于输入字符串计算哈希值，这又是O(s)的时间复杂度。感谢您的解释！ - abadawi
计算哈希函数的时间复杂度不是O(s)，实际上是O(1)。你不需要所有字符串的位来计算它，只需要其中一些（固定数量的）就足够了。 - Nicola Amadio
2
实现HashTable比基本的Trie实现更节省空间。但是对于字符串，大多数实际应用程序都需要排序。但是HashTable完全破坏了词典顺序。如果您的应用程序基于字典顺序执行操作（例如部分搜索、具有给定前缀的所有字符串、按排序顺序列出所有单词），则应使用Tries。仅进行查找时，应使用HashTable（因为可以说它提供了最小的查找时间）。
P.S.：除此之外，Ternary Search Trees (TSTs)也是一个很好的选择。它的查找时间比HashTable长，但在所有其他操作中都是高效的。而且它比Tries更节省空间。
-3

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

6
大多数哈希表并不保证具有已知的执行时间 - 最坏情况为O(n)，如果每个元素都发生碰撞并被链接起来。 - Adam Rosenfield
2
对于任何数据集，您都可以计算出一个完美的哈希函数，以保证该数据的O(1)查找。当然，计算完美哈希并非免费。 - George V. Reilly
5
此外，链式哈希并不是处理冲突的唯一方法；有各种有趣而巧妙的方式可以处理冲突——比如布谷鸟哈希（Cuckoo Hashing）（http://en.wikipedia.org/wiki/Cuckoo_hashing），而最佳选择取决于客户端代码的需求。 - Hank Gay
不知道关于布谷鸟哈希和它与布隆过滤器的关系，这将是一篇有趣的阅读，谢谢！ - Horia Toma
不要忘记Robin-hood Hashing，它在缓存和方差方面更为优越。http://sebastiansylvan.com/2013/05/08/robin-hood-hashing-should-be-your-default-hash-table-implementation/ http://codecapsule.com/2013/11/11/robin-hood-hashing/ - Jarred Nicholls
这似乎完全是相反的，Tries对于渐近性有比字典更强的保证，对于任何操作，tries的绝对最坏情况是O(k)（其中k是键大小），而不完美的哈希算法或真正的坏运气可能会打破字典的限制。 - semicolon
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接