11 ハッシュ表

ハッシュ表は、“値”に“キー”をマップするデータ構造である。 キーと値は任意のLispデータオブジェクトであってよい。ハッシュ表は、 与えられたキーを検索する時間がほぼ一定だという特性を持つ; より単純な 連想リストのようなデータ構造は、リスト中のエントリ数に比例する 時間がかかる。

Function: make-hash-table &key :test :size

この関数は、その要素比較用の関数が:test(既定ではeql) であり、およそ:sizeの要素に合うように割り当てられたハッシュ表 オブジェクトを作成して戻す。:size引数は、単に助言を 与えるものである; より多くの要素を格納する場合、表は自動的に 大きくなる。:sizeが省略された場合、手頃な既定値が使われる。

Common Lispは、eqとeql、equal、equalp だけを:test引数の正しい値として許す。このパッケージでは、 すべての適当な述語関数が動作するが、何か他のものを使う場合、あなたの 述語に適切なことを確実にするために、以下に記述するハッシュ関数の詳細を チェックすべきである。

(Lucid Emacs 19のような)Emacsのある版は、組み込みのハッシュ表型を 含む; これらの版では、eqのテストを伴うmake-hash-table がこれらの組み込みのハッシュ表を使う。他のすべての場合では、先頭に 識別用の“タグ”シンボルを伴うリストのフォームを取る ハッシュテーブルオブジェクトを戻す。このパッケージのすべての ハッシュ表関数は、両方のハッシュ表の型に作用できる; 通常は、どちらの 型が使われているかを知ることは決してないだろう。

この関数は、付加的なCommon Lispキーワード:rehash-sizeと :rehash-thresholdを受け入れるが、その値は無視する。

Function: gethash key table &optional default

この関数は、tableの中でkeyを調べる。もし、表のテスト関数に 従って、存在するキーのいずれかにマッチするという意味で、keyが 表に存在する場合、関連づけられた値が戻される。そうでなければ、 default(またはnil)が戻される。

ハッシュ表に新しいデータを格納するためには、gethashへの 呼び出しにsetfを使う。keyがすでに表に存在する場合、 対応する値は格納する値へ変更される。keyがまだ存在しない場合、 新たなエントリが表へ加えられ、必要ならば表はより大きなサイズへ 再割り当てされる。default引数は許されるが、この場合は 無視される。この状況は、get*のそれと正確に同じである; see 属性リスト.

Function: remhash key table

この関数は、tableからkeyのためのエントリを取り除く。 エントリが取り除かれた場合、tを戻す。keyがテーブルに 現れない場合、何も行なわずnilを戻す。

Function: clrhash table

この関数は、tableからすべてのエントリを取り除き、空のハッシュ表 のままにしておく。

Function: maphash function table

この関数は、tableの各エントリに対してfunctionを呼び出す。 それはfunctionへ2つの引数、与えられたエントリのキーと値を渡す。 functionの戻り値は無視される; maphash自身はnilを 戻す。ハッシュ表上で繰り返す代替の方法は、See ループ機能.

Function: hash-table-count table

この関数は、table内のエントリ数を戻す。警告: Lucid Emacs 19のハッシュ表の現在の実装は、remhashがエントリを 取り除いたときに、格納されたcountを減らさない。従ってこの関数の 戻り値は、表でremhashを使い、かつ表のテストがeqの場合、 信頼できない。エントリを数えるためのより遅いけれども信頼できる方法は、 (loop for x being the hash-keys of table count t)である。

Function: hash-table-p object

この関数は、objectがハッシュ表の場合にtを、さもなければ nilを戻す。これはハッシュ表の両方の型(Lucid Emacs組み込みの表と 特殊なリストで実装された表の両方)を認識する。

ハッシュ表を扱うときには、使われる“ハッシュ関数”を正確に知ることが 有用である場合がある。このパッケージは、Emacs Lispの“obarray”を 使ってハッシュ表を実装する。“obarray”は、Emacs Lispがシンボルの 後をたどるために使うのと同じデータ構造である。それぞれのハッシュ表は、 埋め込まれたobarrayを含む。gethashへ与えられるキーの値は、 さまざまな手段で文字列へ変換され、それからinternや intern-softを使ってobarrayの中を調べられる。与えられたキー 文字列に対応するシンボルまたは“bucket”は、そのsymbol-value として、その文字列へハッシュしたすべてのキーと値の対の連想リストを 含む。テスト関数によっては、多くのエントリを同じbucketへ ハッシュすることも可能である。たとえばテストがeqlの場合、 シンボルfooと2つの別々に組み立てられた文字列"foo"は、 同じbucketに3つのエントリを作るだろう。検索時間はbucket内で 線形なので、あまりに多くのものを同じハッシュに格納しないように準備する 場合に、ハッシュ表は最も効果的だろう。

下記のアルゴリズムが、Lispオブジェクトをハッシュ文字列へ変換するために 使われる:

• 文字列は、直接ハッシュ文字列として使われる(しかしテスト関数が equalpの場合、文字列はまずdowncaseされる)。
• シンボルは、そのsymbol-nameにしたがってハッシュされる。
• 整数は、その値を16で割った余りによって、16のbucketの1つに ハッシュされる。浮動小数点数は、整数に切り捨てられて、16で割った 余りによってハッシュされる。
• コンスセルは、そのcarにしたがってハッシュされる; 空ではない ベクタは、その第1要素にしたがってハッシュされる。
• すべての他のオブジェクトの型は、"*"と名付けられた1つのbucketへ ハッシュする。

したがって、たとえばハッシュ表の中の多くのバッファオブジェクトを 検索することは、1つのbucketを通した(なおかなり速い)線形時間の検索へ 帰するだろう。ところが、異なったシンボルを検索することは、各シンボルは 一般にはそれ自身のbucketへハッシュするので、とても速いだろう。

ハッシュテーブルの中のobarrayの大きさは、要素の数が増えるにつれて 自動的に調節される。

特別な場合として、0または1の:size引数を伴う make-hash-tableは、多くのリストのobarrayではなく、1つの 連想リストを使うハッシュ表オブジェクトを作る。とても小さい 表のためには、調査がキーから文字列への変換またはobarrayの中の調査を 必要としないので、この構造はより効率的である。しかしこのような表は、 検索をするためにはその大きさに比例する時間がかかることが保証される。