Next: 8.4 隣接行列の表現例
Up: 8 グラフの記述
Previous: 8.2 隣接点リストを頂点シンボルの属性リストで表す
データベースを表現する別の方法としてハッシュ表(hash table)というものが
あります．ハッシュとはかきまぜるとか細切れにするという意味を持ちます．
あるキーが与えられた場合にそのキーに関係するデータのおかれている場所を
見つけるためにその場所のアドレスをキーから直接計算する関数を用意し，
そのアドレスから直接データをとり出してこようというのがハッシュ法の
考え方です．格納場所を計算するための関数はハッシュ関数と呼ばれます．
連想リストや属性リストでは，リストの最初から順にデータを比較して調べて
ゆくということを行ないますから，求めているデータがリストの終りの方に
あると非常に時間がかかってしまうことにもなります．
ハッシュ法の場合には，データベース中に蓄積されているデータの順番に関係
なく，アドレスを求める方法なのでどのデータでもほとんど同じような時間で
検索がなされます．（もっともハッシュ関数をどのように作るかで時間は変わ
ります．）
通常は，キーの名前からその格納場所を計算するハッシュ関数を作ります．完
全なハッシュ関数はすべてのキーに対して異なる格納場所を計算できる関数で
すが，データの数が多くなれば非常に困難となります．そのため，同じアドレ
スを返すハッシュ関数であっても，そのアドレスの場所に連想リストなどを用
意しておくことで対応することもよく行なわれます．
commonlispでは，ハッシュ法のインプリメンテーションは処理系によって変わっ
てきます．ハッシュ関数をユーザが指定することもできます．
グラフ*graph4*に対してgethashを行なうだけで隣接点リストが
得られます．
<cl> (gethash 'a *graph4*)
(s b d)
<cl> (gethash 'd *graph4*)
(s a e)
generated through LaTeX2HTML. M.Inaba 平成18年5月6日