java - 如何实现字典(Trie vs HashTable 等重要问题)？

Question

我遇到过几个问题和文章，说 java 中的字典实现最好使用尝试。但据我所知，其中大多数都没有解决重要问题。所以，接下来是一个现实世界的任务:

让我们假设我需要使用 java 实现一个字典(假设像 Lingvo，但更简单)。对于我的特定任务，它需要存储单词定义并执行快速字典查找。

请回答下一个问题:

• 我应该使用什么数据结构(Trie 或 HashTable)？
• 如果我需要字典不区分大小写，它(搜索、数据结构)应该如何组织？
• 如果我希望它(搜索、字典)区分大小写怎么办？

P.S.:非常感谢代码示例。 :)

提前感谢您的回答。

更新:如果我们谈论的是 java 中的标准 DS 实现，那么 HashTable 真的是完成这项特定任务的最佳选择吗？为什么不是 HashMap、TreeMap 或 LinkedHashMap？

Answer 1

我只想解决您问题中的一点:

A trie 不是通用字典数据结构。原因是 trie 是用于(子)字符串搜索的专用搜索树。通常，您会对一般搜索树更感兴趣，例如binary search trees或 B-trees .

所有这些实现都依赖于字典元素的排序，并且它们都具有用于常见操作的对数平均情况和最坏情况运行时间。

相比之下，散列表 不需要元素的相对顺序。相反，它要求元素可散列 和相等性可比。普通哈希表的最坏情况特征比树差很多，即元素数量呈线性关系。

但是，只要小心一点，哈希表操作的平均情况可以常量(即独立于容器大小)。更重要的是，可以证明，较慢的操作是极其罕见的。

在实践中，这意味着除了非常特殊的用异常(exception)，哈希表轻而易举地击败了基于树的字典。

这样做的缺点是哈希表对其元素强加了一种看似任意的顺序。如果您有兴趣按排序顺序从字典中获取项目，哈希表不适合您。

(还有其他有趣的字典实现，例如 skip lists 可与搜索树和概率实现相媲美，如 Bloom filter。)

只有在处理字符串值字典时才能使用基于 trie 的实现，在这种情况下，它通常是一个不错的选择，尤其是当字典中的许多字符串共享公共(public)前缀并且相当短时。