如何实现字典(Trie和重要问题)？

Question

我遇到了几个问题和文章，这些问题和文章说，java中的字典实现在尝试中做得最好。但据我所知，他们中的大多数都没有提到重要的问题。因此，接下来是一个现实世界的任务：

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

请回答下一个问题：

如果我想让字典(搜索，字典)区分大小写，那么我应该使用什么数据结构(Trie或HashTable)?

• How )来组织它(搜索，数据结构)，如果我需要字典是insensitive?

• What呢？

P.S.：代码示例非常受欢迎。:)

谢谢你提前给我答案。

UPDATE：如果我们讨论的是java中的标准DS实现，那么HashTable确实是这个特定任务的最佳实现吗？为什么不是HashMap，TreeMap还是LinkedHashMap？

Answer 1

我只想谈一谈你问题中的一点：

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

所有这些实现都依赖于字典元素的排序，它们都有一个对数的平均值和最坏的运行时，用于公共操作。

相反，哈希表不需要元素的相对排序。相反，它要求元素具有可理解性和平等可比性。常见哈希表特征的最坏情况比树差得多，即元素数是线性的。

但是，稍微小心一点，哈希表操作的平均情况可以保持不变(即与容器大小无关)。更重要的是，可以证明缓慢的操作是非常罕见的。

在实践中，这意味着除了非常专门的用例之外，哈希表比基于树的字典更容易使用.

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

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

只有在处理字符串值字典时，才能使用基于trie的实现，在这种情况下，它通常是一个很好的选择，特别是当字典中的许多字符串共享共同的前缀并且相当短的时候。

Answer 2

编辑停止讨论这个问题:我误解了这个问题。OP不是在查字典来验证单词spellings/suggestions/type-ahead-lookup/auto-completion/whatever (我以为这就是他想要的)。OP是在键/值映射之后，每个单词都有一个定义。

在写过字典之后，我可以告诉你，你采取了错误的方法。

这并不像在散列表和trie之间的选择那么简单。

你提到林格:这不仅仅是一张桌子。

你想要近距离的比赛提供建议吗？然后，您可能需要在用户输入的内容上生成排列，对于每个置换，查看它是否存在于dico中:如果存在，则需要计算它的“Levenhstein编辑距离”，并首先建议具有最短LED的单词。

你想要最有可能的匹配是自动完成/建议(就像谷歌所做的)？然后，您需要一个非常先进的数据结构，如BK树(基本上是一棵LED树，如果我正确理解的话)。

你的字典里有几个单词？您将无法使用使用Strings和其他重量级Java对象/数据结构的由40万个单词组成的字典，而不会受到严重的性能影响(再说一次:字典不仅仅是一个哈希表，一个字典通常包含多个数据结构)。这将不容易适应您的用户的计算机内存。有一些已知的、可搜索的存储单词的方法，其中每个单词可以被包装在少于每个单词的15位上(每个单词少于15位，您正确地阅读)。

此外，您还可以根据语音进行建议:比如使用双元电话映射。

字典(如"word字典“中的字典)是，所以不仅仅是一个键/值表。它确实是一个复杂的野兽，因为它的特点，用户应该除了和由于所涉及的数据量。只是简单的英语+一些专门的领域术语，医学，comp，什么的。将为您提供数十万个数据:尝试将其放入Java HashMap中.卡博姆！

Answer 3

字典的实现，绝对是哈希集合的最佳选择。

关于HashMap 或 HashTable：主要是如果您的类是以多线程方式使用，而不是必须使用HashTable，否则HashMap是最好的选择。

HashMap vs TreeMap**:**如果您需要将插入顺序插入到集合中，那么我们必须使用TreeMap。

HashMap vs LinkedHashMap**:** LinkedHashMap实现与HashMap的不同之处在于它维护了一个贯穿所有条目的双链接列表。这个链表定义了迭代顺序，这通常是将键插入到映射中的顺序(插入顺序)。注意，如果将键重新插入到映射中，则插入顺序不会受到影响。(如果调用k将在调用之前返回true，则m.put(k, v)将重新插入到映射m中。)