实现单词字典的数据结构

Question

最近，我在一次采访中被问及数据结构的用法。问题是:在创建英语词典时，我打算使用什么数据结构？词典将包含每个字母表下的单词数，每个单词将有一个意思。另外，我将如何实现数据结构来更新、搜索和选择不同的单词？

你有什么建议吗？你提出建议的原因是什么？

Answer 1

哈希表将是实现具有更新、搜索和选择功能的字典的首选数据结构。

哈希表是一种可以存储键值对的数据结构.它本质上是一个数组，包含所有要搜索的键。哈希函数(h())用于将索引计算到数组中，在数组中可以插入或搜索元素。因此，当需要插入时，哈希函数用于查找需要插入元素的位置。

在合理假设下插入的是O(1)。每次我们插入数据时，都需要O(1)时间来插入它(假设哈希函数是O(1))。

查找数据也是类似的。如果我们需要找到单词x的含义，我们需要计算h(x)，这将告诉我们x在哈希表中的位置。因此，我们也可以在O(1)中查找单词(哈希值)。

然而，O(1)插入和搜索并不总是正确的。没有什么可以保证哈希函数不会为两个不同的输入产生相同的输出，因此会发生冲突。为了处理这种情况，可以使用不同的策略，即单独链接和开放寻址。但是搜索/插入将不再是O(1)。