hashtableのn * 2 + 1の意義

勇士Ｑ @ucq

@a4lg ああ、なるほど。そういわれてみるとそんな理由なのかも。

Tsukasa #01 @a4lg

@ucq でも素数になることが大事なら、1 か 7 以降のメルセンヌ素数から始めて、4n+3 にした方がメルセンヌ素数に当たる確率が高くなるのね…。2^n-1 の形のメルセンヌ数は、少なくとも n が合成数の場合は合成数になるから。

勇士Ｑ @ucq

@a4lg うーむ、計算速度的にも4n+3でもあまり遅くならない(と思う)ことをかんがえると、別の理由なのかなぁ

二階堂ちむら @thimura

@kumagi ハッシュテーブルのサイズは素数か、合成数でも因数が少ない方が良いと信じられてるらしい。乱数列作ってるわけじゃないから合成数でも問題は無いと思うのだけど… http://bit.ly/h35xaf

くまぎ @kumagi

@thimura 素数だと良く散るという状態がピンと来ないですが、そもそもハッシュ関数が理想的に散ってくれるなら要らない工夫なんじゃないかという疑惑が濃厚です。

くまぎ @kumagi

バイナリアンたちの会話がレベル高い…！

二階堂ちむら @thimura

@kumagi あーでも、Ruby の Fixnum とかだと hash が必ず奇数になるので、2の倍数をテーブルサイズにしてるとテーブルの半分しか使わなくなりますね…。Object.hashCode の実装がどうなってるか知りませんが、アドレスを元に生成してるとマズいのかも

非実在naka aki @naka_aki_spl

@kumagi たしかハッシュって原理的に半端なサイズのほうが検索ヒット率（ひいてはスピード）が上がるんじゃなかったかな。半端なほうがよりよくシャッフルできる。シャッフルがうまくいかなくて偏るとハッシュの旨味が減る。単純2倍だと必ず2で割れる。複数回やれば2^Nの「弱点」が積もる

くまぎ @kumagi

@naka_aki_spl ハッシュ結果が満遍なく散らない限りは仰る通りだと思います。