#ちょいメモ。Gaucheのハッシュテーブルを改善したいってのをずっと考えてて、ハッシュ関数を複数持たせたいってのがある。Cuckoo hashとかにも使えるし、コリジョン攻撃への対応というのもある。でもカスタムハッシュ関数を許すテーブルとどうやって折り合いをつけるか。
#パラメタライズされたハッシュ関数を取ることにする、という手はある。hash :: obj -> int じゃなくて、例えば hash :: (obj, int) -> int で、intに与える値によって結果は変わるんだけど性質 (eq(a,b)がtrueならhash(a,x)==hash(b,x) for all x) は変わらない
#でも既存のハッシュテーブルsrfiやcomparator srfiはパラメタライズされたハッシュ関数とは互換性がない。可能性としては、srfi-39 parameter経由でパラメータを渡すことにして(ややこしいな)、組み込みのハッシュ関数はそれに対応させる。それだと、組み込みのハッシュ関数の結果を組み合わせるだけのカスタムハッシュ関数は自動的にパラメタライズされることになる。
#コリジョン攻撃は起動時に毎回ランダムに初期化されるソルトをハッシュ値の計算に加えるとかではだめなんですか
#ハッシュ関数の生成値が同じだと以降の計算の値は全部同じになるので意味ないですよね。組み込み関数はいくらでもやりようがありますが、カスタムに外から与えられるハッシュ関数については互換性を保ったまま何とかするのは難しいってことです。
#あと、GaucheのhashはCommon Lispのsxhashと同様、同じ(equal?)なオブジェクトのハッシュ値はプロセスをまたいで一定であることを保証しないとならないです(永続化するデータにも使えるようにするため)。それとランダムソルトの整合性をどう取るか。
#ハッシュ関数がパラメタライズされるって仕様なら、hashを従来どおり呼び出した場合は既定値のソルト(一定)が使われるので結果も同じ、だけど組み込みハッシュテーブルで使う時はランタイムがランダムソルトをパラメタに与える(どうせ内部ハッシュテーブルに使われてるハッシュ値を外部で利用することはないから)ということで互換性は保たれるかなと。
Gauche > Archives > 2015/03/22