Ruby 中的哈希“has_key”复杂性

Question

我有一个哈希vars = {"a" => "Name", "b" => "Address" , "c" => "Phone"}。我想检查这条线的性能：

vars.has_key(:b)?

是 O(1) 还是 O(散列大小)？

Answer 1

简单的基准：

require 'benchmark'

iterations = 10_000
small      = 10
big        = 1_000_000

small_hash = {}
big_hash   = {}

(1..small).each do |i|
  small_hash[i] = i
end

(1..big).each do |i|
  big_hash[i] = i
end

Benchmark.bmbm do |bm|
  bm.report('Small Hash') do
    iterations.times { small_hash.has_key?(1) }
  end

  bm.report('Big Hash') do
    iterations.times { big_hash.has_key?(1) }
  end
end

运行测试：

$ ruby has_key_test.rb 
                 user     system      total        real
Small Hash   0.000000   0.000000   0.000000 (  0.001167)
Big Hash     0.000000   0.000000   0.000000 (  0.001171)

所以是的，我认为我们可以考虑成本常数 O(1)（至少，不检查内部 MRI 实现）。

注意这并非在所有情况下 100% 正确，请参阅此答案中的更多详细信息。

Answer 2

源代码has_key是（http://ruby-doc.org/core-1.9.3/Hash.html#method-i-has_key-3F）

rb_hash_has_key(VALUE hash, VALUE key)
{
    if (!RHASH(hash)->ntbl)
        return Qfalse;
    if (st_lookup(RHASH(hash)->ntbl, key, 0)) {
        return Qtrue;
    }
    return Qfalse;
}

有st_lookup以下片段（https://github.com/ruby/ruby/blob/ca6b174078fa15f33655be704d9409fdbc4f9929/st.c#L383）：

if (table->entries_packed) {
    st_index_t i = find_packed_index(table, hash_val, key);
    if (i < table->real_entries) {
        if (value != 0) *value = PVAL(table, i);
        return 1;
    }
        return 0;
    }

这告诉我们，如果entries_packed那么 ruby​​ 使用索引 (O(1))，否则它使用无索引搜索 (O(n))。

的值entries_packed似乎取决于哈希的大小：（https://github.com/ruby/ruby/blob/ca6b174078fa15f33655be704d9409fdbc4f9929/st.c#L41）

#define MAX_PACKED_HASH (int)(ST_DEFAULT_PACKED_TABLE_SIZE * sizeof(st_table_entry*) / sizeof(st_packed_entry))

https://github.com/ruby/ruby/blob/ca6b174078fa15f33655be704d9409fdbc4f9929/st.c#L219

tbl->entries_packed = size <= MAX_PACKED_HASH;

这size是索引大小的一种。

您可以在 ruby​​ 源代码中找到更多详细信息，但其复杂度并不总是 O(1)，而是取决于哈希的大小。（关于其索引的大小）