ハッシュ関数を組み合わせることで衝突確率を下げることに関して本当の利点があるかどうかは誰にもわかりませんか? 特に 32 ビット ハッシュ、つまり Adler32 と CRC32 の組み合わせに関してこれを知る必要があります。 基本的に、adler32(crc32(data)) は crc32(data) よりも小さい衝突確率をもたらしますか? 最後のコメントはこちら結合を支持するいくつかのテスト結果を示しますが、ソースは言及されていません。私の目的では、衝突は重要ではありません (つまり、タスクにセキュリティは関係しません) が、可能であれば、衝突の可能性を最小限に抑えたいと考えています。PS: 私はハッシュの素晴らしい世界を始めたばかりで、それについて多くのことを読んでいます。ばかげた質問をした場合は申し訳ありませんが、適切な「ハッシュ方言」をまだ取得していません。おそらく、これに関する Google 検索の形式も不十分でした。ありがとう。
1370 次
1 に答える
7
このように直列に組み合わせても意味がありません。1 つの 32 ビット空間を別の 32 ビット空間にハッシュしています。
最初のステップで crc32 衝突が発生した場合、最終結果は依然として衝突です。次に、adler32 ステップで潜在的な衝突を追加します。したがって、これ以上良くなることはなく、同じか、悪くなるだけです。
衝突を減らすには、2 つのハッシュを個別に使用して 64 ビットの出力空間を作成するなどの方法を試すことができます。
adler32(データ) << 32 | crc32(データ)
それを行うことに大きなメリットがあるかどうかはわかりません。
あなたが参照した元のコメントは、ハッシュを個別に保存していたことに注意してください。
どちらのアルゴリズムを使用しても、誤検出の可能性はいくらかあります。ただし、2 つの異なるハッシュ アルゴリズムを使用することで、これらの可能性を大幅に減らすことができます。各 URL の CRC32 と Alder32 の両方を計算して保存すると、特定の URL ペアの両方のハッシュが同時に衝突する可能性が大幅に減少します。
もちろん、それは元の問題の一部である 2 倍の情報を保存することを意味します。ただし、Perl のハッシュとほぼ同じルックアップ パフォーマンス (5 マイクロ秒と比較して 15 マイクロ秒/ルックアップ) を提供しながら、最小限のメモリ (10kb 程度) しか必要としないように、両方のハッシュ データ セットを格納する方法があります。
于 2009-08-24T16:33:54.487 に答える