1

私のウェブアプリでは、パフォーマンスレベルを最適化するために、ハッシュで生成されたファイル名を含むキャッシュファイルをさまざまなサブディレクトリに保存しています。パフォーマンスを向上させる方法の1つは、生成された名前が8.3ファイル名構造に従うようにすることです。これにより、NTFSで短いファイル名を生成する必要がなくなります（レジストリで設定できなくなります）。

そのためには、ハッシュ（SHA1を考えていた）を8文字にトリミングする必要がありますが、これにより、衝突の可能性が大幅に高まります。私が知りたいのは、衝突の確率はどれくらいかということです。

ここで完全なSHA1ハッシュ衝突率に関する答えを見てきましたが、私の計算はひどいので、値の計算は私をはるかに超えています。

4

2 に答える 2

5

の出力は均一に分散されているためSHA-1、BirthdayParadoxを使用して衝突率を概算できます。

n出力のビットを保持すると仮定すると、レコードSHA-1を含むセットで衝突が発生する可能性は約50％です。2^(n/2)つまり、衝突率はおよそ1/2^(n/2)

より正確な回答が必要な場合は、質問で参照した回答の数式をいつでも使用できます。

したがって、ここで、各文字が1バイト（8ビット）であると仮定すると、〜レコードがある場合に衝突が発生する可能性が高くなります2^(8*8/2) = 4294967296（したがって、衝突率2.32 * 10^-8は非常に小さくなります）。

テストプログラムを使用して発見した衝突率を考慮すると、ToSHA1Fingerprint()関数は16進文字列を返します。これは、その8文字のサブ文字列が4バイトのみを表すことを意味します。したがって、上記の式に基づくおおよその衝突率はまたは1/2^(4*8/2) = 0.000015258789です0.002%。

于 2014-03-03T20:08:55.673 に答える
0

とにかく衝突率が私のニーズには高すぎるようです。次のコードを使用して約0.004％のテストを取得しています。

const int Iterations = 10;
const int Maxitems = 360000;

for (int i = 0; i < Iterations; i++)
{
    List<string> paths = new List<string>();

    for (int j = 0; j < Maxitems; j++)
    {
        string path = Path.GetRandomFileName().ToSHA1Fingerprint()
                                              .Substring(0, 8);

        paths.Add(path);
    }

    int count = paths.Distinct().Count();

    double collisionRate = ((Maxitems - count) * 100D) / Maxitems;
    collisions.Add(collisionRate);
}

double averageCollisionRate = collisions.Average();
于 2013-03-18T22:12:57.970 に答える