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