用于实现字典的最佳数据结构？
什么是最好的数据结构来存储字典的所有单词？ 我能想到的最好的是使用一个HashMap ，它将映射到一个HashTable 。 基本上，根据第一个字符，我们将得到相关的HashTable ，然后使用这个，我们可以添加从该字符开始的单词。 然后我们将根据stringselect一个好的散列函数。
有更好的方法吗？
根据你想要做什么，有很多好的数据结构。
如果你只是想存储单词并询问“这个单词在这里还是不是？”，那么一个没有其他花式机器的标准哈希表是一个合理的方法。 如果这个单词是提前列出的，可以考虑使用一个完美的哈希表来获得优异的性能和空间使用率。
如果您希望能够在支持快速查找的同时检查给定的前缀是否存在，则trie是一个不错的select，尽pipe它可能有点空间效率低下。 它也支持快速插入或删除。 它也允许按字母顺序进行迭代，哈希不提供。 这实质上就是你在答案中描述的结构，但根据用例，尝试的其他表示可能会更好。
如果除了上述内容之外，还知道单词列表是固定的，可以考虑使用DAWG （有向无环词表），该语言基本上是该语言的最小状态DFA。 它比实质上更紧凑，但支持许多相同的操作。
如果你想要类似行为的行为，但不想支付巨大的空间的惩罚， 三元search树是另一个可行的select，就像基数树 。 这些结构是非常不同的，但是在不同的情况下可以比结果好得多。
如果空间是一个问题，但你想要一个trie，看看简洁的trie表示，它有较慢的查找，但只是理论上最佳的空间使用情况。 该链接讨论了如何在JavaScript中使用它作为传输大量数据的简单方法。 另一种紧凑的表示forms是双数组树 ，尽pipe我对此知之甚less。
如果你想使用字典进行拼写检查等操作，需要find与其他字相似的字，那么BK树就是一个很好的数据结构。
希望这可以帮助！
