11

ファイルを処理するプログラムで重複を検出するために SHA-1 を使用しています。強力な暗号である必要はなく、元に戻すことができます。この高速ハッシュ関数のリストを見つけましたhttps://code.google.com/p/xxhash/

より高速な関数と SHA-1 に近いランダム データの衝突が必要な場合は、何を選択すればよいですか?

ファイルの重複排除には 128 ビットのハッシュで十分ではないでしょうか? (vs 160 ビット sha-1)

私のプログラムでは、ハッシュは 0 ～ 512 KB のチャンクで計算されます。

4

7 に答える 7

4

あなたの場合、ハッシュアルゴリズムの唯一の関連するプロパティは衝突確率であるため、それを推定して、要件を満たす最速のアルゴリズムを選択する必要があります。

アルゴリズムが絶対的な均一性を持っていると仮定すると、可能な値がdのハッシュを使用して、 n 個のファイル間でハッシュが衝突する確率は次のようになります。

ここに画像の説明を入力

たとえば、100 万個のファイル間で 100 万分の 1 未満の衝突確率が必要な場合は、5*10^17 を超える個別のハッシュ値が必要になります。つまり、ハッシュには少なくとも 59 ビットが必要です。均一性が悪い可能性があるため、64 に丸めます。

したがって、適切な 64 ビット ハッシュで十分であると言えます。ハッシュが長くなると、衝突の確率がさらに低下しますが、計算が重くなり、ハッシュ ストレージの容量が増加します。CRC32 のような短いキャッシュでは、明示的な衝突処理コードを記述する必要があります。

于 2015-04-14T13:01:40.277 に答える
3

異なるファイルやチャンクを検出するには、128 ビットで十分です。少なくとも意図的な衝突が試みられていない限り、衝突のリスクはごくわずかです。

追跡したいファイルまたはチャンクの数が「十分に小さい」ままである場合 (つまり、数百万を超えない場合) は、64 ビットでも十分であることが証明されます。

ハッシュのサイズが決まったら、リンクに Q.Score=10 でリストされているものなど、いくつかの非常に優れた分散特性を持つハッシュが必要です。

于 2015-04-11T08:33:53.573 に答える
3

事実：

  1. 優れたハッシュ関数、特に暗号化関数 (SHA-1 など) は、この場合にはあまり役に立たない多くのプロパティを尊重する必要があるため、かなりの CPU 時間を必要とします。
  2. 任意のハッシュ関数で得られる確実性は 1 つだけです。2 つのファイルのハッシュ値が異なる場合、それらのファイルは確実に異なるものです。ただし、それらのハッシュ値が等しい場合、ファイルも等しい可能性がありますが、この「等しい」ことが単なるハッシュの衝突ではないかどうかを確認する唯一の方法は、2 つのバイナリ比較にフォールバックすることです。ファイル。

結論:
あなたのケースでは、CRC32 のようなはるかに高速なアルゴリズムを試してみます。これは、必要なほとんどすべてのプロパティを備えており、99.9% 以上のケースを処理でき、低速の比較方法 (バイナリなど) にのみ頼ることができます。比較）、誤検知を除外します。大多数の比較ではるかに高速であることは、おそらく「素晴らしい」均一性がないことを補うでしょう（おそらく、さらにいくつかの衝突が発生します）。

于 2015-04-11T05:16:33.330 に答える
1

それは、反復で計算するハッシュの数に依存します。たとえば、64 ビットのハッシュは、計算された 600 万のハッシュで 1000000 分の 1 の衝突確率に達します。

参照 :ハッシュ衝突確率

于 2015-04-14T13:45:21.413 に答える