確かに素数で剰余を取ることにあまり意味は感じないかなあと.素数で剰余を取ることでばらけさせるのではなく,ハッシュ関数そのものの方でばらけさせるべきではと.
他の言語ではどうだろと思って調べてみると,以下の言語は2^nになっているっぽい.ディスク上に残っていたソースを読んだだけなので,バージョンによって違うかもしれないけど.
あと,以下の部分が本当にKnuth先生が言っているのか気になって,「The Art of Computer Programming」の6.4 Hashingの辺りを斜め読みしてみたのだが,特に見当たらないかなあ.
http://www.azillionmonkeys.com/qed/hash.html
My boss advocated simply performing a modulo by prime operation and cited Knuth’s 30 years old “the Art of Computer Programming”. I showed him examples where modulo by prime had extremely bad collisions, but this did not seem to sway him at all. It seems Knuth’s rewrites have come too late.
Hash Functions: the modulo prime myth? – Codexon
こっちの除算法のようにハッシュ関数そのものをテーブルのサイズの剰余を計算することで実装するという場合は,テーブルサイズを素数にすべきだとは書いてあるのだけども,一般的なハッシュテーブルのサイズについては特に言及していないような.