如何选择之间的哈希表和特里（preFIX树）？ [英] How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?

问题描述

所以，如果我有一个哈希表或preFIX树什么是歧视的因素，这将导致我选择了另一种之间做出选择。但从您自己的幼稚点它好像使用一个线索有一些额外的开销，因为它不被存储为一个数组，但在运行时间方面（假定最长键是最长的英语单词），它可以是基本上ö （1）（相对于上界）。也许最长的英文单词为50个字符？

So if I have to choose between a hash table or a prefix tree what are the discriminating factors that would lead me to choose one over the other. From my own naive point of view it seems as though using a trie has some extra overhead since it isn't stored as an array but that in terms of run time (assuming the longest key is the longest english word) it can be essentially O(1) (in relation to the upper bound). Maybe the longest english word is 50 characters?

哈希表是即时查找的一旦你的指数的。哈希的关键，然而得到的指数似乎是它可以很容易地采取近50个步骤。

Hash tables are instant look up once you get the index. Hashing the key to get the index however seems like it could easily take near 50 steps.

有人可以提供我在这一个更有经验的角度？谢谢！

Can someone provide me a more experienced perspective on this? Thanks!

推荐答案

尝试的优点：

基础知识：

• predictable O（k）的查找时间，其中k是关键
的大小
• 查找可以采取少于k个时间，如果它不存在
• 支持有序遍历
• 在无需散列函数
• 删除很简单

新的操作：

• 您可以快速查找键prefixes，枚举所有条目与给定的preFIX等。

链接结构的优点：

• 如果有许多共同的prefixes，它们所需要的空间是相通的。
• 在不可改变的尝试可以共享结构。而不是更新代替线索的，你可以建立一个新的这是不同的只能沿着一个分支，其他地方的一端指向旧的线索。这对于并发性，表的多个同步版本等有用。
• 在一个不变的线索是COM pressible。也就是说，它可以在后缀的同时，通过哈希consing。
股权结构

• If there are many common prefixes, the space they require is shared.
• Immutable tries can share structure. Instead of updating a trie in place, you can build a new one that's different only along one branch, elsewhere pointing into the old trie. This can be useful for concurrency, multiple simultaneous versions of a table, etc.
• An immutable trie is compressible. That is, it can share structure on the suffixes as well, by hash-consing.

哈希表的优点：

• 每个人都知道哈希表，对吗？你的系统就已经有一个很好的精心优化的实施，比试图在大多数情况更快。
• 您的键不需要有任何特殊的结构。
• 更多空间效率的较明显联线索结构（见下文评论）

• Everyone knows hashtables, right? Your system will already have a nice well-optimized implementation, faster than tries for most purposes.
• Your keys need not have any special structure.
• More space-efficient than the obvious linked trie structure (see comments below)

这篇关于如何选择之间的哈希表和特里（preFIX树）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！