今日わXORベースのハッシュの衝突確率についてチョットイイ話をする、 定義 ここでハッシュとは、n種類中のr個のシンボルで表せる何かであるところのX(簡単のためrが一定として、最大C(n, r)種類の何かのブツ。ここでC(n, r)はコンビネーション)を、0~C(n, r)-1よりかなり小さい値域の整数に対応付けたものを指す。さらに、ハッシュはハッシュでもXORベースのハッシュとは、以下の手段で作ったハッシュH(X)を(ここでは)指す。 ハッシュシード HS(s(k)) n種類のシンボルs(k) (k=1..n)それぞれに互いに異なるランダムなm bitの整数を割り当てたもの。 ハッシュH(…