在Ruby中哈希“has_key”的复杂性
我有一个哈希vars = {"a" => "Name", "b" => "Address" , "c" => "Phone"} 。 我想检查一下这行的性能：
vars.has_key(:b)?
是O（1）还是O（哈希的大小）？
简单基准：
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实现）。
该方法的预期复杂性是恒定的。
def fake_h(n) n.times.inject({}){|o,x| o[x] = :a; o} end n = 1000000; h1 = fake_h(1); h10 = fake_h(10); h100 = fake_h(100); h1000 = fake_h(1000); h10000 = fake_h(10000); h100000 = fake_h(100000); h1000000 = fake_h(1000000); Benchmark.bm do |x| x.report { n.times{|t| h1.has_key?(t) } } x.report { n.times{|t| h10.has_key?(t) } } x.report { n.times{|t| h100.has_key?(t) } } x.report { n.times{|t| h1000.has_key?(t) } } x.report { n.times{|t| h10000.has_key?(t) } } x.report { n.times{|t| h100000.has_key?(t) } } x.report { n.times{|t| h1000000.has_key?(t) } } end # Result : user system total real 0.200000 0.000000 0.200000 ( 0.204647) 0.210000 0.000000 0.210000 ( 0.205677) 0.210000 0.000000 0.210000 ( 0.214393) 0.210000 0.000000 0.210000 ( 0.206382) 0.210000 0.000000 0.210000 ( 0.208998) 0.200000 0.000000 0.200000 ( 0.206821) 0.220000 0.000000 0.220000 ( 0.213316)
具有1个条目或1百万个条目的哈希之间的差异是……最小的。
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），但取决于哈希的大小。 （关于其指数的大小）