23

インスタンスでGetHashCode()メソッドを呼び出すときに重複する値を取得する確率を知りたいです。stringたとえば、このブログ投稿によると 、x86 マシンで同じハッシュコード (1758039503) を持っていますblair。brainlessness

4

6 に答える 6

39

大きい。

(ジョンごめん！)

短い文字列間でハッシュ衝突が発生する確率は非常に高くなります。一般的な単語から抽出されたわずか 1 万個の異なる短い文字列のセットが与えられた場合、セット内で少なくとも 1 つの衝突が発生する確率は約 1% です。80,000 個の文字列がある場合、少なくとも 1 つの衝突が発生する確率は 50% を超えます。

セットのサイズと衝突の確率の関係を示すグラフについては、この件に関する私の記事を参照してください。

https://docs.microsoft.com/en-us/archive/blogs/ericlippert/socks-birthdays-and-hash-collisions

于 2011-11-01T16:00:14.897 に答える
26

小さい-任意の2つの等しくない文字列が衝突する可能性について話している場合。（もちろん、文字列がどれだけ「任意」であるかによって異なります。コンテキストが異なれば、使用される文字列も異なります。）

大規模-任意の文字列の大規模なプールで少なくとも1つの衝突が発生する可能性について話している場合。小さな個々の確率は、誕生日の問題に一致しません。

それはあなたが知る必要があるすべてについてです。衝突が発生する場合は間違いなくあり、可能なハッシュコードは2つだけであり、文字列の数はそれ以上であることに注意する必要があります。したがって、鳩の巣原理は、少なくとも1つのハッシュコードに複数の文字列が必要であることを証明しています。それを生成します。ただし、ハッシュがかなり合理的に設計されていることを信頼する必要があります。

特定の文字列に一致する可能性のあるものを絞り込むための非常に優れた方法として、これを信頼できます。これは、多くの衝突を生成する異常な自然発生の文字列のセットになります。衝突が発生した場合でも、候補の検索セットを50Kから10文字列未満に絞り込むことができれば、かなり大きなメリットがあります。ただし、文字列の一意の値としてこれに依存してはなりません。

.NET 4で使用されるアルゴリズムはx86とx64で異なるため、この例はおそらく両方のプラットフォームで有効ではないことに注意してください。

于 2011-11-01T15:29:46.260 に答える
14

言えることは、「小さいが有限であり、間違いなくゼロではない」ということだけだと思います。つまり、2つの異なるインスタンスに対して一意の値を返すことに依存してはなりません。GetHashCode()

私の考えでは、ハッシュコードは、2つのインスタンスが同じであるかどうかではなく、異なるかどうかをすばやく確認したい場合に最適です。

言い換えると、2つのオブジェクトのハッシュコードが異なる場合、それらは異なることがわかり、（おそらく高価な）より深い比較を行う必要はありません。

ただし、2つのオブジェクトのハッシュコードが同じである場合は、オブジェクト自体を比較して、実際に同じであるかどうかを確認する必要があります。

于 2011-11-01T15:29:02.247 に答える
1

あなたの質問が文字列のグループでの衝突の確率であることが意図されている場合に備えて、

n個の利用可能なスロットとm個の占有アイテムの場合：
Prob。最初の挿入時に衝突がない場合は1です
。2回目の挿入で衝突がない場合は（n
--1）/n確率です。3回目の挿入で衝突がない場合は（n-2）/n
確率です。m番目の挿入で衝突がない場合は（n-（m --1））/ n

m回の挿入後に衝突が発生しない確率は、上記の値の積です：（n --1）！/（（n --m）！* n ^（m -1））。

これは単純化して（nはkを選択）/（n ^ m）になります。

そして、誰もが正しいです、あなたは0の衝突を仮定することはできません、それで、確率が「低い」と言うことは本当かもしれませんが、衝突がないと仮定することはできません。ハッシュテーブルを見ている場合、標準では、ハッシュテーブルが約2/3いっぱいになると、重大な衝突で問題が発生し始めると思います。

于 2011-11-01T16:12:38.180 に答える
-1

1 / 2^(bits in hash code)ハッシュが完全な場合、ランダムに選択された 2 つの文字列が衝突する確率はです。これはありそうもないか不可能です。

于 2011-11-01T15:35:00.970 に答える