如何在哈希表和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缺失。
使用树：
- 如果你需要自动完成function
- find所有以“a”或“ax”开头的单词。
- 后缀树是树的特殊forms。 后缀树有一整套哈希不能涵盖的优点。
有些事我没有看到任何人明确提到，我认为重要的是要记住。 哈希表和各种types的尝试通常都会有O(k)操作，其中k是以位为单位的string的长度（或等同于字符）。
这是假设你有一个很好的散列函数。 如果你不希望“农场”和“农场动物”哈希到相同的值，那么哈希函数将不得不使用密钥的所有位，所以哈希“农场动物”应该花费大约两倍的时间“农场”（除非你在某种滚动哈希scheme，但也有类似的操作节约scheme）。 而用香草的尝试，很明显为什么插入“农场动物”将只需要“农场”的两倍。 从长远来看，压缩尝试也是如此。
与基本的Trie实现相比， HashTable的实现是节省空间的。 但是对于string，在大多数实际应用中，sorting是必须的。 但是HashTable完全干扰了词汇顺序。 现在，如果您的应用程序正在基于词法顺序进行操作（如部分search，所有具有给定前缀的string，按sorting顺序排列的所有单词），则应使用“试行”。 只有查找，应该使用HashTable（可以说，它提供了最less的查找时间）。
PS：除了这些， 三元search树（TSTs）将是一个很好的select。 它的查找时间比HashTable多，但在所有其他操作中是省时的。 而且，它比尝试更有效率。
一些（通常是embedded的，实时的）应用程序要求处理时间独立于数据。 在这种情况下，散列表可以保证已知的执行时间，而系数则根据数据而变化。
