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

ただし、すべてのキーをチェックする必要はありません。同じ値にハッシュされるキーのみをチェックする必要があります。そして、あなたが言うように、優れたハッシュ コードはハッシュの衝突の数を最小限に抑えるため、平均してキーの比較を行う必要はまったくありません。

GetHashCodeif a.HashCode <> b.HashCode、 thenと言うルールを覚えておいてくださいa <> b。しかし、もしa.HashCode == b.GetHashCodeにa 等しいかもしれません b。

また、次のように言います。

Count が容量よりも小さい場合、Dictionary のメソッド Add は O(1) であると想定されていることを知っています (これは明らかです)。

それは完全に真実ではありません。すべてのキーに一意の番号を与える完全なハッシュ関数を想定すると、これが理想です。しかし、一般的なケースでは完全なハッシュ関数は存在しないため、通常、Count が容量のかなり大きなパーセンテージ (85% または 90% など) を超えるまで、O(1) (またはそれに非常に近い) パフォーマンスが見られます。 .

于 2013-04-16T12:46:48.633 に答える
0

答えは簡単で難しいです。簡単な部分：それは（自分で確認できる）からです

a.Equals(b) == false

「b」を追加するときに例外が必要な場合は、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);

このメソッドの正確な実装とは何なのかはわかりませんが、ポインター (メモリ内のアドレス) に基づいていると思います。

于 2013-04-16T11:21:58.083 に答える