次へ: その他のハッシュテーブル関数, 前へ: ハッシュテーブルへのアクセス, 上へ: ハッシュテーブル   [目次][索引]

8.3 ハッシュ比較の定義 ¶

define-hash-table-test を使用して、キー検索の新しいメソッドを定義できます。この機能を利用するには、ハッシュテーブルの仕組みと、ハッシュコード の意味を理解しておく必要があります。

ハッシュテーブルは、概念的には、それぞれが1つの関連付けを保持できる多数のスロットからなる大きな配列と考えることができます。キーを検索する際、gethashはまずキーから整数（ハッシュコード）を算出します。この整数を配列の長さで割った余りを求めることで、配列内のインデックスを導き出します。その後、そのスロット、および必要に応じて周辺の他のスロットを調べ、目的のキーが見つかったかどうかを確認します。

したがって、新しいキー検索手法を定義するには、キーからハッシュコードを計算する関数と、2つのキーを直接比較する関数の両方を指定する必要があります。これら2つの関数は互いに整合している必要があります。つまり、2つのキーが等しいと判定される場合、それらのハッシュコードも同一である必要があります。また、これら2つの関数は（ガベージコレクタなどによって）いつでも呼び出される可能性があるため、副作用がなく、迅速に処理を完了し、その動作は変更されないキーのプロパティのみに依存する必要があります。

関数: define-hash-table-test name test-fn hash-fn ¶

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

このように name を定義すると、それを make-hash-table の test 引数として使用できます。その際、ハッシュテーブルは test-fn をキー値の比較に、hash-fn をキー値からのハッシュコードの算出に使用します。

関数 test-fn は2つの引数（2つのキー）を受け取り、それらが同一とみなされる場合は non-nil を返す必要があります。

関数 hash-fn は、キーを1つの引数として受け取り、そのキーのハッシュコードとなる整数を返す必要があります。良好な結果を得るため、この関数は負の fixnum を含む fixnum の全範囲をハッシュコードとして使用すべきです。

指定された関数は、name のプロパティリスト内のプロパティ hash-table-test に格納されており、プロパティ値の形式は (test-fn hash-fn) です。

関数: sxhash-equal obj ¶

この関数は、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の互換性のためのエイリアスとしてこの名称を提供しています。

関数: sxhash-eq obj ¶

この関数は、Lispオブジェクト obj のハッシュコードを返します。その結果は obj の同一性を反映しますが、その内容は反映しません。

2つのオブジェクト obj1 と obj2 が eq であるならば、(sxhash-eq obj1) と (sxhash-eq obj2) は同じ整数である。

関数: sxhash-eql obj ¶

この関数は、eql での比較に適した Lisp オブジェクト obj のハッシュコードを返します。言い換えれば、obj の同一性を反映しますが、オブジェクトがビッグナンバーまたは浮動小数点数である場合は、その値に対してハッシュコードが生成されます。

2つのオブジェクト obj1 と obj2 が eql であるならば、(sxhash-eql obj1) と (sxhash-eql obj2) は同じ整数である。

この例では、大文字小文字を区別せずに比較される文字列をキーとするハッシュテーブルを作成します。

(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オブジェクトを指定でき、見た目が同一のオブジェクトは同じキーとみなされます。

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

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

Lispプログラムは、Emacsセッション間でハッシュコードが保持されることに依存すべきではありません。ハッシュ関数の実装が、セッション間や異なるアーキテクチャ間で変動し得るオブジェクトストレージの詳細を利用しているためです。