3

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

我知道Adda的方法Dictionary应该是 O(1) 如果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) 复杂度？

4

2 回答 2

1

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

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

另外，你说：

我知道如果 Count 小于容量（这很明显），字典的 Add 方法应该是 O(1)。

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

于 2013-04-16T12:46:48.633 回答
0

答案既简单又困难。简单部分：是因为（可以自己查）

a.Equals(b) == false

如果您在添加“b”时想要异常，只需实现 Equals 方法。

没有困难的部分：Equals 的默认对象实现调用 RuntimeHelpers.Equals。RuntimeHelpers 的来源在这里。不幸的是，该方法是外部的：

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

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

于 2013-04-16T11:21:58.083 回答