Techioz Blog

Rubyのハッシュ「has_key」の複雑さ

概要

ハッシュ変数 = {“a” => “名前”、“b” => “住所”、“c” => “電話番号”} があります。この行のパフォーマンスを確認したいと思います。

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 実装をチェックせずに)。

注: これはすべてのシナリオに 100% 当てはまるわけではありません。詳細については、この回答を参照してください。