あるキーに対応する値を取り出す方法にはいくつかあるが、 Emacs Lisp でよく利用されているのは「連想リスト」である。 連想リストは、以下のように「ドット対」のリストである。
(setq alist '(("rose" . red) ("violet" . blue)))
連想リストを検索するには、assoc や assq を用いる。 この例ではキーが文字列なので、assoc を使う。
(assoc "rose" alist)
→ ("rose" . red)
assoc は、組み込み関数なので高速であるが、 それでも検索のオーダは O(n) である。
検索のオーダが O(1) である方法としてハッシュが知られている。 Emacs 21 にはハッシュがあるので、何も言うことはない。 Emacs 20 ではハッシュは提供されていないが、 シンボル表を利用することでハッシュを実現できる。 以下では、この方法について述べる。
シンボル表とは、シンボル名を登録する配列のことである。 配列の各要素の初期値は 0 にする必要がある。 そして、ハッシュの検索性能に大きな影響を及ぼす配列の大きさは、 素数にすることが望ましい。
以下の例では、配列の大きさとして素数 3 を選んでいる。
(setq vec (make-vector 3 0))
次にこの配列にシンボル名を登録する。 それには、intern という関数を使う。 (この行為を Emacs Lisp では、 シンボルを obarray に intern すると表現するから何が何だか分らない。 シンボル名をシンボル表に登録すると分りやすく表現されていれば、 このページを書くこともなかっただろう。)
(intern "rose" vec) → rose vec → [0 rose 0]
"rose" が配列に登録されたのが分るだろう。 キーは登録できたが、対応する値は格納されていないので、 これだけでは役に立たない。 値は、intern が返すシンボルの変数の値として束縛する。
(set (intern "rose" vec) 'red) (set (intern "violet" vec) 'blue)
intern は、配列にシンボル名を問答無用に登録する。 だから検索には利用できない。 検索には、intern-soft という関数を利用する。 この関数は、配列にシンボル名が登録されているときに限り、 その検索したシンボルを返す。
(let ((sym (intern-soft "rose" vec))) (if sym (symbol-value sym))) → red
ここまでで使い方は理解できたと思うが、一体どうしてこの方法が高速なのだろう？
Emacs の intern の実装は以下のようにハッシュ値を計算する。 (XEmacs では異なる計算方法を採用している。)
hash_string (ptr, len)
char *ptr;
int len;
{
unsigned char *p = ptr;
unsigned char *end = p + len;
unsigned char c;
int hash = 0;
while (p != end)
{
c = *p++;
if (c >= 0140) c -= 40;
hash = ((hash<<3) + (hash>>28) + c);
}
return hash & 07777777777;
}
ptr はシンボル名へのポインタ、len はシンボル名への長さである。 hash_string が返す値は、 配列の大きさで割って余りを取り、 それを配列のインデックスとして使う。 すなわち、シンボル名から配列のインデックスを単純に計算するので、 O(1) となるわけだ。 配列の大きさに素数を使うのは、 余りが散らばるようにするためである。
hash_string が返す値は、当然衝突する可能性がある。 この場合、普通のハッシュの実装と同様に、 同じハッシュ値を持つシンボル名はリストとして管理される。
以下の例では、"rose" と "lily" のハッシュ値が、 両方 1 になったことが分る。
(setq vec (make-vector 3 0)) (set (intern "rose" vec) 'red) (set (intern "violet" vec) 'blue) → [0 rose violet] (set (intern "lily" vec) 'white) → [0 lily violet]
しかし以下のように、 "rose" も "lily" も両方ちゃんと登録されているから安心しよう。
(symbol-value (intern-soft "rose" vec)) → red (symbol-value (intern-soft "lily" vec)) → white