From: Yusuke ENDOH <mame@...>
Date: 2007-09-20T22:58:40+09:00
Subject: [ruby-dev:31802] hash value of { n => n }

遠藤と申します

1.9 で以下のコードを実行すると、かなり時間がかかります。


$ time ./ruby -ve 'h = {}; 10000.times {|x| h[{ x => x }] = 1 }'
ruby 1.9.0 (2007-09-15 patchlevel 0) [i686-linux]

real    0m12.369s
user    0m9.050s
sys     0m3.280s


任意の x について { x => x } のハッシュ値がすべて 1 であるため、
衝突しまくっているようです。
耐衝突性はそれほど重要じゃないかもしれませんが、ちょっと簡単に
衝突しすぎな気もします。どうでしょうか。


上のコードについては以下のパッチでとりあえず解決します。

Index: hash.c
===================================================================
--- hash.c      (revision 13472)
+++ hash.c      (working copy)
@@ -1461,6 +1461,7 @@
 {
     if (key == Qundef) return ST_CONTINUE;
     *hval ^= rb_hash(key);
+    *hval *= 137;
     *hval ^= rb_hash(val);
     return ST_CONTINUE;
 }


$ time ./ruby -ve 'h = {}; 10000.times {|x| h[{ x => x }] = 1 }'
ruby 1.9.0 (2007-09-15 patchlevel 0) [i686-linux]

real    0m0.182s
user    0m0.030s
sys     0m0.150s

--
Yusuke ENDOH <mame@tsg.ne.jp>