哪种数据结构最适合实现字典？
Which data structure is most suitable to implement a Dictionary?
我必须编写一个字典程序作为数据结构和算法本科课程的学期项目，我希望找到最适合table问题的解决方案（数据结构）。
我考虑过使用 哈希 table 或 trie。有人建议我使用 treaps，但我还没有仔细研究过。
我的数据库有大约 10 万个不同的单词及其含义。该程序预计提供的基本功能是 insert, update、删除和搜索一个word/definition。如果我设法加入 自动完成 和 拼写校正 ，那将是一个额外的好处。
所以，我的问题是，牢记我的要求，哪种数据结构最适合我的目的。当我说 'best' 时，我要求的是具有最佳运行时复杂性和低成本（内存要求）的数据结构。
另外，我希望能够有一个算法 returned 所有以给定前缀开头的单词。例如，假设我进行了一个函数调用 dictionary.getWordsStartingWith("fic") 它应该 return 以 fic 开头的所有单词的列表，例如 fiction、fictitious、fickle 等。我知道如果我将我的字典实现为一个特里树，我可以做到这一点，但是这可以用散列 table 来做到吗？
如果您想进行自动 completion/prefix 匹配，您几乎肯定需要尝试一下。哈希表并不能真正做到这一点；事实上，好的哈希函数被设计成即使非常相似的键（例如相同的前缀）也映射到数组的完全不同的部分。出于散列目的，这被视为一项功能。
Treaps 基本上是使用随机性 + 堆 属性 进行平衡的二叉搜索树。一般接口是标准的BST树接口；所以它实际上只是一个实现细节，只会导致与红黑树或 AVL 树略有不同的属性。
BST 不太适合您似乎希望作为 trie 解决的问题。 BST 倾向于向下遵循不等式，而 trie 则是向下遵循等式。当您处理数字数据时，不平等比较就是一切，因为平等非常罕见（因为 space 的可能性很大）。对于字符串，每个字符的可能性都非常小，因此利用相等性更有意义，从而导致优化，例如在大多数节点上实际上不存储密钥。
总而言之，我建议继续尝试。它们被大量用于这类事情，你可以找到大量关于优化它们的资源（特别是 space），因为它们特别用于 space/cycles 的移动设备上的文本输入是溢价。与 BST 相比，学习恕我直言，这也是一个非常有趣的数据结构，您 a) 可能在新生数据结构中学到了大量知识，并且 b) 数据结构并不是那么有趣；除了平衡方案之外的一切都是微不足道的，而且平衡方案比其他任何东西都更乏味（RB 树有 7 个真正不同的平衡案例或类似的东西，很难编写 RB 树代码并使它们完全正确）。
维基百科页面有一些有用的信息：https://en.wikipedia.org/wiki/Trie。按位尝试看起来特别有趣。
我必须编写一个字典程序作为数据结构和算法本科课程的学期项目，我希望找到最适合table问题的解决方案（数据结构）。
我考虑过使用 哈希 table 或 trie。有人建议我使用 treaps，但我还没有仔细研究过。
我的数据库有大约 10 万个不同的单词及其含义。该程序预计提供的基本功能是 insert, update、删除和搜索一个word/definition。如果我设法加入 自动完成 和 拼写校正 ，那将是一个额外的好处。
所以，我的问题是，牢记我的要求，哪种数据结构最适合我的目的。当我说 'best' 时，我要求的是具有最佳运行时复杂性和低成本（内存要求）的数据结构。
另外，我希望能够有一个算法 returned 所有以给定前缀开头的单词。例如，假设我进行了一个函数调用 dictionary.getWordsStartingWith("fic") 它应该 return 以 fic 开头的所有单词的列表，例如 fiction、fictitious、fickle 等。我知道如果我将我的字典实现为一个特里树，我可以做到这一点，但是这可以用散列 table 来做到吗？
如果您想进行自动 completion/prefix 匹配，您几乎肯定需要尝试一下。哈希表并不能真正做到这一点；事实上，好的哈希函数被设计成即使非常相似的键（例如相同的前缀）也映射到数组的完全不同的部分。出于散列目的，这被视为一项功能。
Treaps 基本上是使用随机性 + 堆 属性 进行平衡的二叉搜索树。一般接口是标准的BST树接口；所以它实际上只是一个实现细节，只会导致与红黑树或 AVL 树略有不同的属性。
BST 不太适合您似乎希望作为 trie 解决的问题。 BST 倾向于向下遵循不等式，而 trie 则是向下遵循等式。当您处理数字数据时，不平等比较就是一切，因为平等非常罕见（因为 space 的可能性很大）。对于字符串，每个字符的可能性都非常小，因此利用相等性更有意义，从而导致优化，例如在大多数节点上实际上不存储密钥。
总而言之，我建议继续尝试。它们被大量用于这类事情，你可以找到大量关于优化它们的资源（特别是 space），因为它们特别用于 space/cycles 的移动设备上的文本输入是溢价。与 BST 相比，学习恕我直言，这也是一个非常有趣的数据结构，您 a) 可能在新生数据结构中学到了大量知识，并且 b) 数据结构并不是那么有趣；除了平衡方案之外的一切都是微不足道的，而且平衡方案比其他任何东西都更乏味（RB 树有 7 个真正不同的平衡案例或类似的东西，很难编写 RB 树代码并使它们完全正确）。
维基百科页面有一些有用的信息：https://en.wikipedia.org/wiki/Trie。按位尝试看起来特别有趣。