キャーこの人置換表です

ハッシュ関数のバリデーション

いま何か適当な分布（一様とは限らない）に従い生起する事象sがあったとして、ハッシュ関数fでもってハッシュキーhをh=f(s)として作ったとする
このとき（sの分布は一様とは限らないにもかかわらず）hの剰余h % Nは有限の区間[0, N)の範囲内で一様に分布して欲しい
かような虫の良い思惑が外れなかったことを調べ鯛、
のだが
ネットに情報が無いのでここに書く、

その(1): 置換表が埋まる速度をバリデート

いまエントリ[0..N-1]からなる置換表がu_i個のエントリまで埋まっているとする、
エントリの確保はh=f(s)の剰余h % Nが指すエントリを割り当てるものとすると、直近に確保するエントリ[h % N]が既存エントリの上書きにならない確率は、
　1 - u_i/N
であり、この確率で、確保後のu_iが+1される、すわなち
　u_(i+1) = u_i + (1 - u_i/N) * 1 + (u_i/N) * 0 = 1 + *1

その(2): 置換エントリ毎の衝突回数をバリデート

いわずと知れた話で、エントリの確保1回につき、既存エントリが上書きされる確率は1/N。これを確認する、
すわなち、順当に行けば全エントリの上書き回数は1/Nづつ増加する。実際には当たるときと外れるときがあり、hの一様性から時間平均は長時間見たらどっちも同じ頻度で生起するから、c_i = (1/N)*iを中心とするランダムウォーク的な振る舞いとなる
c_iから外れるエントリがあったらNG

理想的なハッシュ関数とは、

置換表サイズNを素数として、ハッシュ関数hは最小完全ハッシュとして、h(s)の結果をNで剰余すれば良い
上のテストにはよゆーでパスする*2

*1:N-1)/N) * u_i という漸化式を得るが、これは 　u_1 = 1 　u_i = (1 - α^i) / (1 - α) に他ならぬ ここでα=((N-1)/N)である。Excelで1兆項ぐらい計算するとﾜｶﾙが、u_iはNに収束する。 これのiの増加に対する曲線と、実際の置換表の埋まる曲線を比較すればおk 下回り続けるようなら一様性に問題がある((上回り続けても一様でないと言えるが、他の基準に抵触しなければひとまずおk（多分有り得ないが

*2:筆者の想像だが