Hash “has_key” complejidad en Ruby

Tengo un vars = {"a" => "Name", "b" => "Address" , "c" => "Phone"} hash vars = {"a" => "Name", "b" => "Address" , "c" => "Phone"} . Quiero comprobar el rendimiento de esta línea:

 vars.has_key(:b)? 

¿Es O (1) u O (tamaño de hash)?

Punto de referencia simple:

 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 

Ejecutando la prueba:

 $ 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) 

Entonces sí, creo que podemos considerar el costo constante O (1) (al menos, sin verificar la implementación interna de MRI).

La complejidad esperada del método es constante.

 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) 

La diferencia entre un hash con 1 entrada o 1 millón de entradas es … mínima.

El código fuente de has_key es ( 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; } 

El st_lookup tiene el fragmento siguiente ( 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; } 

Lo que nos dice que si entries_packed , ruby ​​usa el índice (O (1)), de lo contrario, utiliza la búsqueda no indexada (O (n)).

El valor de entries_packed parece depender del tamaño del hash: ( 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; 

El size es un tipo de tamaño de índice.

Puede encontrar más detalles en las fonts de ruby, pero su complejidad no siempre es O (1), sino que depende del tamaño del hash. (sobre el tamaño de su índice)