長さの異なる2つの文字列が同じハッシュコードを持つことはできますか？

Question

2つの異なる文字列が同じハッシュコードを返すことができることを認識していますが、異なる長さの文字列を2つ見つけることができませんでした。これは可能なのか、もしそうなら、例が分かるだろう。これは、何か変更があった場合に備えて、javaのハッシュコード関数を使用しています。

Answer 1

ハッシュコードは、intのスペースに分散しています。 intの値は2^32 = ~4 billionです。できるだけ多くの文字列が存在するので、ピジョンホールの原則では、同じハッシュコードを持つ複数の文字列が存在する必要があります。

しかし、これは以下のように同じ長さの文字列が同じハッシュコードを持つことは証明しません。 Javaでは、文字列のハッシュに式s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]が使用されています。これを知ると、同じハッシュコードを持つ異なる長さの文字列を構築するのは簡単です：

let String s1 = "\001!";とString s2 = "@";です。次にs1.length() != s2.length()しかしs1.hashCode() == '\001' * 31 + '!' == 1 * 31 + 33 == 64 == s2.hashCode() == '@' == 64。

しかし、あなたが想像するほど低くはないが、私は再びあなたのことを与えている、なぜならBirthday Paradoxの、その衝突のあなたの確率が低い、intの 4オーバーの可能な値があるとしましょう約77Kハッシュ後に衝突の確率は約50％です（ハッシュは無作為に分散されていると仮定します。データは実際にあなたのデータに依存しています - 非常に小さい文字列を処理する場合は頻繁に衝突します）。ただし、ハッシング取引を使用するすべてのデータ構造は衝突に対処する必要があります（一般的な方法は、各ハッシュ位置でリンクリストを使用することです）。

Answer 2

はい、これが起こります。

いくつかではなく些細な例：

• 初期ゼロ値の文字がハッシュコードに影響を与えるので、など（例えば）"foo"、"\0foo"、"\0\0foo"、していない、すべてが同じハッシュコードを持っています。
• 次の文字を追加する前に、各キャラクタに31が掛けられます。 2文字の文字列new String(new char[] { 12, 13 })は、単一文字new String(new char[] { 12 * 31 + 13 })と同じハッシュコードを持ちます（ここでは12と13を任意に選択しました; 12 * 31 + 13アナログが2つの範囲内にとどまっている限り、他の値についても同じことが成り立ちます） -byte-unsigned-integer range）を指定します。

しかし、これらはほんの簡単に構成できる例です。また、それらの間に明白な関係がないにもかかわらず、同じハッシュコードを持つためにうまくいくストリングのペアがたくさんあります。