2

構造体のハッシュを格納する必要があるシステムを開発していますが、長さはおそらく 20 バイト未満です。ただし、一連のハッシュでハッシュを検索するプロセスを最適化するために、ハッシュのサイズをできるだけ小さくしたいと考えています。

私の質問はこれです。crc16 ハッシュに入力するデータの量と、同じ長さの別のエントリとの衝突の確率との間に関係はありますか? もしそうなら、これに最適な長さはどれですか?

18 バイトが ASCII テーブル (az、0 ～ 9) 内にあり、残りの範囲は 0 ～ 10 です。

4

4 に答える 4

5

次の単純なスクリプトは、2 つのランダムな 20 バイト シーケンスをフェッチし、CRC16 を計算し、衝突があるかどうかをチェックする無限ループを実行します。このループの事実上の継続的な評価により、衝突の割合が推定されます。

#!/usr/bin/env perl

use Digest::CRC qw(crc16);

open(my $f, '<', '/dev/urandom');
my $n = 0;
my $coll = 0;

while (1) {
    read $f, $randstr1, 20;
    read $f, $randstr2, 20;
    my $crc1 = crc16($randstr1);
    my $crc2 = crc16($randstr2);

    $n++;
    $coll++ if $crc1 == $crc2;

    printf "percent of collisions = %.6f%%\n", $coll * 100.0 / $n if ($n % 100000 == 0);
}

私のコンピューターで取得したものから、衝突の割合は約0.0016%(または1e-5"100_000 分の 1") であると思われます。これは、16 ビット ハッシュの理想的なハッシュ分布 (2^16 / 2^160)。

更新: 20 バイトは完全にランダムなバイトではなく、[a-z0-9]. そのアルファベットでの衝突を推定する更新版は次のとおりです。

#!/usr/bin/env perl

use Digest::CRC qw(crc16);

my $n = 0;
my $coll = 0;
my @chars = ('a'..'z', '0'..'9');

sub randstr() {
    my $res;
    foreach (1..20) { $res .= $chars[rand @chars]; }
    return $res;
}

while (1) {
    my $crc1 = crc16(randstr());
    my $crc2 = crc16(randstr());

    $n++;
    $coll++ if $crc1 == $crc2;

    printf "percent of collisions = %.4f%%\n", $coll * 100.0 / $n if ($n % 100000 == 0);
}

ほぼ同じ結果が得られます0.0016%。

于 2012-12-22T00:58:17.350 に答える
2

ハッシュの衝突が発生する可能性があるかどうかは、データの量ではなく、データの内容によって異なります。意図的に衝突するように選択されていない場合、データのサイズがハッシュのサイズの 10 倍になるこのような状況では、かなり安全なはずです。とはいえ、これはまだ 16 ビットのハッシュであり、衝突の可能性は最新の基準では非常に高いです。

于 2012-12-22T00:38:43.830 に答える