Lispのハッシュを使ってみた.
ハッシュの作成と値の取り出し
レコードの設定
削除
キーの比較
領域の拡張
ハッシュの作成と値の取り出し
ハッシュはmake-hash-table関数で作成できる.make-hash-tableは引数なしで呼び出す.
> (setf hash (make-hash-table ))
#S(HASH-TABLE EQL)
値はgethashで取り出せる.第一引数がキーで,第二引数がハッシュである.
> (gethash 'hoge hash)
NIL ;
NIL
返り値は二つある.第一返り値が値で,第二返り値がハッシュにレコードがあったかどうかを示す真偽値である.上の例では,第二引数がnilなので,キーに対応する値がnilなのではなく,該当レコードがなかったということになる.レコードの設定
レコードの設定はやはりsetfである.gethashでキーを指定して(レコードがあるかどうかは関係ない),その返り値に対してsetfする.
> (setf hash (make-hash-table ))
#S(HASH-TABLE EQL)
> (gethash 'hoge hash)
NIL ;
NIL
;; キーがhoge,値が"HOGE"のレコードを作成
> (setf (gethash 'hoge hash) "HOGE")
"HOGE"
> (gethash 'hoge hash)
"HOGE" ;
T
;; キーがhogeのレコードの値を"FUGA"に上書き
> (setf (gethash 'hoge hash) "FUGA")
"FUGA"
> (gethash 'hoge hash)
"FUGA" ;
T
;; キーがhogeのレコードの値をさらにnilに上書き
> (setf (gethash 'hoge hash) nil)
NIL
> (gethash 'hoge hash)
NIL ;
T
上の例で,レコードがある時は第二返り値がTであることに注意.最後の式では,第二返り値がTだから,レコードが存在してその値がnilである.第二返り値がnil,すなわちレコードが存在しない場合とは意味が異なる.値の設定にはpushも使用できる.
> (setf hash (make-hash-table ))
#S(HASH-TABLE EQL)
> (push "FUGA" (gethash 'hoge hash))
("FUGA")
> (gethash 'hoge hash)
("FUGA") ;
T
pushはsetfとは引数の順番が異なること,設定される値は(第一引数を要素とする)リストになっていることに注意.同じキーに対して複数回pushすると以下のようになる.
> (setf hash (make-hash-table ))
#S(HASH-TABLE EQL)
> (push "FUGA" (gethash 'hoge hash))
("FUGA")
> (push "FOO" (gethash 'hoge hash))
("FOO" "FUGA")
> (gethash 'hoge hash)
("FOO" "FUGA") ;
T
この例からpushによりキーに該当する値がスタックになっていることがわかる.だからpopもできたりする.上の例に続けてpopを実行してみた.
> (pop (gethash 'hoge hash))
"FOO"
> (gethash 'hoge hash)
("FUGA") ;
T
> (pop (gethash 'hoge hash))
"FUGA"
> (gethash 'hoge hash)
NIL ;
T削除
ハッシュからレコードを削除するには,remhashを使用する.
> (setf hash (make-hash-table ))
#S(HASH-TABLE EQL)
;; キーhoge,値"HOGE"のレコードを作成
> (setf (gethash 'hoge hash) "HOGE")
"HOGE"
> (gethash 'hoge hash)
"HOGE" ;
T
;; キーhogeのレコードを削除
> (remhash 'hoge hash)
T
> (gethash 'hoge hash)
NIL ;
NILキーの比較
gethashするときにはキーを指定し,ハッシュからキーが一致するものがあればそれを返す.で,member関数と同様にハッシュでもmake-hash-tableのキーワード引数testでキーの一致判定に使用する関数を指定できる.デフォルトではeqlでキーの一致を判定する.
> (setf hash (make-hash-table ))
#S(HASH-TABLE EQL)
> (setf akey '(a))
(A)
> (setf (gethash akey hash) "HOGE")
"HOGE"
> (gethash akey hash)
"HOGE" ;
T
;; eqlで判定するので,同じ値の別のオブジェクトだと
;; 該当レコードがないことになる.
> (gethash '(a) hash)
NIL ;
NIL
キーワード引数testの値をequalにしてみる.
> (setf hash (make-hash-table :test #'equal))
#S(HASH-TABLE EQUAL)
> (setf akey '(a))
(A)
> (setf (gethash akey hash) "HOGE")
"HOGE"
> (gethash akey hash)
"HOGE" ;
T
;; equalで判定するので,同じ値の別のオブジェクトでも
;; 該当レコードがある.
> (gethash '(a) hash)
"HOGE" ;
T領域の拡張
ハッシュは領域が足りなくなったら自動的に領域を拡張する.これによりハッシュは好きなだけ要素を格納できる.ここで問題になるのは領域を拡張する際の大きさである.メモリ領域の確保はコストが大きいので,領域拡張回数は少ない方がよい.拡張回数を少なくするには拡張サイズを大きくする方法があるが,それだと無駄にメモリ領域を消費する危険がある.このトレードオフの問題はプログラマがチューニングして解決するしかないように思われる.試しに以下のサンプルを使用してキーワード引数sizeの効果を確認してみた.
(setf hash (make-hash-table :size 10000))
(setf str “HOGE”)
(do ‘(i 0 (+ i 1))
((> i 100000) ‘t)
(setf (gethash i hash) str))
で,キーワード引数sizeの値を1,10,100,1000,10000と書き換えて順に実行してみた. $ time clisp hash-test.lisp real 0m3.649s user 0m3.510s sys 0m0.150s $ time clisp hash-test.lisp real 0m3.575s user 0m3.370s sys 0m0.210s $ time clisp hash-test.lisp real 0m3.646s user 0m3.460s sys 0m0.180s $ time clisp hash-test.lisp real 0m3.638s user 0m3.470s sys 0m0.170s $ time clisp hash-test.lisp real 0m3.563s user 0m3.320s sys 0m0.250s 一回試行だが,でかけりゃいいってものではない雰囲気は掴めた.さらにハッシュというと,領域の使用率の問題(※)があるが,make-hash-tableではそれをチューニングする方法を見つけられなかった.
※一般にハッシュでは領域の使用率が大きくなると検索効率が落ちる.
