ruby-on-rails - 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 实现)。