7.3 Defining Hash Comparisons

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

概念的にはハッシュテーブルを、1つの連想を保持できるスロットがたくさんある巨大な配列として考えることができます。キーを照合するには、まずgethashが、キーから整数のハッシュコード(hash code)を計算します。配列内のインデックスを生成するために、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をreturnします。

関数hash-fnは1つの引数(キー)をとり、そのキーの“ハッシュコード”(整数)をreturnします。よい結果を得るために、この関数は負の整数を含む整数の全範囲を、ハッシュコードに使用するべきです。

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

Function: sxhash obj

この関数は、Lispオブジェクトobjにたいするハッシュコードをreturnします。return値は、objと、それが指す別のLispオブジェクトの内容を表す整数です。

2つのオブジェクトobj1とobj2がequalの場合、(sxhash obj1)と(sxhash obj2)は同じ整数になります。

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

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

(defun case-fold-string= (a b)
  (eq t (compare-strings a nil nil b nil nil t)))
(defun case-fold-string-hash (a)
  (sxhash (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)

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