Emacs Lisp Hash-Table C

Super Technique 講座
http://www.nurs.or.jp/~sug/soft/super/hash.htm を参考にしたら、
Elisp の Hash-Table も読めそうな気になってきたのでメモしていく。

Elisp の gethash は src/fns.c で定義されている。
ハッシュテーブルなので、任意のキーからハッシュ値を生成している部分があるはず。
コメントを付けてみる。

DEFUN ("gethash", Fgethash, Sgethash, 2, 3, 0,
       doc: /* Look up KEY in TABLE and return its associated value.
If KEY is not found, return DFLT which defaults to nil.  */)
     (key, table, dflt)
     Lisp_Object key, table, dflt;
{
  /* Lisp Object がハッシュテーブルか確認して *h に設定 */
  struct Lisp_Hash_Table *h = check_hash_table (table);
  /* ハッシュ値を取得 */
  int i = hash_lookup (h, key, NULL);
  /* ヒットすれば値を、そうでなければ gethash の第３引数のデフォルト値を返す。*/
  return i >= 0 ? HASH_VALUE (h, i) : dflt;
}

puthash の方も見ると、やっぱり hash_lookup を呼んでいる。

src/fns.c を良く眺めてみると、 Hash Code Computation という部分があった。
怪しげなマジックナンバーが埋め込まれているので、
sxhash_string なる C の関数がハッシュ値を生成しているようだ。

勘が悪いことだが、ようやくElisp 側にも sxhash という関数があることに気づいた。
これがまず探していた、ハッシュ関数だ。

DEFUN ("sxhash", Fsxhash, Ssxhash, 1, 1, 0,
       doc: /* Compute a hash code for OBJ and return it as integer.  */)
     (obj)
     Lisp_Object obj;
{
  unsigned hash = sxhash (obj, 0);;
  return make_number (hash);
}

本体は sxhash なる C 関数。任意の Lisp オブジェクトに対して、うまいことハッシュ値を計算しているだろうか？
型によって、sxhash_list とか sxhash_string を使い分けている。
list の場合は SXHASH_MAX_DEPTH より深くはたどらないようになっている。

HASH_VALUE は C のマクロで、ここで 「Lisp の配列」（※まだ実体がつかめていないが、
添字で高速にアクセスする対象。）から値を取り出しているらしい。

続く。