おもこん

おもこんは「思いつくままにコンピュターの話し」の省略形です

ハッシュについて

今日はハッシュについて書こうと思う。ハッシュは、あるオブジェクトから、ある定まった範囲の整数への関数で、違うオブジェクトに対して違う整数が対応することが期待されているものである。実際には一対一対応は難しいので、できるだけ一対一になるような関数を作る。ハッシュはオブジェクトを登録、参照するプログラムで用いられる。例えばコンパイラにおいて変数名の登録、参照で用いられる。

Cのハッシュの例は、「プログラム言語C」に載っている。プログラムは短く簡単なので、自分でアレンジするのは容易いだろう。

今回、対称群の部分群を検索するプログラムで、部分集合の登録にハッシュを使ってみた。前のバージョンではリストで管理していたが、ハッシュの導入により非常に速くなった。具体的には14秒かかったものが5秒になった。この経験から、検索というのは時間がかかるコストの高いプログラムなのだということが良く分かった。そしてハッシュが非常に価値があるということもわかった。リストは線形に検索をするので効率が悪く、ある意味最悪の検索方法である。より良い方法には二分木やハッシュがあるが、ハッシュが最速ではないだろうか。

このおかげで6次対称群の部分群が5時間40分で求まるようになった。このプログラムは githubにアップロードされている。