java - HashCode と SHA-1

Question

木を表すいくつかの大きなオブジェクトを比較し、何かをキャッシュして、新しいオブジェクトを既存のオブジェクトと毎回比較することを避けたいと思います...

質問は、何が最高のものでしょうか? （パフォーマンスと衝突の間の妥協...）。

一方では、さまざまなフィールドの値に基づいた通常の hashCode 関数があります ( effective Javaの第 3 章に従っています。しかし、このようなアプローチに伴う潜在的な衝突を評価することはできません。

一方、SHA-1アルゴリズムを使用した標準のJavaディストリビューションからのMessageDigestアプローチがあります。効率的ではないと思いますが、衝突が少ないかもしれません。私は正しいですか？私のコンテキストでは正しい解決策ですか、それとも完全に間違っていますか?

問題は、オブジェクトのサイズがどうなるかわからないということです。また、計算された値は HashTable では使用されないことに注意してください。

どうも...

Answer 1

以下を参照してください。

• http://www.javapractices.com/topic/TopicAction.do?Id=28
• https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#hashCode--
• http://www.ibm.com/developerworks/java/library/j-jtp05273.html

次の点に注意してください。

• オブジェクトは等しくない可能性がありますが、同じハッシュコードを持っています
• 衝突の可能性は、遭遇するオブジェクトの数によって異なります。
• ハッシュコードの有用性は、チェックの実装方法によって異なります

一般に、予想されるオブジェクトの数と可能なハッシュの数（最大ハッシュ値）に基づいて、衝突の可能性を判断できます。詳細な説明については、http：//en.wikipedia.org/wiki/Birthday_paradoxを参照してください。

個人的に？Javaオブジェクト（インスタンス化されたクラス）<10,000？ハッシュコード。ファイル/ブロブ/大量のデータを表しますか？SHA-1。私はデータベースでSHA-1ハッシュを使用して、同じファイルでETL作業を複数回行わないようにしています。次に、2番目のレベルでSHA-1ハッシュを再度使用して、同じセクションを複数のファイルでETLしないようにします（たとえば、異なるファイルで同じ順序が2回表示される）。

Answer 2

個人的にはhashCode()、可能性のある衝突が実際の問題であることが証明されるまで、オブジェクトに使用して、実際には発生していない可能性のある問題を先制的に最適化することを回避します。

Answer 3

誕生日の問題があるため、衝突の可能性は、作業しているアイテムの数によって異なります。

SHA-1の160ビットのスペースは非常に大きいので、衝突を確認するのに十分なアイテムがあるとは思えません。

の32ビットスペースでhashCode()は、アイテムが50,000を超えるまで、衝突の数が多くなることはありません。ただし、これは適切なハッシュアルゴリズムの使用に依存します。

SHA-1のような暗号ダイジェストを適用するには、グラフをバイトの文字列に変換する必要があります。これは、計算コストが高く、複雑になる可能性があります。

Answer 4

通常、重複ファイル/データの検出では、MD5 は速度と衝突の可能性との適切なトレードオフです。MD5 は、誰かが意図的にファイルを作成してプログラムをだます可能性がある場合には不適切です (衝突攻撃に対してわずかに脆弱です)。しかし、たまたま衝突が心配なだけなら、現時点では 128 ビット幅で十分です。

SHA-1 と SHA-256 は、意図的な衝突攻撃に対する保護を提供します (SHA-1 を使用した理論上の攻撃は知られていますが、実際の攻撃は知られていません。データのキーイングでは、160 ビットのハッシュ コード幅を超える価値はほとんどありません)。SHA-1 は MD5 の約半分の速度です。

確かに、MD5 を使用している場合、パフォーマンスはあまり問題にならないはずです。しかし、明らかにこれはデータのサイズに依存します。Javaでの安全なハッシュ関数のパフォーマンスについてまとめた情報に興味があるかもしれません。

本当に高速なものが必要で、数百万項目のデータしか扱っていない場合は、Numerical Recipes の作成者によって提案された 64 ビット ハッシュ アルゴリズムを検討する別のオプションがあります。

Java の標準的な hashCode() 実装 (たとえば、文字列) はおそらく適切ではありません。ハッシュの品質に関する問題は別として、その 32 ビット幅は、わずか 16,000 個のアイテムの後に衝突が予想されることを意味します。

Answer 5

「最適化する必要がある前に最適化しないでください」というマットbの言葉を支持します。

ただし、将来的にハッシュコード以外のものが必要だと判断した場合は、メッセージダイジェスト（私の場合はMD5）を使用して、RSSフィードからダウンロードされたさまざまなアイテムを「一意に」識別したので、同じ結果にはなりませんでした。何度もポーリングしたときにリストに何度も表示されるアイテム。これらは通常、ダイジェストをすばやく計算できるように小さな投稿でした。私の経験では、それは非常に効果的でうまく機能しました。

これらは通常、入力データのごくわずかな変更にも強く反応することを目的とした一方向性関数であるため、MD5またはSHA-1との衝突が発生する可能性は確実に低くなります。