如何能方法字典.加上0(1)平摊

Question

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

我知道如果Count小于容量(这是显而易见的)，Dictionary的方法Add应该是O(1)。

但是，让我们看一下代码:

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(1)的复杂度，当它看起来应该是O(n)，如果它检查已经插入的键?

Answer 1

但是它不需要检查所有的键。它只需要检查散列值相同的键。而且，正如你所说的，一个好的哈希码会最小化哈希冲突的数量，所以平均来说，它根本不需要进行任何键比较。

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

你还可以说:

我知道如果Count小于容量(这是很明显的)，那么Dictionary的方法Add应该是O(1)。

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

Answer 2

答案既简单又困难。简单的部分:这是因为(你可以自己检查)

a.Equals(b) == false

如果你想在添加"b"时出现异常，只需实现also Equals方法。

没有困难的部分:Equals的默认对象实现调用RuntimeHelpers.Equals。RuntimeHelpers的源代码在这里。不幸的是，方法是extern:

    [System.Security.SecuritySafeCritical]  // auto-generated
    [ResourceExposure(ResourceScope.None)]
    [MethodImplAttribute(MethodImplOptions.InternalCall)]
    public new static extern bool Equals(Object o1, Object o2); 

这个方法的具体实现是什么，我不知道，但我认为它是基于指针的(所以内存中的地址)