RubyにおけるHashの実装を詳しく：（前編）#hashと#eql?とActiveSupport::HashWithIndifferentAccess

morimorihogeです．バシクルしてるけど浜風まだ出ない．0.5%とかまじか・・・．春イベ前には欲しいなあ．

Crafting Rails 4 Applications読み会の中で，第三回にHashに関する議論がありました．
その中ではhash[['hoge', 'huga']]やhash[{a: 'hoge', b: 'huga'}]よりもhash['hoge']['huga']が早いよ，という話題が出てきて，その原因はHashの探索方法が要因にあるぜ，みたいな話で終わったのですが，個人的にもうちょっと気になったので深く調べてみました．
元々はOrdered Hashについて詳しく書くつもりだったのですが，書いているうちに長くなってしまったので前後編に分けて，前半はHashの探索の話，後半にOrdered Hashの話を書こうと思います．

RubyにおけるHashの基本

※ハッシュとは何かという話は省略します．また，単にハッシュというとハッシュ関数とハッシュテーブルの話が混在してしまいますが，ここではRubyの定義に従いハッシュテーブルのことをHashと称します

RubyにおけるHashの実装では，ハッシュキーを求める関数はObject#hashです．また，この関数はObject#eql?とセットで更新する指定がされており，「hoge.eql? hugaがtrueのとき，hogeとhugaはハッシュキーとして同値である」と判定されます．
ここで大事なのは「同値」であって「同じオブジェクト」ではない点です．

調べてみましょう．ちなみに同じオブジェクトかどうかを調べるメソッドはObject#equal?です．

pry(main)> hoge_1 = 'hoge'
pry(main)> hoge_2 = 'hoge'
pry(main)> hoge_1.hash
=> -4151845462648794472
pry(main)> hoge_2.hash
=> -4151845462648794472
pry(main)> hoge_1.eql? hoge_2
=> true
pry(main)> hoge_1.equal? hoge_2
=> false

上記の様に，RubyのStringオブジェクトは文字列リテラルで呼び出す度に新しいオブジェクトが作成されるので，同一文字列でもオブジェクトIDはリテラルを呼び出すごとに異なるものになります．
Object#object_idを使うとその辺の様子がよく分かります．

pry(main)> 'hoge'.object_id
=> 70324223417240
pry(main)> 'hoge'.object_id
=> 70324223529920
pry(main)> 'hoge'.object_id
=> 70324202438220

一方，Symbolは最初に呼び出されたタイミングでオブジェクトの生成を行った後は，同一Symbol名であれば同一オブジェクトを返します．Singletonですね．

pry(main)> :hoge.object_id
=> 2172328
pry(main)> :hoge.object_id
=> 2172328
pry(main)> :hoge.object_id
=> 2172328

オブジェクトの生成がされない分，Symbolは余計なメモリを使わないということがよく分かりますね．うんうん．

Symbolと文字列の#hash

と，ここでSymbolの#hashと文字列の#hashが同じものを返すのか，調べてみましょう．

pry(main)> 'hoge'.hash
=> -4151845462648794472
pry(main)> :hoge.hash
=> 4192888994621530309
pry(main)> 'hoge'.to_sym.hash
=> 4192888994621530309
pry(main)> :hoge.to_s.hash
=> -4151845462648794472

というわけで，同一の文字列を元にしたSymbolと文字列オブジェクトであっても，クラスが異なれば異なる#hashが返ることが分かりました．

Railsなんかでデータを格納するときに，hoge[:foo] = 'piyo'がhoge["foo"]で参照できないのはこれが理由ですね．
ダメ押しで確認してみましょう．

pry(main)> class Symbol
pry(main)*   def hash
pry(main)*     self.to_s.hash
pry(main)*   end
pry(main)* end
pry(main)> 'hoge'.hash
=> -4151845462648794472
pry(main)> :hoge.hash
=> -4151845462648794472
pry(main)> 'hoge'.to_sym.hash
=> -4151845462648794472
pry(main)> :hoge.to_s.hash
=> -4151845462648794472

おっしゃ，これならSymbolとString，どっちをKeyにしても同じ結果が返る様にできるんじゃね？ということで，

# symbol_test.rb
hoge_s   = 'hoge'
hoge_sym = :hoge

puts "a_symbol.eql?(a string): #{hoge_sym.eql?(hoge_s)}"

class Symbol
  def hash
    self.to_s.hash
  end

  def eql?(b)
    self.hash == b.hash
  end
end

puts "a_symbol.eql?(a string): #{hoge_sym.eql?(hoge_s)}"

hash_s   = { 'hoge' => true }
hash_sym = { hoge: true }

puts hash_s.inspect
puts "hash_s[String]: #{hash_s[hoge_s]}"
puts "hash_s[Symbol]: #{hash_s[hoge_sym]}"

puts hash_sym.inspect
puts "hash_sym[String]: #{hash_sym[hoge_s]}"
puts "hash_sym[Symbol]: #{hash_sym[hoge_sym]}"

として

$ ruby symbol_test.rb

a_symbol.eql?(a string): false
a_symbol.eql?(a string): true
{"hoge"=>true}
hash_s[String]: true
hash_s[Symbol]: 
{:hoge=>true}
hash_sym[String]: 
hash_sym[Symbol]: true

あれあれ？#hashも#eql?もきちんとオーバーライドされているのに，うまくとれないorz．
ここで詰まってチームメンバーにも色々聞いてみたところ，

Ruby 2.1.0 リファレンスマニュアル: instance method Object#hash

ただし、Fixnum, Symbol, String だけは組込みのハッシュ関数が使用されます(これを変えることはできません)。

(　ﾟдﾟ) ・・・

(つд⊂)ｺﾞｼｺﾞｼ

ただし、Fixnum, Symbol, String だけは組込みのハッシュ関数が使用されます(これを変えることはできません)。

｡･ﾟ･(ﾉД`)

というオチでした．どうやら，#hash，#eql?の単体呼び出しではオーバーライドしたメソッドが呼ばれるのですが，hash key lookupでは組み込み関数が強制的に使われてしまう様です．

ActiveSupport::HashWithIndifferentAccess

しかしここでbabaさんよりActiveSupport::HashWithIndifferentAccessを教えてもらい，以下の様にしたところ，

# symbol_test.rbの末尾に追記する
require 'active_support/all'

hash_s = hash_s.with_indifferent_access
puts "hash_s[String]: #{hash_s[hoge_s]}"
puts "hash_s[Symbol]: #{hash_s[hoge_sym]}"

hash_sym = hash_s.with_indifferent_access
puts "hash_sym[String]: #{hash_sym[hoge_s]}"
puts "hash_sym[Symbol]: #{hash_sym[hoge_sym]}"

hash_s[String]: true
hash_s[Symbol]: true
hash_sym[String]: true
hash_sym[Symbol]: true

というわけで，無事にStringでもSymbolでも取得することができるようになりました．
ちなみにActiveSupport::HashWithIndifferentAccessの中身をちらっとみた感じでは，keyに設定する際，#convert_keyを使ってSymbolをStringに変換して保存するようになっていました．気になる人は読めば分かると思います．

まとめ

というわけで，今回はRubyにおけるHashのデータ格納には#hashがキーとして使われるという話と，ただしFixnum, Symbol, Stringだけは組み込み関数が使われてしまうので思った様にオーバーライドして使えないという話をしました．
後編にはOrdered Hashにまつわるちょっとしたハマりどころを紹介しようと思います．

・・・と思ったら，babaさんからHash#rehashについても言及すべきとの指摘を受けたので，次回は中編としてそのあたりを書いてみようと思います．

ではでは．検証に付き合ってくれたチームメンバーの皆さま，ありがとうございました！