c++ - 大文本中搜索词的哈希表。O(1)

Question

我必须为大文本（搜索、粘贴、删除）创建运算速度为 O(1) 的哈希表。这是真的吗？如何减少碰撞？有什么例子吗？后来我再也没用过 C++。我找不到任何带有文本字典的示例哈希表。
目标语言 C++（仅限 STL）。

Answer 1

您可以使用unordered_map或unordered_set作为标准的一部分，或者如果不是选项C++11，则使用这些容器的 boost 版本。C++11如果您需要自己实施解决方案，我相信您可以使用其中任何一个的实施作为参考。

编辑：作为 amit 的指针，这仍然不是常量，因为您需要散列一个字符串，因此您需要至少遍历它一次。因此，复杂性在于要搜索的字符串在O(|S|) 哪里。S此外，无论散列函数冲突可能 O(|S|)发生多么好（除了可以使用完美散列的非常罕见的情况外，由于生日悖论，它会以非常非常高的概率出现）。