2

私はハッシュとハッシュテーブルを読んで学習しており、いくつかのコードで実験しました（私はまだこれに非常に慣れていないので、誤解した何か間違ったことを言うかもしれません）。私は完全なハッシュ関数の問題に直面しました。どういうわけか完全なハッシュ関数を持つ独自のカスタム型があるとします。

class Foo
{
    private int data;

    override int GetHashCode()
    {
        return data.GetHashCode();
    }
}

Anintのハッシュコードはintそれ自体なので、完全なハッシュ関数を持っていますよね? しかし、ハッシュ関数を使用して、単純な式でオブジェクトをハッシュテーブルにマップすると、次のようになります。

index = foo.GetHashCode() % hashtable.Length

ハッシュテーブルにある要素の数にも依存する可変インデックスを取得します。ハッシュテーブルのサイズが int.MaxValue のみの場合、完全なハッシュ関数が得られます。たとえば、サイズが 2 のハッシュテーブルがあるとします。たとえば、数値 1 と 3 をハッシュすると、次のようになります。

1 % 2 = 1
3 % 2 = 1

衝突！ハッシュとハッシュテーブルについて何か間違ったことを理解しましたか? 完全なハッシュ関数は完全ではないことがわかります。

4

3 に答える 3

7

この時点までは大丈夫です

index = foo.GetHashCode() % hashtable.Length

ハッシュ関数は完璧ですが、モジュロを計算すると、実際には別のハッシュ関数を使用しています。この場合、ハッシュ関数int.GetHashCode は完璧ですが、使用するデータ構造foo.GetHashCode() % hashtable.Length は ではありません。つまり、1 つはオブジェクトのハッシュであり、別のものはそれらのオブジェクトを保持する構造体によって使用されるハッシュです。

データ構造も完璧であるためには、その最大サイズも int の数でなければなりません。

では、なぜ に衝突がないのDictionaryでしょうか? 実際、そうです。2 つのオブジェクトAとBがディクショナリに同じハッシュを持つ場合、衝突が発生します。A.Equals(B)2 つのオブジェクトが実際に同じかどうかを確認する最終チェックとしてディクショナリが実行されます。そうである場合、重複があるという例外が発生します。そうでない場合、それらは両方とも同じ辞書ハッシュの下に保持されます。

于 2013-05-11T20:48:47.370 に答える
3

  1. はい！（定義上、前述のとおり）

  2. そもそもphfはどこから入手するのですか？固定された、つまり、異なる(つまりマルチセットがない) 値の定数セット S をセット 1..|S| に全単射でハッシュしたいとします。明らかに、phf は集合 S に依存します。

  3. また、S から 1 つの要素を削除し、別の要素を追加すると、ほぼ確実に (新しい要素と古い要素の) 衝突が発生します。

  4. したがって、実際には「そのような明確に定義された/記述されたセットのphf」が必要です。そして、それを見つけようとすることができます。

于 2013-12-07T14:33:53.063 に答える
2

はい、完全なハッシュ関数は衝突しないことが保証されています。

それがまさにその定義です！

ウィキペディアから ( http://en.wikipedia.org/wiki/Perfect_hash_function )

セット S の完全なハッシュ関数は、S の個別の要素を整数のセットに衝突なしでマップするハッシュ関数です。完全なハッシュ関数には、他のハッシュ関数と同じアプリケーションの多くがありますが、衝突解決を実装する必要がないという利点があります。

于 2013-05-11T20:44:40.613 に答える