Next: , Previous: , Up: Hash Tables   [Contents][Index]


8.3 ハッシュの比較の定義

define-hash-table-testでキーを照合する新しい方法を定義できます。この機能を使用するにはハッシュテーブルの動作方法と、ハッシュコード(hash code)の意味を理解する必要があります。

概念的にはハッシュテーブルを1つの連想を保持できるスロットがたくさんある巨大な配列として考えることができます。キーを照合するにはまず、gethashがキーから整数のハッシュコードを計算します。配列内のインデックスを生成するために、gethashは配列の長さからこの整数のmoduloを得ます。それからキーが見つかったかどうか確認するためにそのスロット、もし必要なら近くのスロットを探します。

したがってキー照合の新しい方法を定義するためには、キーからハッシュコードを計算する関数と、2つのキーを直接比較する関数の両方が必要です。

Function: define-hash-table-test name test-fn hash-fn

この関数はnameという名前の新たなハッシュテーブルテストを定義します。

この方法でnameを定義した後は、make-hash-tableの引数testにこれを使用することができる。これを行なう際は、そのハッシュテーブルのキー値の比較にtest-fn、キー値からハッシュコードを計算するためにhash-fnを使用することになる。

関数test-fnは2つの引数(2つのキー)をとり、それらが同一と判断されたときは非nilをリターンする。

関数hash-fnは1つの引数(キー)を受け取り、そのキーのハッシュコード(整数)をリターンすること。よい結果を得るために、その関数は負の整数を含む整数の全範囲をハッシュコードに使用するべきある。

指定された関数は、プロパティーhash-table-testの配下の、nameというプロパティーリストに格納される。そのプロパティーの値形式は(test-fn hash-fn)

Function: sxhash-equal obj

この関数はLispオブジェクトobjのハッシュコードをリターンする。リターン値はobjと、それが指す別のLispオブジェクトの内容を表す整数。

2つのオブジェクトobj1obj2が等しければ(sxhash-equal obj1)(sxhash-equal obj2)は同じ整数になる。

2つのオブジェクトがequalでなければ通常はsxhash-equalがreturnする値は異なるが、常に異なるとは限らない。稀(運次第)にsxhash-equalが同じ結果を与える、2つの異なって見えるオブジェクトに遭遇するかもしれない。

Common Lispに関する注意: Common Lispではこれに似た関数はsxhashと呼ばれる。Emacsは互換性のためにsxhash-equalにたいするエイリアスとしてこの名前を提供している。

Function: sxhash-eq obj

この関数はLispオブジェクトobjにたいするハッシュコードをリターンする。結果はobjの識別値でありコンテンツではない。

2つのオブジェクトobj1obj2eqなら(sxhash-eq obj1)(sxhash-eq obj2)は同じ整数。

Function: sxhash-eql obj

この関数はeqlによる比較に適したLispオブジェクトobjにたいするハッシュコードをリターンする。つまり浮動小数点数以外のobjならそれにたいする識別値(浮動小数点数ならその値にたいするハッシュコード)を生成する。

2つのオブジェクトobj1obj2eqlなら(sxhash-eql obj1)(sxhash-eql obj2)は同じ整数。

以下はlcaseを区別しない文字列のキーをもつハッシュテーブルを作成する例です。

(defun case-fold-string= (a b)
  (eq t (compare-strings a nil nil b nil nil t)))
(defun case-fold-string-hash (a)
  (sxhash-equal (upcase a)))

(define-hash-table-test 'case-fold
  'case-fold-string= 'case-fold-string-hash)

(make-hash-table :test 'case-fold)

以下は事前に定義されたテスト値equalと等価なテストを行なうハッシュテーブルを定義できるという例です。キーは任意のLispオブジェクトで、equalに見えるオブジェクトは同じキーと判断されます。

(define-hash-table-test 'contents-hash 'equal 'sxhash-equal)

(make-hash-table :test 'contents-hash)