为什么 String.GetHashCode 的复杂度为 O(1)

Question

我想使用字符串作为字典中的键类型。喜欢

Dictionary<string, string>

。

据我了解，如果我想添加一个新对象，它首先计算密钥的哈希码，然后将其与已经存在的进行比较。所以 Add 方法的复杂性归结为

String.GetHashCode()

方法的复杂性。

我不明白的是，如果我们还需要遍历所有字符来计算它，它怎么会是 O(1) 呢？

Answer 1

我认为你混淆了插入字典和字典键的哈希计算的复杂性。

String.GetHashCode()

就字符串长度（哈希码计算）而言是 O(n)，但就整个字典插入操作而言是 O(1)。

您写了

"...and then compares it against already existing"

，没有必要这样做，无论如何您都会覆盖现有值。一旦计算出哈希值，键和值就可以简单地以 O(1) 的速度插入到字典中。