如何在哈希表和 Trie (前缀树)之间进行选择？

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

一些(通常是嵌入式的，实时的)应用程序要求处理时间独立于数据。在这种情况下，哈希表可以保证已知的执行时间，而尝试根据数据的不同而不同。

尝试的好处:

基本知识:

• 可预测的 O (k)查找时间，其中 k 为键的大小
• 如果找不到的话，可以少花点时间
• 支持有序遍历
• 不需要散列函数
• 删除很简单

新业务:

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

链接结构的优点:

• 如果有许多通用前缀，则共享它们所需的空间。
• 不变的尝试可以共享结构。不需要在适当的位置更新一个尝试，您可以构建一个新的尝试，该尝试仅沿着一个分支不同，在其他地方指向旧的尝试。这对于并发性、表的多个并发版本等非常有用。
• 不可变的尝试是可压缩的，也就是说，它也可以通过散列来共享 后缀上的结构。

散列表的优点:

• 每个人都知道散列表，对吧? 您的系统已经有了一个优化良好的实现，比大多数情况下的尝试都要快。
• 你的钥匙不需要有任何特殊的结构。
• 比明显的链接三元结构(请看下面的评论)更节省空间

使用树木:

1. 如果您需要自动完成功能
2. 找出所有以“ a”或“ ax”开头的单词，以此类推。
3. 后缀树是树的一种特殊形式。后缀树有许多散列无法覆盖的优点。

大家都知道哈希表及其用法，但它并不完全是常量查找时间，它取决于哈希表有多大，哈希函数的计算复杂度。

在大多数工业场景中，即使是很小的延迟/可伸缩性问题(例如: 高频交易) ，为高效查找创建巨大的哈希表也不是一个优雅的解决方案。为了减少缓存丢失，您还必须考虑优化数据结构以适应它在内存中占用的空间。

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

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

这是假设您有一个很好的散列函数。如果你不想让“农场”和“农场动物”散列到相同的值，那么散列函数将不得不使用键的所有位，所以散列“农场动物”应该是“农场”的两倍长(除非你在某种滚动散列场景，但也有类似的操作节省场景与尝试)。如果用香草的话，就很清楚为什么插入“农场动物”的时间会是插入“农场”时间的两倍。从长远来看，压缩尝试也是如此。

与基本的 试试实现相比，HashTable 实现的空间效率更高。但是对于字符串，在大多数实际应用中排序是必要的。但是 HashTable 完全扰乱了字母顺序。现在，如果您的应用程序正在执行基于词法顺序的操作(比如部分搜索，所有前缀给定的字符串，所有单词按排序顺序) ，那么您应该使用 Tries。对于只进行查找，应该使用 HashTable (可以说，它提供了最短的查找时间)。

除此之外，三元搜索树是一个很好的选择。它的查找时间比 HashTable 多，但是在所有其他操作中都很有效。而且，它比尝试更节省空间。