データ構造のお勉強。本日はハッシュテーブル。

ハッシュテーブル - アルゴリズムとデータ構造

ハッシュテーブル（hash table）は、 「ハッシュ値」という物を使うことによって、 要素の挿入・削除・検索を非常に高速に行うことの出来るコレクションです。

挿入する要素の数よりも、余裕を見て大きめのメモリを確保して置くならば、 要素の挿入・削除・検索をほぼ O(1) （要素数によらず一定時間）で行うことができます。

要素の挿入・削除・検索をほぼ O(1) （要素数によらず一定時間）で行うことができる のはスゴい。

ハッシュ値、ハッシュ関数とは？

ハッシュ（hash）というのは、 文字列などの任意のデータから、そのデータを要約して得られる固定長の値のことです。 得られた値のことをハッシュ値（hash value）、 値を得る操作をハッシュ関数（hash function）といいます。

ハッシュは不可逆

パスワード認証で使われる。

元のメッセージよりも持っている情報量が少ないということは、 原理的に不可逆で、 ハッシュ値から元のメッセージを再生することはできません。 このような性質から、パスワード認証に使われたりもします。 （認証サーバ内では、パスワードのハッシュ値が記録されている。）

メッセージダイジェストとの違い

メッセージダイジェストという言葉も使われるが何が違うのか？

メッセージの真偽確認やパスワード認証のために使われる場合には、 ハッシュ値のことを「メッセージダイジェスト」と呼ぶ場合もあります。

これに対して、「ハッシュ値」という呼び方をする場合、「任意のデータから固定長の値（ほとんどの場合整数値）を得る」という部分に意味があります。

Hash vs Array キーの探索のパフォーマンス比較

キーの探索の計算量は次の通り

  • Hash: O(1)
  • Array: O(n)

Rubyでベンチマークしてみた結果

ary = Array.new(10_000) { rand(1...100_000_000) }.freeze
hash = ary.to_h {|n| [n, n] }.freeze
RANDOM_NUMBERS = Array.new(10_000) { rand(1...100_000_000) }.freeze

require 'benchmark'

Benchmark.bm 10 do |r|
  r.report "Array" do
    RANDOM_NUMBERS.each do |n|
      ary.include? n
    end
  end
  r.report "Hash" do
    RANDOM_NUMBERS.each do |n|
      hash.key? n
    end
  end
end

結果は下記の通り。

                 user     system      total        real
Array        0.498321   0.000451   0.498772 (  0.499107)
Hash         0.000851   0.000000   0.000851 (  0.000851)

See also