ハッシュテーブル

hash-tableは、キーで連想される値を探すためのクラスである（assocでもできる）。比較的大きな問題において、hash-tableはassocより良い性能を出す。キーと値の組数が増加しても探索に要する時間は、一定のままである。簡単に言うと、hash-tableは100以上の要素から探す場合に用い、それより小さい場合はassocを用いるべきである。

hash-tableは、テーブルの要素数がrehash-sizeを越えたなら、自動的に拡張される。デフォルトとして、テーブルの半分が満たされたとき拡張が起こるようになっている。 sxhash関数は、オブジェクトのメモリアドレスと無関係なハッシュ値を返し、オブジェクトが等しい(equal)ときのハッシュ値はいつも同じである。それで、hash-tableはデフォルトのハッシュ関数にsxhashを使用しているので、再ロード可能である。 sxhashがロバストで安全な間は、列やtreeの中のすべての要素を探索するため、比較的に遅い。高速なハッシュのためには、アプリケーションにより他の特定のハッシュ関数を選んだ方がよい。ハッシュ関数を変えるためには、hash-tableに:hash-functionメッセージを送信すれば良い。簡単な場合、ハッシュ関数を#'sxhashから #'sys:addressに変更すればよい。 EusLisp内のオブジェクトのアドレスは決して変更されないため、#'sys:addressを設定することができる。

sxhash obj [関数]

: objのハッシュ値を計算する。 equalな2つのオブジェクトでは、同じハッシュ値を生じることが保証されている。 symbolなら、そのpnameに対するハッシュ値を返す。 numberなら、そのinteger表現を返す。 listなら、その要素全てのハッシュ値の合計が返される。 stringなら、それぞれの文字コードの合計をシフトしたものが返される。その他どんなオブジェクトでも、sxhashはそれぞれのスロットのハッシュ値を再帰的呼出しで計算し、それらの合計を返す。

make-hash-table &key (:size 30) (:test #'eq) (:rehash-size 2.0) [関数]

: hash-tableを作り、返す。

gethash key htab [関数]

: htabの中からkeyと一致する値を得る。 gethashは、setfを組み合せることによりkeyに値を設定することにも使用される。 hash-tableに新しい値が登録され、そのテーブルの埋まったスロットの数が 1/rehash-sizeを越えたとき、hash-tableは自動的に2倍の大きさに拡張される。

remhash key htab [関数]

: htabの中からkeyで指定されたハッシュ登録を削除する。

maphash function htab [関数]

: htabの要素全てをfunctionでmapする。

hash-table-p x [関数]

: もしxがhash-tableクラスのインスタンスなら、Tを返す。

hash-table [クラス]


  :super   object 

  :slots 		 (key value count 


hash-function test-function 


rehash-size empty deleted)

: hash-tableを定義する。 keyとvalueは大きさが等しい一次元ベクトルである。 countは、keyやvalueが埋まっている数である。 hash-functionのデフォルトはsxhashである。 test-functionのデフォルトはeqである。 emptyとdeletedは、keyベクトルのなかで空または削除された数を示すsymbol(パッケージに収容されていない）である。

:hash-function newhash [メソッド]

: このhash-tableのハッシュ関数をnewhashに変更する。 newhashは、1つの引数を持ち、integerを返す関数でなければならない。 newhashの1つの候補としてsys:addressがある。

2016-04-05