MD5は、4バイトと8バイトのキーを16バイトの値にハッシングします。衝突のチャンスは何ですか？

Question

私は2を持っています私がハッシュしている4バイトのキー。衝突のチャンスは何ですか？私は2 8バイトの鍵を持っている場合（実際にはすべてのキーを保存するが、私は最悪のケースを知られたくない）何

？

Answer 1

the wikipedia page on the Birthday Problemの場合、良好な1次近似が1-e^(-(n^2)/d)で見つかります。あなたの値をグラフ化すると、this graph（対数横軸、確率が急上昇する位置を拡大しています）となります。これは近似値に過ぎず、控えめに考えなければならないことに注意してください（実際の確率はやや高いかもしれませんが、正しい球場にあるはずです）。

Answer 2

ハッシュコードはどうしていますか？ 2つのデータが同じであるかどうかを調べるためにそれらを使用している場合、悪意のあるエンティティによって作成されていないデータを扱っている場合に限り、MD5ハッシュはかなり良いです。 （暗号の目的は、「悪意のある攻撃者」の問題に対処するために、より良いハッシュアルゴリズムを正確に必要とします。）

マップを構築するためにそれらを使用している場合安価なハッシュを使用して、衝突のコストを軽減する方法を考え出します（たとえば、ハッシュテーブルからリンクされたリストをハングアップし、平均的な重みが大きくなりすぎるとサイズ変更/再構築するなど）。