ツイッターで「Ruby の Hash のキーにするオブジェクトに hash と eql? を定義しないといけないのなんでなんだろう」という話題が出て、「おそらく Hash の名前の通り、Hash テーブルを lookup するのにキーの hash 値を計算するのに使ってるんだろうね」という話になったのだけれど、「じゃあhash.c 読んでみようぜ」って感じになって、一部読んだ。2.0.0-p0のコードです。

(一部markdownが注釈と解釈されておかしなことになってるの防ぐためにスペースを余分に入れてある)

まずは、Hash#[ ] の実装がどこにあるのか見る。

hash.c の 3448 行目見るとわかる。

rb_define_method(rb_cHash,"[ ]", rb_hash_aref, 1);

Hash#[ ] の実体は rb_hash_aref というCの関数である。じゃあそこを見る。hash.c の L560から。

VALUE
rb_hash_aref(VALUE hash, VALUE key)
{
    st_data_t val;

    if (!RHASH(hash)->ntbl || !st_lookup(RHASH(hash)->ntbl, key, &val)) {
        return hash_default_value(hash, key);
    }
    return (VALUE)val;
}

VALUEってのはRubyの世界のオブジェクトを表すっぽい。RHASHは、Rubyの世界のオブジェクトをCの世界の構造体に変換するマクロっぽい。じゃあCの世界の構造体がどこに定義されるかっていうと、include/ruby.h の L921

struct RHash {
    struct RBasic basic;
    struct st_table *ntbl;      /* possibly 0 */
    int iter_lev;
    VALUE ifnone;
};

たしかに ntbl っていうメンバーがある。

さっきの rb_hash_aref に話は戻って、引数にhash, keyがある。どちらも VALUE だし、hash は Ruby の世界の Hash オブジェクト、そして key はその key というのが推察できると思う。

if 文のところ。 hashの内部で保持してるテーブルが無いか、あるいはst_lookupの返り値が偽ならばデフォルトの値を返すっぽい。

st_lookupにvalというものをポインタ渡ししている。もし st_lookup でハッシュテーブルのエントリが見つかればそれを val に入れてるんだなってわかると思う。

で、見つかったばあいは valを(VALUE)にして(つまりRubyの世界のオブジェクトにして)返してる。

さて、ここでキモは st_lookup だとわかったので、st_lookup 見る。st.c L409。

int
st_lookup(st_table *table, register st_data_t key, st_data_t *value)
{
    st_index_t hash_val;
    register st_table_entry *ptr;

    hash_val = do_hash(key, table);
    ...

do_hashというところでハッシュ値を求めてるっぽいのが見れる。じゃあdo_hash見る。st.c の L87

#define do_hash(key,table) (st_index_t)(*(table)->type->hash)( ( key ) )

関数ポインタだ。 *(table)->type->hash で得られる関数をkeyを引数に呼び出している。

じゃあ table ってなんだろう。st_lookupの第一引数だ。st_lookupを呼び出してる部分みてみると、これは RHASH(hash)->ntbl であることがわかる。

RHASH(hash)で得られるものは RHash 構造体であった。この構造体に実際に何が入っているかは、初期化してるところを見れば良い。

rb_hash_initialize から rb_hash_modify に飛んで、さらに rb_hash_tbl (hash.c L266)に飛ぶ。ここで以下のようなコードで初期化している。

struct st_table *
rb_hash_tbl(VALUE hash)
{
  if (!RHASH(hash)->ntbl) {
    RHASH(hash)->ntbl = st_init_table(&objhash);
  }
  return RHASH(hash)->ntbl;
}

st_init_tableに objhash を渡している。

st_init_tableを見る(st.c L266)

st_table*
st_init_table(const struct st_hash_type *type)
{
    return st_init_table_with_size(type, 0);
}

st_init_table_with_size 呼んでるだけなので st_init_table_with_size(st.c L229)見る。

st_table*
st_init_table_with_size(const struct st_hash_type *type, st_index_t size)
{
    st_table *tbl;

    (略)

    tbl = st_alloc_table();
    tbl->type = type;
    (略)

    return tbl;
}

ここまで見ると、tbl->type に objhash が渡されているのが見て取れる。

ではobjhashを見る。hash.c L104

static const struct st_hash_type objhash = {
  rb_any_cmp,
  rb_any_hash,
};

st_hash_typeってのが出てきた。読む。(st.h L70)

struct st_hash_type {
    int ( *compare )(ANYARGS /*st_data_t, st_data_t*/); /* st_compare_func* */
    st_index_t ( *hash )(ANYARGS /*st_data_t*/);        /* st_hash_func* */
};

ANYARGSは C 環境だと空文字列に展開される。(include/ruby/defines.h)

ふむ。なるほど。まず、(table)->type が objhashだとわかって、 objhash->hash が rb_any_hash への関数ポインタであることがわかる。

これで、do_hash の中で出てきた *(table)->type->hash の正体が rb_any_hashであることがわかった。あとひといきだ。

rb_any_hash は hash.rb L84

static st_index_t
rb_any_hash(VALUE a)
{
  VALUE hval;
  st_index_t hnum;

  if (SPECIAL_CONST_P(a)) {
    if (a == Qundef) return 0;
    hnum = rb_hash_end(rb_hash_start( (st_index_t)a) );
  }
  else if (BUILTIN_TYPE(a) == T_STRING) {
    hnum = rb_str_hash(a);
  }
  else {
    hval = rb_hash(a);
    hnum = FIX2LONG(hval);
  }
  hnum <<= 1;
  return (st_index_t)RSHIFT(hnum, 1);
}

組み込みでないような型の値 a に対しては、rb_hash(a) でハッシュ値を求めている。では rb_hash を見る。(hash.c L66)

VALUE
rb_hash(VALUE obj)
{
  VALUE hval = rb_funcall(obj, id_hash, 0);
 retry:
  switch (TYPE(hval)) {
  case T_FIXNUM:
    return hval;

  case T_BIGNUM:
    return LONG2FIX(((long*)(RBIGNUM_DIGITS(hval)))[0]);

  default:
    hval = rb_to_int(hval);
    goto retry;
  }
}

rb_funcall で引数に渡されたオブジェクトのhashメソッドを呼んでいる。じゃあここの引数にわたって来ているものはなんだ、って今度は上に辿ってみて行くと、 rb_any_hashに渡されている引数で、それはどこから来ているかというと、

#define do_hash(key,table) (st_index_t)(*(table)->type->hash)( (key) )

ここであった。引数は key である。

というわけで、無事に「なぜ Hash のキーに渡すためのオブジェクトに hash メソッドを定義しなければならないのか」が理解できた。eql? についてはまだ読んでないけど、同じ感じで突き止めていけばわかると思う。

追記 2013 3 29

eql? についても調べた。ここまでちゃんと読んだひとなら普通に読める

st_lookup で呼ばれている find_entry(st.c L381) の中で呼ばれている PTR_NOT_EQUAL の中で呼ばれている EQUAL の中で *(table)->type->compare されており、(table)->type->compare の実体は rb_any_cmp であり、そこで rb_eql が呼ばれている。rb_eql の定義は object.c のL67 、rb_funcall で id_eql がkeyに対して呼ばれている

id_eql = rb_intern("eql?");とされている(object.c L3171)ので、やはりハッシュテーブルの lookup に eql? も使われていることがわかる。

ちなみにこの同値性をどう使っているのかというと、key.hashでハッシュ値を求めハッシュテーブルの slot を確定させ、その slot の中からオブジェクトを取り出すときに、eql? で一致したオブジェクトを取り出すという実装になっている。

猫型の蓄音機は 1 分間に 45 回にゃあと鳴く

Nekogata.rotation_per_minute(45)

CRuby の hash.c を一部読んだ

追記 2013 3 29