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