为什么说在哈希表中查找字符串是O(1)？

Question

• 让我们假设字符串的长度是

  L

  。现在，当我们将其插入哈希表时（假设我们使用单独的链接），首先计算字符串的哈希值。现在如何插入哈希表

  O(1)

  。计算字符串哈希值的时间随着字符串大小的增加而增长，这不应该是

  O(L)

  吗？

• 计算完哈希后，然后将字符串存储到哈希表中，现在这个复制不也需要

  O(L)

  吗？

• 现在，当在哈希表中查找字符串时，它怎么可能是一个常量操作，因为再次计算字符串的哈希，然后在计算出的存储桶中比较字符串，这在最坏的情况下也应该是

  O(L)

  案例。

  请有人解释一下。我错过了什么。谢谢你。

我尝试询问chatGPT，也在网站上寻找解决方案，但它们是冲突的，chatGPT说它将是O(L)，但有些网站说它将是O(1)。

Answer 1

C++ 标准是这么说的：

[container.requirements.general]/2 本条款中的所有复杂性要求仅根据所包含对象的操作数量来说明。 [示例：

vector<vector<int>>

类型的复制构造函数具有线性复杂度，尽管复制每个包含的

vector<int>

的复杂度本身是线性的。 —结束示例]

类似地，为了讨论基于哈希的容器上的操作的复杂性，

hash(string of length L)

被视为对所包含对象的一项操作，尽管实际计算哈希可能需要与

L

成正比的墙时间量。