如何在哈希表和Trie(前缀树)之间进行select?

所以如果我不得不在哈希表或前缀树之间进行select,那么导致我select哪一个的区别因素是什么。 从我自己的天真的angular度来看,似乎使用一个特里特有一些额外的开销,因为它不存储为一个数组,但就运行时间而言(假设最长的键是最长的英文单词),它可以基本上是O (1)(相对于上限)。 也许最长的英文单词是50个字符?

一旦获得索引,哈希表就会立即查找。 散列键获得索引,但似乎可以轻松地采取近50个步骤。

有人能给我提供一个更有经验的观点吗? 谢谢!

尝试的优点:

基础:

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

新业务:

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

链接结构的优点:

  • 如果有许多共同的前缀,他们需要的空间是共享的。
  • 不变的尝试可以共享结构。 而不是更新一个trie,你可以build立一个新的不同,只有一个分支,其他地方指向旧的trie。 这对于并发性,表的多个同时版本等是有用的。
  • 一个不可改变的trie是可压缩的。 也就是说,它也可以通过散列来共享后缀上的结构。

哈希表的优点:

  • 大家都知道哈希表,对吗? 你的系统已经有了很好的优化实现,比大多数目的的尝试更快。
  • 你的钥匙不需要任何特殊的结构。
  • 比显而易见的链接结构更具空间效率( 见下面的注释

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

每个人都知道散列表及其使用,但是它不是完全一致的查找时间,它取决于散列表有多大,散列函数的计算复杂度。

在大多数即使很小的延迟/可扩展性(例如高频交易)很重要的工业场景中,创build大型哈希表以进行高效查找也不是一个很好的解决scheme。 您必须关心数据结构,以优化它在内存占用的空间,以减lesscaching缺失。

消息中间件是一个很好的例子,更好地满足需求。 你有100万用户和消息的发布者到不同的类别(以JMS术语 – 主题或交换),在这种情况下,如果你想过滤掉基于主题(实际上是string)的消息,你绝对不想创build哈希表百万话题的百万订阅。 更好的方法是将主题存储在trie中,所以当基于主题匹配进行过滤时,其复杂度与主题/订阅/发布者的数量无关(仅取决于string的长度)。 我喜欢它,因为你可以用这个数据结构创造性地优化空间需求,从而减lesscaching缺失。

使用树:

  1. 如果你需要自动完成function
  2. find所有以“a”或“ax”开头的单词。
  3. 后缀树是树的特殊forms。 后缀树有一整套哈希不能涵盖的优点。

有些事我没有看到任何人明确提到,我认为重要的是要记住。 哈希表和各种types的尝试通常都会有O(k)操作,其中k是以位为单位的string的长度(或等同于字符)。

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

与基本的Trie实现相比, HashTable的实现是节省空间的。 但是对于string,在大多数实际应用中,sorting是必须的。 但是HashTable完全干扰了词汇顺序。 现在,如果您的应用程序正在基于词法顺序进行操作(如部分search,所有具有给定前缀的string,按sorting顺序排列的所有单词),则应使用“试行”。 只有查找,应该使用HashTable(可以说,它提供了最less的查找时间)。

PS:除了这些, 三元search树(TSTs)将是一个很好的select。 它的查找时间比HashTable多,但在所有其他操作中是省时的。 而且,它比尝试更有效率。

一些(通常是embedded的,实时的)应用程序要求处理时间独立于数据。 在这种情况下,散列表可以保证已知的执行时间,而系数则根据数据而变化。