Rubyのhashメソッドをきちんと実装するには?

Ruby

データ構造のハッシュテーブルにキーとしてオブジェクトが利用されることを想定する場合、同値性を確かめるeql?メソッドと、同じ値のオブジェクトに対して実行すると同じ値のFixnumを返すhashメソッドを実装する必要があります。

これを実装しておかないと、Object#hashがそのまま利用され、自分で独自に定義したオブジェクトをHashのキーに使うとバグってしまいます。

eql?は同値性を確かめることができればよいので、割と簡単に実装できるはずです。

このエントリで議論したいのは、hashメソッドのちゃんとした実装方法です。

僕は

class Hoge
  def hash
    return "#{self.class}hogehoge#{@var1}#{@var2}".hash
  end
end

といった実装をやっつけですることがあるのですが、これでは同じ内容のStringと衝突してしまうのがよくないはずです。(同じHashにStringオブジェクトをキーとして混在させなければ問題ないですし、そもそも動作がおかしくなるのではなくハッシュ内で探索に時間がかかってしまうという程度の「よくない」)

またHashのキーとして使われるので値がばらけるような計算結果にならないとまずいです。(hashの結果を10で割ったあまりが常に3とかだとまずい, 詳しくはハッシュテーブルのアルゴリズムを参照)

ちょっと考えてみましたが、String#hashが返す結果がほどよくばらけているのであれば、これに対して一定のビットマスクを排他的論理和すればいいような気がしました。ビットマスクはクラスごとにランダムに作ればいいという。

unsigned 32bitなビットマスクを得るにはrand(2<<32-1)をirbでたたけばよさそうです。

$ irb 
ruby-1.9.2-p0 > rand( 2<<32-1 )
 => 3428158691

ここで出てきた3428158691を採用してみることにします。

class Hoge
  def hash
    return (3428158691 ^ "#{self.class}hogehoge#{@var1}#{@var2}".hash)
  end
end

どうでしょう。いいような気がしていますが、きちんとバラけた数値が出ているのかどうか、今度検証してみたいです。JavaでもObject#hashCodeの実装で同じことが言えるので、気をつけてプログラミングしたいところですね。