#:g1: ハッシュテーブルのキーとしてリストを使う

Posted 2019-09-30 19:51:28 GMT

こちらのエントリーを読んでいて、本筋とはちょっと関係ないのですが、リストに対してのsxhashの返り値が特定の長さからは同じ値を返すということについて興味を持ったので手元の処理系で調べてみました。

調べるのに使ったコードは、下記のようなものです

(loop :for i :from 0 :when (= (sxhash (make-list i)) (sxhash '#0=(nil . #0#))) :return i)

各処理系でリストの sxhash のハッシュ値が区別できなくなる地点

処理系 区別できなくなる地点
LispWorks 7.1.2 14以降
Allegro CL 10.1 14以降
Lucid CL 4.1 9以降
CCL 1.11.5 7以降
CMUCL 21d 7以降
CMUCL 17f 7以降
SBCL 1.5.7 5以降
AKCL 1.619 4以降
GCL 4以降
ECL 3以降
MkCL 3以降

興味本位で、CADR system 78のLisp Machine Lisp(Common Lispの祖先)で試してみたところ、sxhashはどんな長さでも諦めないで計算してくれるようです。
また、循環リストを与えると停止しません。

Lisp Machine Lispと違って、Common Lispで上記のように特定の長さでハッシュ値の計算を打ち切ってしまうのは、sxhashが循環構造のオブジェクトについても停止することが要求されているからでしょう。

それにしても、ECLあたりは3つ目以降は区別できないのでリストをキーとして使うのは難しそうです。

まとめ

リストをハッシュテーブルのキーにしたいことは個人的にはこれまで無かったのですが、リストがキーになっているのを目にしない理由もなんとなく分かった気がします。


HTML generated by 3bmd in LispWorks 7.1.2

comments powered by Disqus