c# - Dictionary.Add 方法如何进行 O(1) 摊销？

Question

我试图从复杂性的角度更好地理解哈希表和字典在 C# 中的工作方式(但我想语言不是一个重要因素，这可能只是一个理论问题)。

我知道如果 Count 小于容量(这有点明显)。

不过，让我们看看这段代码:

public class Foo {
    public Foo() { }
    public override int  GetHashCode() {
        return 5; //arbitrary value, purposely a constant
    }
}
static void Main(string[] args) {
    Dictionary<Foo, int> test = new Dictionary<Foo,int>();
    Foo a = new Foo();
    Foo b = new Foo();

    test .Add(a, 5);
    test .Add(b, 6); //1. no exception raised, even though GetHashCode() returns the same hash

    test .Add(a, 10); //2. exception raised
}

我了解到在幕后 1. 处存在哈希冲突，并且可能有一个单独的链来处理它。

但是，在 2. 处引发了参数异常。这意味着在内部 Dictionary 会跟踪在确定其哈希后插入的每个键。这也意味着每次我们向字典添加条目时，它都会使用 equals 方法检查是否尚未插入该键。

我的问题是，如果它检查已经插入的键，为什么它看起来应该是 O(n) 的复杂度却被认为是 O(1) 的复杂度？

Answer 1

但它不必检查所有 key 。它只需要检查散列为相同值的键。而且，正如您所说，一个好的哈希码将最大限度地减少哈希冲突的次数，因此平均而言它根本不需要进行任何 key 比较。

请记住，GetHashCode 的规则说如果a.HashCode <> b.HashCode , 然后 a <> b .但是如果a.HashCode == b.GetHashCode , a 可能等于 b .

另外，你说:

Iknow that the method Add of a Dictionary is supposed to be O(1) if Count is less than the capacity (which is kind of obvious).

这不完全正确。这是理想的，假设一个完美的散列函数将为每个键提供一个唯一的数字。但在一般情况下，完美的哈希函数并不存在，因此通常您会看到 O(1)(或非常接近它)的性能，直到 Count 超过容量的某个相当大的百分比:比如 85% 或 90% .