「追根溯源」Ruby数组的uniq方法

Published on:
Tags: ruby

昨天,在群(「诱人的Ruby」 QQ学习群号:222359552)里,@赵宇 问了一个问题, 为什么他修改了hash方法和eql?方法,会对uniq方法有影响?

他给出的代码是这样的:

class Item
  attr_reader :item_name, :qty
 
  def initialize(item_name, qty)
    @item_name = item_name
    @qty = qty
  end
 
  def to_s
    "Item (#{@item_name}, #{@qty})"
  end
 
  def hash
    puts "#hash? invoked"
    @item_name.hash ^ @qty.hash
  end

  def eql?(other_item)
    puts "#eql? invoked"
    @item_name == other_item.item_name && @qty == other_item.qty
  end
 
end

p Item.new("abcd", 1).hash
p Item.new("abcd", 1) == Item.new("abcd", 1)

items = [Item.new("abcd", 1), Item.new("abcd", 1), Item.new("abcd", 1)]
p items.uniq

当运行上述代码之后,你会发现, 在Item类里他修改的hash和eql?方法是对items.uniq的结果有了影响。


第一眼看到这个问题,挺不以为然,这不是明摆着的吗,因为Ruby Doc里Array#uniq已经说了, uniq方法会依赖hash和eql?两个方法。

但是@赵宇说,他想知道uniq的内部机制, 于是我把Ruby Doc里显示的uniq方法的源码发在群里,当我发在群里之后,也仔细看了下源码(c代码),才发现,这里并没有调用eql?方法的痕迹, 因为eql?方法在C源码里是rb_ary_eql这个函数, 看到这里,我有点好奇了, 就想探寻一下uniq的工作机制。

我打开了github上Ruby的源码,搜索了一下, rb_ary_uniq,因为这是Ruby的uniq方法在C源码中的函数名, 于是就找到了array.c这个文件里对uniq方法的定义:

static VALUE
rb_ary_uniq(VALUE ary)
{
    VALUE hash, uniq;

    if (RARRAY_LEN(ary) <= 1)
        return rb_ary_dup(ary);
    if (rb_block_given_p()) {
        hash = ary_make_hash_by(ary);
        uniq = rb_hash_values(hash);
    }
    else {
        hash = ary_make_hash(ary);
        uniq = rb_hash_values(hash);
    }
    RBASIC_SET_CLASS(uniq, rb_obj_class(ary));
    ary_recycle_hash(hash);

    return uniq;
}


(比对一下ruby-doc.org上面查看的方法的源码,你就知道哪个更靠谱一些了。)

其实我在「诱人的Ruby - 入门篇」的第19课时,讲过如何用C扩展一个ruby gems, 我们知道比较安全和常用的一种扩展方式就是使用"ruby.h",利用Ruby定义好的库,相当于可以用C来写Ruby代码了,在这个库里,函数的命名都很有规律的。

@赵宇给的代码里,使用uniq后面并没有加block,那么,当uniq执行的时候, 程序的执行会走进else语句里,那么我们重点要考察的就是这两行代码了:

    hash = ary_make_hash(ary);
    uniq = rb_hash_values(hash);

我们先来看看第一行代码:hash = ary_make_hash(ary)


我们看到ary_make_hash这个函数,是ary打头命名的函数,那么就应该是在array.c这个文件中被定义的,所以直接在这个文件里查它的定义:

static VALUE
ary_make_hash(VALUE ary)
{
    VALUE hash = ary_tmp_hash_new();
    return ary_add_hash(hash, ary);
}

很轻松就查到了, 代码就两行,可以看得出来, 这个方法是把uniq方法传入的数组,给变成了Hash。ary_tmp_hash_new(), 这个方法甚至都不用去查,可以想到,这是创建一个临时的Hash结构,然后使用ary_add_hash(hash, ary)这个方法,把数组加入到那个临时的Hash里去

static VALUE
ary_add_hash(VALUE hash, VALUE ary)
{
    long i;

    for (i=0; i<RARRAY_LEN(ary); i++) {
        VALUE elt = RARRAY_AREF(ary, i);
        rb_hash_aset(hash, elt, elt);
    }
    return hash;
}

在ary_add_hash函数里,我们看得到, 传进来的数组被循环的插入到Hash里, 那么最终这个Hash的结构是什么样子的呢?或者说, 数组是按什么规则变成一个Hash的呢? 看来有必要去考察一下这个rb_hash_aset的方法了。

可是无奈的是, 我没有在ruby源码中找到这个方法的定义, 原因是我对C语言不是很熟悉,希望哪位看到文章的大神帮我找一下。

不过,我在查找过程中,发现这个函数的用法是这样的:

rb_hash_aset({}, key, value)
就是说, 这个方法执行以后,会创建一个类似于这样的hash:{key => value}

明白了rb_hash_aset方法的用法之后,就不难了解,在ary_add_hash里, 最终传进来的数组变成了下面Ruby语言描述的Hash结构了:

arr = [1, 2, 3, 4]
hash = {1 => 1,  2 => 2,  3 => 3, 4 => 4}

也就是说,ary_add_hash方法按传进去的数组每个元素自身做key和value,来创建了一个Hash。

这个时候,rb_ary_uniq方法里,

  hash = ary_make_hash(ary)

这句代码算是解释清楚了。

那么还剩下另一行代码,我们看看:

uniq = rb_hash_values(hash);

到目前为止,我们发现一个命名规律:

rb_ary_uniq # 是Ruby语言里uniq方法的内部定义
ary_make_hash # 是array.c文件中,Ruby源码内部调用的函数

所以我们得出一个结论, rb_hash_values,应该是在hash.c文件里定义的, 结果,搜了一下, 果然如此

VALUE
rb_hash_values(VALUE hash)
{
    VALUE values;
    st_index_t size = RHASH_SIZE(hash);

    values = rb_ary_new_capa(size);
    if (size == 0) return values;

    if (ST_DATA_COMPATIBLE_P(VALUE)) {
        st_table *table = RHASH(hash)->ntbl;

        if (OBJ_PROMOTED(values)) rb_gc_writebarrier_remember_promoted(values);
        RARRAY_PTR_USE(values, ptr, {
            size = st_values_check(table, ptr, size, Qundef);
        });
        rb_ary_set_len(values, size);
    }
    else {
        rb_hash_foreach(hash, values_i, values);
    }

    return values;
}

这个方法太长了, 但是幸好有注释啊:

 *     h = { "a" => 100, "b" => 200, "c" => 300 }
 *     h.values   #=> [100, 200, 300]

原来这个方法,就是获取hash的所有values。


于是,我们终于得出结论了, Array#uniq的工作机制,可以用下面Ruby代码描述:

arr = [1, 2, 3, 4, 1, 2]
hash = {1 => 1,  2 => 2,  3 => 3, 4 => 4}
new_arr = hash.values  #=> [1, 2, 3, 4]

原来, uniq方法,就是把数组变成了Hash,然后利用了Hash的Key值不能重复的工作机制来去重复的。


但是到目前为止,我们还是没有解决,为什么修改了Object#hash和Object#eql?方法会对Array#uniq产生影响。但是在了解了uniq方法的工作机制之后,我们会想,难道,是创建Hash的时候, 判断Key值重复的时候,使用了Object#hash和Object#eql?方法? 想到这里,我马上翻开了Object#hash方法的文档看到了以下文字:

The hash value is used along with eql? by the Hash class to determine if two objects reference the same hash key.
翻译过来就是:这个hash值,是在Hash结构使用eql?方法去确认是否有两个相同的对象引用被当作了Hash key的时候被调用的。

最后,我在@赵宇的代码后面加了几行代码去验证上面所说:

item1 = Item.new("abcd", 1) 
item2 = Item.new("abcd", 1)

item3 = Item.new("abcd", 2)

h = {}
h[item1] = item1
h[item2] = item2

到此,迷雾解开:

- uniq方法,就是把数组变成了Hash,然后利用了Hash的Key值不能重复的工作机制来去重复的。

- Hash检查key值是否重复的时候,调用了Object#eql?和Object#hash方法。


最后欢迎关注公众帐号: RubyStudy


Comments

comments powered by Disqus