先週, hash 構造のことでF澤さんと二人で話した内容が面白かったので,
まとめ。
ハッシュの設計には
- キーが衝突した時のデータ構造(分離連鎖法(リンクドリスト)/開番地法(1つの配列 中で次を探す))
- ハッシュ関数の定義
の2つの自由度があるが, このうちデータ構造はどちらか選ぶだけなので
除くとすると, 残るのはハッシュ関数の設計。
で, 伝統的にこれは普通えいや, と適当に決めてしまう。別の言い方をすると,
これが最適な解, というのは知られていない(多分)。
- しかし, よく考えてみると, ハッシュのキーが一様に降ってくるならともかく, 普通は(例えば英語のテキストなら), "is" とか "the" みたいなものが圧倒的に多い。
- 一般のハッシュを考えても, 検索するアイテムに頻度の偏りがあるのは当然予想でき て, それは自然言語のキーの偏りよりももしかすると大きいかもしれない。
- すると, キーの頻度がわかっていたとすると, それに合わせたある程度最適で (キーの衝突が少ない), かつ計算量の少ない関数が設計できるのではないか。
- 例えば, 極端な例として, supercalifragilisticexpialidocious
みたいなキーが非常に多かったと仮定すると, この文字列の文字コードを普通のように
全部足し込んでハッシュにするのは効率が悪い。もっと簡単に計算できるハッシュ関数
があるはず。
- ハッシュを速くする, ということに需要があるのだろうか, ということが気になった が, 聞いてみると, データが増えるにつれハッシュを引かなければならない回数は
増えるし, 特に最近テキストデータが非常に増えているので, 大容量データに対して
(内部的に)ハッシュを引く需要はむしろ大きいのではないか, と思う。
(もしかすると気にならないのかもしれませんが,
実は高速で効率的なハッシュの需要は大きいのではないか,
という気がする。)
- さて, そうすると次の問題は, キーの頻度が動的に変わるときどうするか, という問題。むしろ実際的には, キーの頻度が事前にわかっていることは少なくて,
データに対して適応的に関数が再構築されるという方が嬉しいと思う。
- もちろんその際にはデータ構造の中で場所を入れ換えないといけないので, 適切なタイミングを図るか, 途中で緩衝を入れたりして再構築の影響を吸収する必要は
あると思う。
- この辺りで情報圧縮との関連性が明らかになってくるわけで, うまいハッシュ関数を 設計することで, 入力キーに対するデータ構造上の符号長を最小にするように
できるか, という(ような感じの)問題になる。
- そうすると, 窓幅の適応的な取り方とか, 上のような forward な関数の推定だけで なくて, 後ろから見る場合も考えるとか, 非常に圧縮っぽい話になってくると思う。
..というようなことを, ハッシュ関数のデバッグのついでに
話した。
もちろん, このへんの話は研究的にはある程度進んでいるかもしれない, とは思う
のだけれども。