unladen-swallowのissue を見て、ちょっと気になったので、昨今のハッシュ関数の事情を調べていたのですが、 一言でいうと、難しい、です。
Pythonのハッシュ関数は、今でも FNV っぽいアルゴリズムを用いています。 ただし、実際には独立して開発されていて、たまたま似ているというだけだそうです。
で、 Hash functions: An empirical comparison なんかを見ると、 Murmur2 が汎用的には奨励されていて、 FNVよりも大体速くて、場合によっては衝突も少ないという結果が出ているみたいです。
では、なぜPythonがあいもかわらずFNVっぽいのかというと、 Python 3000のハッシュアルゴリズムの議論 でも見られるように、「ランダムなハッシュ関数は望ましくない（かもしれない）」というのが根拠らしいです。 つまり、似たようなキーがあったとき、ちょっとずつハッシュ値がずれてくれる方が、特にdictが小さいときに、衝突が減少するので、似たようなキーがランダムに散らばるよりも、性能が高いということです。
この辺の議論はなかなか複雑で、ハッシュ関数の特性に求められることとして、
等など、さまざまな要素があげられますが、連想配列に適用する場合、さらに、
等が付け加わります。 逆に、連想配列では、暗号等で求められるような、同じハッシュ値を持つキーが作りにくいという要求はあまり高くありません。 もちろん、DoS問題とかもあるんですが、ここではその問題は無視することにします。
Murmurの問題は、乱数性能が高くて、下位1ビットを変えるだけで、全然違うハッシュ値になってしまうことです。 そうすると、a、b、cみたいな似たようなキーばかりやってくると、 連想配列中で衝突する可能性が高くなります。
しかし、特にdictが大きくなってくると、丸めて衝突する確率が下がるので、問題はむしろクラスタリングが発生することです。 クラスタリングとは、連想配列に含まれる要素が局所的に集まってしまって、衝突が増大し、かつ、使われないバケットが増えてしまう状態です。 これを避けるには、元のハッシュ値がうまく散らばってくれないといけません。
ですから、この種の問題は常に使い方や目的に依存していて、 何を重視し、何を軽視するかというバランスの取り方の問題になります。 CPythonはdict使いまくりの処理系であるため、 小さいdictが大量に発生しやすく、そこに最適化しています。
ですが、だからといって、本当に現状のままが最善なのか、簡単にはわかりません。 Murmurでランダムな値になって発生する衝突率の増大が、 Murmurの高速動作と比べてどうなのか、 dictが大きくなった時の衝突率の増大によって、 その利点が帳消になっていないのか、 こういうことをちゃんと調べてみないとわからないわけです。
自分で調べるのは面倒くさかったので、 とりあえず他がどうしているのか知りたくて、 Rubyを覗いてみることにしました。
最近のRubyはすでにMurmurを使ってます。 これは レポジトリを眺めて、すぐにわかりました。 ですが、ここからはわからないことだらけです。 最初のコミット を見ても、そうしたとしか書いていなくて、どうしてそうしたかったのかが書かれていません。 成瀬さんが提案されている にもかかわらず、古い方のマジックナンバーが使われていたり、 その方がよいからそうしているのか、ただ変更していないだけなのか、 最近Rubyの開発を全く追いかけていない私にはよくわかりませんでした。
なので、RubyからわかったことはMurmurを使っている、そのことだけでした。 Pythonでもそれほど定量的な解析がなされているわけでもなさそうだったので、 五十歩百歩なんですが、 せっかく覗いたのに情報が得られなかったのはちょっと残念です。
もっとも、RubyとPythonではかなり事情が違うので、 仮にわかったとしても、そのままPythonに当てはまるわけでもありません。 RubyのArrayは（自分の記憶では）chainingを使っているはずですし、 Pythonのdictはopenですから、衝突のコストや分布に求められる特性も自ずと違うものになるでしょう。 また、Pythonは32-bitのハッシュ値をopen arrayに押し込んで、 文字列比較をできるだけサボろうとしていますので、 元のハッシュ値が32-bit空間でどれだけうまく散らばっているかが、 かなり重要です（Rubyがここんところをどうしていたかは全然覚えてません）。
自分で少し実験してみてもいいんですが、 最初やりかったことから、またかなり脱線してしまっているので、 誰かがやってくれることを期待して、 止めておきたいと思います。