155

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

一旦获得索引,哈希表就会立即查找。然而,散列密钥以获取索引似乎可以轻松完成近 50 个步骤。

有人可以为我提供一个更有经验的观点吗?谢谢!

4

8 回答 8

134

尝试的优点:

基础:

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

新操作:

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

链接结构的优点:

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

哈希表的优点:

  • 每个人都知道哈希表,对吧?你的系统已经有了一个很好的优化实现,比大多数目的的尝试都要快。
  • 您的密钥不需要有任何特殊结构。
  • 比明显的链接特里结构更节省空间(见下面的评论
于 2008-10-29T06:38:06.697 回答
50

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

于 2008-10-29T05:25:20.137 回答
33

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

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

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

于 2012-04-15T05:57:34.530 回答
14

使用树:

  1. 如果您需要自动完成功能
  2. 查找所有以“a”或“axe”开头的单词,依此类推。
  3. 后缀树是树的一种特殊形式。后缀树有一系列哈希无法涵盖的优点。
于 2012-01-12T10:27:47.747 回答
5

我没有看到任何人明确提到过一些我认为很重要的事情要牢记在心。哈希表和各种尝试通常都有O(k)操作,其中k是字符串的长度,以位为单位(或等效地以字符为单位)。

这是假设你有一个好的散列函数。如果您不希望“农场”和“农场动物”散列到相同的值,那么散列函数将不得不使用密钥的所有位,因此散列“农场动物”大约需要两倍的时间“农场”(除非您处于某种滚动散列场景中,但也有一些类似的操作保存场景与尝试)。有了香草树,就很清楚为什么插入“农场动物”所需的时间大约是“农场”的两倍。从长远来看,压缩尝试也是如此。

于 2014-10-16T12:40:26.170 回答
5

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

哈希将为您提供查找和插入的 O(1),但首先您必须根据再次为 O(s) 的输入字符串计算哈希。

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

从数据的角度来看,trie 有更多的开销,但您可以选择一个压缩的 trie,它会让您再次或多或少地与哈希表平起平坐。

要打破平局,请问自己这个问题:我只需要查找完整的单词吗?还是我需要返回与前缀匹配的所有单词?(如在预测文本输入系统中)。对于第一种情况,请使用哈希。它是更简单、更干净的代码。更容易测试和维护。对于前缀或后缀很重要的更详细的用例,请尝试一下。

And if you do it just for fun, implementing a trie would put a Sunday afternoon to a good use.

于 2017-11-19T17:16:23.157 回答
2

与基本的Trie实现相比,HashTable实现更节省空间。但是对于字符串,在大多数实际应用中都需要排序。但是 HashTable 完全打乱了字典顺序。现在,如果您的应用程序正在执行基于字典顺序的操作(如部分搜索、所有具有给定前缀的字符串、所有单词按排序顺序),您应该使用 Tries。对于仅查找,应使用 HashTable(可以说,它提供了最短的查找时间)。

PS:除此之外,三元搜索树(TST)将是一个很好的选择。它的查找时间比 HashTable 长,但在所有其他操作中都具有时间效率。此外,它比尝试更节省空间。

于 2017-06-18T16:05:39.103 回答
-2

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

于 2008-10-29T05:31:49.810 回答