ハッシュは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ではそれをチューニングする方法を見つけられなかった.