2

によるとBirthday paradox

データベースに適用した場合(間違っている場合は修正してください):UNIQUEハッシュデータをデータベースに保存する必要があり、365の一意のハッシュ値を生成できるハッシュアルゴリズムがある場合、データが衝突する可能性は50%です。最初の23個のデータエントリの後に発生し、最初の75個のデータベースエントリの後に衝突する可能性は99.9%(!)です。

アルゴリズムが生成できる一意のハッシュの量とデータエントリの量は指数関数的に増加する可能性がありますが、衝突の確率は同じままです。これでいいの?

(Eコマース用の)トランザクションを含む巨大なテーブルがあり、フィールド「領収書」が一意に設定されています。そして、実際のレシート番号は私を悩ませているものです。

レシート番号の例:BHF2Z47E大文字のみAZ / 0-9、長さ8記号。

アップデート:

誕生日のパラドックス

4

1 に答える 1

1

誕生日のパラドックスは、のスペースでランダムに値を生成すると、値nを格納するときに衝突なしから衝突への急速な位相遷移が発生することをsqrt(n)示しています。これにより、確率が50%以上に増加します。

あなたの例では、26 + 10文字、8桁のアルファベットがあります。つまり36^8、約2.8兆の可能なキーです。約160万のエントリの後、50%を超える衝突確率が期待できます。それはあまり良くありません。そのほんの一部でも衝突の可能性は十分にあります。

比較として、レシートごとに160ビットのランダムキーを生成したとします(2^160可能な値)。次に、同じ衝突確率に到達するために、約2^80レシート(約)を生成する必要があります。10^24あなたはあなたの生涯にわたって非常に大きな会社としてあなたの製品を売ることができます、そしておそらくまだ何も見ません。もう1つの見方は、衝突を観察する前にハードディスクまたはコンピューターに障害が発生することです。

この記事の表は、具体的な数値を示しています。たとえば、256ビットのハッシュ値と10^31値が挿入されている場合、衝突確率は。になり10^-15ます。その記事によると、それはあなたのハードディスクの修正不可能なエラー率の周りです。それはおそらく、領収書を上書きしないようにするために、領収書で目指すべきものの大きさです。値を少し大きくするのは難しいことではありません。

もちろん、これは、ランダムデータを使用してPRNGを適切にシードするという事実に依存します。そうしないと、同じキーを簡単に取得できます:)

于 2013-03-08T15:55:37.003 に答える