Next: ハッシュテーブルのためのその他関数, Previous: ハッシュテーブルへのアクセス, Up: ハッシュテーブル [Contents][Index]
define-hash-table-test
でキーを照合する新しい方法を定義できます。この機能を使用するにはハッシュテーブルの動作方法と、ハッシュコード(hash
code)の意味を理解する必要があります。
概念的にはハッシュテーブルを1つの連想を保持できるスロットがたくさんある巨大な配列として考えることができます。キーを照合するにはまず、gethash
がキーから整数(ハッシュコード)を計算します。配列の長さを法(modulo)としてこの整数を縮小して(訳注:配列の長さで割った余りの整数にして)、配列内のインデックスを生成することができます。それから探しているキーが見つかったかどうか確認するためにそのスロット、必要なら近くのスロットを調べます。
したがってキーを照合する新たな方法を定義するにはキーからハッシュコードを計算する関数、および2つのキーを直接比較する関数の両方を指定する必要があります。この2つの関数は互いに一貫性をもつ必要があります。すなわちキーを比較してequalなら、2つのキーのハッシュコードは同一であるべきです。さらに(ガーベージコレクターからの呼び出しのように)2つの関数は任意のタイミングで呼び出される可能性があるので、関数が副作用をもたないこと、すぐにリターンすること、そしてこれらの関数の挙動はそのキーの不変の性質だけに依存する必要があります。
この関数はnameという名前の新たなハッシュテーブルテストを定義します。
この方法でnameを定義した後は、make-hash-table
の引数testにこれを使用することができる。これを行なう際は、そのハッシュテーブルのキー値の比較にtest-fn、キー値からハッシュコードを計算するためにhash-fnを使用することになる。
関数test-fnは2つの引数(2つのキー)をとり、それらが同一と判断されたときは非nil
をリターンする。
関数hash-fnは1つの引数(キー)を受け取り、そのキーのハッシュコード(整数)をリターンすること。よい結果を得るために、その関数は負のfixnumを含むfixnumの全範囲をハッシュコードに使用すること。
指定された関数は、プロパティhash-table-test
の配下の、nameというプロパティリストに格納される。そのプロパティの値形式は(test-fn
hash-fn)
。
この関数はLispオブジェクトobjのハッシュコードをリターンする。リターン値はobjと、それが指す別のLispオブジェクトの内容を表す整数。
2つのオブジェクトobj1とobj2がequal
ならば(sxhash-equal
obj1)
と(sxhash-equal obj2)
は同じ整数になる。
2つのオブジェクトがequal
でなければ、通常ならsxhash-equal
がリターンする値は異なるが常に異なるとも限らない。sxhash-equal
はネストされた構造体を深く再帰しないことによって十分高速になるようデザインされている(ハッシュテーブルのインデックス作成に使用するため)。加えて稀に(運次第)ではあるがsxhash-equal
が同じ結果を与える、2つの異なって見えるシンプルなオブジェクトに出会うことがあるかもしれない。したがって一般的にはオブジェクトが変更されたかどうかのチェックにsxhash-equal
を用いることはできない。
Common Lispに関する注意: Common
Lispではこれに似た関数はsxhash
と呼ばれる。Emacsは互換性のためにsxhash-equal
にたいするエイリアスとしてこの名前を提供している。
この関数はLispオブジェクトobjにたいするハッシュコードをリターンする。結果はobjの識別値であり内容が反映されているわけではない。
2つのオブジェクトobj1とobj2がeq
なら(sxhash-eq
obj1)
と(sxhash-eq obj2)
は同じ整数になる。
この関数はeql
による比較に適したLispオブジェクトobjにたいするハッシュコードをリターンする。つまり浮動小数点数とbignum以外のobjなら、それにたいする識別値(浮動小数点数ならその値にたいするハッシュコード)を生成する。
2つのオブジェクトobj1とobj2がeql
なら(sxhash-eql
obj1)
と(sxhash-eql obj2)
は同じ整数になる。
以下はcaseを区別しない文字列のキーをもつハッシュテーブルを作成する例です。
(defun string-hash-ignore-case (a) (sxhash-equal (upcase a))) (define-hash-table-test 'ignore-case 'string-equal-ignore-case 'string-hash-ignore-case) (make-hash-table :test 'ignore-case)
以下は事前に定義されたテスト値equal
と等価なテストを行なうハッシュテーブルを定義できるという例です。キーは任意のLispオブジェクトで、equalに見えるオブジェクトは同じキーと判断されます。
(define-hash-table-test 'contents-hash 'equal 'sxhash-equal) (make-hash-table :test 'contents-hash)
ハッシュ関数の実装はセッション間や異なるアークテクチャー間で変わる可能性のあるオブジェクトストレージのいくつかの詳細を使用するので、LispプログラムはEmacsセッションの間はハッシュコードが保存されることに依存するべきではありません。