[Mew-dist 09772] hash on Emacs (toward threading)

[Kazu Yamamoto ( 山本和彦 )]

あまり知られていないことですが、実は Emacs にはハッシュの機能がありま
す。その名を obarray といい、実体は vector (配列) です。(XEmacs には加
えて、明示的なハッシュがあります。)

使い型

(1) ハッシュテーブルを作る (ハッシュの大きさは素数がよい)
	(setq hash (make-vector 5 0)) -> [0 0 0 0 0]
	;; 0 で初期化するのはお約束

(2.1) キー(文字列)をハッシュに入れるには intern を使う

	(intern "key" hash) -> key
	hash -> [0 0 key 0 0]

(2.2) intern は、キーがある場合は、キー名に対するシンボルを返す。よって、
そのシンボルに値を set できる

	(set (intern "key" hash) "value")

これで、hash に「キー名 ＋ 値」を登録できたことになります。(実は 2.1 
は不要)

(3) キー名に対する値を得たい場合は、intern + symbol-value を使う

	(symbol-value (intern "key" hash)) -> "value"
	
分かりにくいので、実際使うときは、put-hash や get-hash というマクロを
定義すればいいでしょう。この機能を使えば、高速な検索が可能になります。

さて、obarray はまともなハッシュなので、ハッシュ値がぶつかっても平気で
す。実は vector のそれぞれの要素はリストで管理されています。つまり、要
素は同じハッシュ値を持つオブジェクトのリストです。

intern はハッシュ値を計算し、ハッシュ値番目のリストを取り出します。そ
の後は、key が一致するエントリを線形に検索します。

Emacs の変数や関数の値の検索にはこの obarray が利用されています。実際
に obarray という大域変数があるので、評価してみるといいでしょう。この 
obarray の大きさは 1511 に決め打ちされています。

ここで湧く疑問は、Emacs がたくさん .el を読み込むと、衝突が頻繁に起こ
り、線形検索の部分が遅くなるのではないかということです。ソースを見た限
り、ハッシュを動的に大きくするなどの作業はしていないようです。この理解
は正しいでしょうか？

ここから本題ですが、obarray を使うと簡易 DB が作成できるので、thread 
を実装する際に役に立ちます。(Message-ID: に対し、In-Reply-To: を登録す
るなど。)しかし、メッセージの数が大きくなると効率が落ちるんじゃないで
しょうか？ 真剣に探しましたが、ハッシュを大きくする方法はないようです。

後藤さんが obarray で thread を実現していたと思うのですが、
	- ソースは公開していますか？
	- ハッシュの大きさはいくらですか？
	- ハッシュは動的に大きくしていますか？
	- たくさんメッセージを扱うと遅くなりませんか？
などを教えて下さい。

あと、ハッシュに関して深い知識のある方は、ハッシュはどういうときに大き
くすべきか教えてもらえると嬉しいです。

--かず