Rubyのhashメソッドをきちんと実装するとある1つの方法

Ruby

前回のエントリの続き。こんなmoduleを作ってみました。includeするだけでまともなhashが使えるようになります。

module Hashable

  require "digest/sha1"

  def hash
    class_name = self.class.to_s
    hash_str = class_name
    hash_str.concat("={")
    if not defined?(@@hashable_hash_use_vars) then
      @@hashable_hash_use_vars = hash_use_instance_vars()
    end
    @@hashable_hash_use_vars.each_with_index do |var_name_symbol, i|
      hash_str.concat(",") if 0 < i
      hash_str.concat(var_name_symbol.to_s)
      hash_str.concat("=")
      hash_str.concat(self.instance_variable_get(var_name_symbol).to_s)
    end
    hash_str.concat("}")

    if not defined?(@@hashable_hash_xor_num) then
      digest = Digest::SHA1.digest(class_name)
      digest_first64bit = digest[0, 64/8]
      @@hashable_hash_xor_num = digest_first64bit.unpack("Q").first # extract unsigned 64bit Fixnum
    end

    return @@hashable_hash_xor_num ^ hash_str.hash
  end

  def eql?(obj)
    return false if !obj.kind_of?(self.class)
    obj_vars = {}
    obj.instance_eval do
      hash_use_instance_vars().each do |sym|
        obj_vars[sym] = self.instance_variable_get(sym)
      end
    end
    my_ivars = hash_use_instance_vars()

    return false if obj_vars.keys.sort != my_ivars.sort

    obj_vars.each do |sym, val|
      return false if val != self.instance_variable_get(sym)
    end

    return true
  end


  private

  def hash_use_instance_vars
    self.instance_variables
  end

end

コードはパフォーマンスを少しでもよくするため冗長になってます。簡潔にするとかわりに30~35%ぐらい遅くなります。Hashableで下のようなシンプルなモデルのhash値を計算した場合、だいたいString#hashと比べて10倍ぐらい遅いです。

基本的なアイディアとしては前回のエントリ(Rubyのhashメソッドをきちんと実装するには?)を踏襲していますが、排他的論理和に使うビットマスクをクラス名をSHA1したものを使って自動化しています。意外と再利用性がありそうだったのでモジュールにしました。

以下のようなパターンの場合、うまく動かないかもしれません。

  • インスタンス変数がまったくない, そもそも等値性関係ないのでこのモジュール使う意味ないですね。。。
  • インスタンス変数がinitialize以外のメソッドで生成される(=初めて代入される)

2点目について補足すると、基本的にリフレクションでインスタンス変数を全部取り出してきているので、等値性に関係ないインスタンス変数があとから増えちゃう場合はそれが考慮されない、という意味です。こういう場合の抜け道もいちおう簡単なものを用意してありまして、hash_use_instance_varsメソッドを以下のようにオーバーライドするとよいです。(別の要求として、あとからインスタンス変数が増えるのもhash値に織り込んで計算させたい場合は@@hashable_hash_use_varsクラス変数へのキャッシュを外してもいいかもしれません。)

# @a, @bに基づいて等値性を判断するのだけど@hogeが邪魔をしてしまうのを回避
class Hoge
  
  include Hashable

  attr_accessor :a
  attr_accessor :b
  
  def initialize(a, b)
    @a, @b = a, b
  end
  
  def hoge
    @hoge = "hoge"
    puts @hoge
  end
  
  private
  
  def hash_use_instance_vars
    [:@a, :@b]
  end
  
end

ちなみにこのHashableの実装はString#hashに依存しているのですが、String#hashは同じ文字列に対しても、同じrubyプロセス内では何回評価しても同じ値ですが、コマンドを複数回実行すると毎回違う値が出てきます。従って、まずありえないとは思いますがString#hashの出力や、Hashableのhashを使って求めたハッシュ値を永続化して、同一でないプロセス上で他のインスタンスのハッシュ値と比較したりすると変なことになるはずです。


あわせて読みたい：

追記：ちらばり具合に関する定量的評価を取ったのを忘れていました、以下折り畳んで追記


33個のバケットがあるハッシュを想定して、ハッシュ値を33で割った余り(x.hash % 33)の分布を数えたところ、標準偏差は100万インスタンスで0.6%程度でしたので、かなり普通にちらばっており、偏ってはいないものと思われます。String#hashも調べてみたところ同様でした。

↓実験したコード

class Hoge

  include Hashable

  def initialize(x, y)
    @x, @y = x, y
  end

end

def mean(v)
  v.inject(0){|r,n| r+n }.to_f / v.size
end

def stddev(v)
  v_mean = mean(v)
  Math.sqrt( v.map{|n| (n-v_mean)**2 }.inject(0){|r,n| r+n }.to_f / (v.size - 1) )
end

times = 100_0000
backet_size = 33
hoge_hashes = [0] * backet_size
str_hashes = [0] * backet_size
puts Benchmark::CAPTION
puts Benchmark.measure{
  times.times do |i|
    h = "hogehoge#{i}".hash
    str_hashes[h % backet_size] += 1
  end
}
puts Benchmark.measure{
  times.times do
    x = rand(100_0000)
    y = rand(100_0000)
    hoge_instance = Hoge.new(x, y)
    hi_hash = hoge_instance.hash
    hoge_hashes[hi_hash % backet_size] += 1
  end
}

str_stddev_result = stddev(str_hashes)
str_percent = str_stddev_result / (times.to_f / backet_size) * 100.0
puts "String: stddev=#{str_stddev_result} (#{str_percent}%)"

stddev_result = stddev(hoge_hashes)
percent = stddev_result / (times.to_f/backet_size) * 100.0
puts "Hashble+Hoge: stddev=#{stddev_result} (#{percent}%)"