問題タブ [hash-collision]

データの大きなチャンクを比較して等しいかどうかを確認する必要があります。また、1秒あたりのペア数を高速で比較する必要があります。各オブジェクトは同じ長さであることが保証されており、未知の位置にわずかな違いがある可能性があります。

以下のタイミング==は、データの先頭近くに差がある場合は演算子の使用が非常に速く、差が終わりにある場合は大幅に遅くなることを示しています。

私のユースケースでは、違いはバイトの中央または終わりの方にある可能性があります（コンテキスト：非圧縮の画像データです）。ハッシュまたはチェックサムを使用して処理を高速化する方法を探しました。md5の使用は遅くなりましたが、Pythonの組み込みhashは実際に物事をスピードアップしました。

このハッシュの技術的な詳細に興味がありますが、それは十分にハッシュのようであり、そのときhash(a) == hash(b)はa == b非常に可能性が高いですか？ハッシュの衝突がかなりまれである場合、誤検知は許容されます。その意図は、平均的な場合の比較を高速化するための高速パスです。

無限の数の文字列を 32b int にハッシュすると衝突が発生する必要があることはわかっていますが、ハッシュ関数には適切な分布が期待されます。

これら 2 つの文字列が同じハッシュを持つのは奇妙ではありませんか?

やその他を使用できることはわかってboost::hash<std::string>いますが、 の何が問題なのか知りたいですstd::hash。私はそれを間違って使用していますか？どういうわけかそれを「シード」するべきではありませんか？

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

これはプレフィックスハッシュ関数です。この方法で衝突の数を数えたいのですが、どうすればよいかわかりません。簡単そうに見えますが、いい方法が思いつかない…。

MD5、Whirlpool、SHA [n]などに、次のように整列するhexdigest出力を取得する可能性のある「特別な」入力があるかどうかは誰でも知っています。

• すべての数字
• すべての英字
• 同じ文字/パターンのすべてが一貫してまたは完全に繰り返された

Pythonの例：

これも可能ですか？ハッシュ関数に関する私の知識は、パスワードを保存するためのデータベースにそれらを適用する範囲に限定されていますが、基本的にはありません。

しかし、衝突をテストするときに、このようなケースが発生する可能性があるのではないかと思うことがあります...

2つの入力があります（例）：「SmoothCriminal」と「BillieJean」。ハッシュ関数を実行すると同じインデックスキーを返します。

array []で、曲のMP3ファイルへのパスをハードディスクに保存したいと思います。

両方ともインデックスキーとして0を返すとすると、「Smooth Criminal」はインデックス：0になり、「BillieJean」はインデックス0 + 1 ^ 2=1になります。

両方の曲が同じキーを返す場合、配列内の「BillieJean」のファイルパスをどのように見つけることができますか？

ありがとう

Slashdotによって報告されたように、MSは本日ハッシュ衝突攻撃を修正するためにASP.NETに更新を発行しました。（リンクされたTechnetページに「HashTableの衝突によりDoSの脆弱性が発生する可能性があります-CVE-2011-3414」と記載されています。）

問題は、POSTデータが既知のハッシュアルゴリズムを使用するハッシュテーブルに変換されることです。また、攻撃者が多数の衝突を含むリクエストを作成してこれを使用すると、サービス拒否を簡単に引き起こす可能性があります。

そのアップデートで問題がどの程度正確に修正されるかを誰かが知っていますか？

ハッシュに衝突攻撃を実装しようとしています (コース「暗号化」にアクセスしています)。したがって、ハッシュ (= byte-sequences byte[]) の 2 つの配列があり、両方の配列に存在するハッシュを見つけたいと考えています。いくつかの調査と多くの検討の後、シングルコア マシンでの最善の解決策はHashSet(最初の配列のすべての要素を追加しcontains、2 番目の配列の要素が既に存在するかどうかを確認する) ことであると確信しています。

ただし、8 コアと 12 GB RAM を搭載したマシンにアクセスできるため、同時実行ソリューションを実装したいと考えています。私が考えることができる最善の解決策は、Collections.newSetFromMap(new ConcurrentHashMap<A,B>()). このデータ構造を使用すると、最初の配列のすべての要素を並列に追加でき、すべての要素が追加された後contains、同一のハッシュを同時にチェックできます。

だから私の質問は、この正確な問題のために設計されたアルゴリズムを知っていますか? そうでない場合、そのような ConcurrentHashSet を問題や効果的なランタイムの複雑さに関して使用した経験はありますか? または、私を助けることができる別の事前構築されたデータ構造をお勧めできますか?

PS: 誰かが詳細に興味を持っている場合: Skandiumを使用してプログラムを並列化する予定です。

md5アルゴリズムの衝突の確率はどれくらいですか？非常に低いと思います。

私はJavaでHashMapの実装を書いています。衝突解決にはオープンアドレス法を使用しています。より良いキー配布のために、キーのハッシュコードに素晴らしいハッシュ関数を使用したいと思いintます。どのハッシュ関数がそれに適しているのかわかりませんか？

キーのハッシュコード用のハッシュ関数が必要です。