Hash "has_key" complexity in Ruby

Question

I have a hash vars = {"a" => "Name", "b" => "Address" , "c" => "Phone"}. I want to check the performance of this line :

vars.has_key(:b)?

Is it O(1) or O(size of hash) ?

Answer 1

Simple benchmark:

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

Running the test:

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

So yes, I think we can consider the cost constant O(1) (at least, without check the internal MRI implementation).

NOTE This is not 100% true in all scenarios, see more details in this answer.