ハッシュ表 - van勉だぃありぃ〜

ハッシュ表: キーと値の組み合わせを複数個格納し、キーに対する値を素早く参照するデータ構造。特徴はハッシュと表を使うことでキー同士の比較回数を減らし、高速な検索を実現しようとすること。

ハッシュ表にデータを格納する方法

キーをハッシュした値%nを求める
求めた値のスロットへデータを格納
すでにデータがあった場合、現在のデータの後ろに格納

すでにデータがあった時、衝突が起きている。衝突した場合、データの格納方法にはいくつかのバリエーションがある。

同一データに複数格納
隣のスロットに格納
異なるハッシュ関数を使ってスロット番号を振りなおす

また、ハッシュ表がいっぱいになってきた場合、自動的にハッシュ表を拡大する。

ハッシュ表にデータを取得する方法

キーをハッシュした値%nを求める
求めた値のスロットからデータを取得
データ上のキーと検索キーを照合して、一致すれば取得

ハッシュの検索時間

ハッシュを使うと高速な検索を実現できるというけれど、なぜか。
要素数Nに対する検索について、逐次検索であれば

キー同士の比較*n/2の時間が必要。

となります。
ハッシュの場合は

ハッシュ計算時間 + 表をひく時間　+ 平均衝突破数*キー同士の比較時間

らしい。

ハッシュ表の原理を示すコードを書く

簡単なハッシュ関数を書いてみると下記のようになるらしい。解説では文字列の各バイトを1ビットずつ左へずらしながら排他論理和を取って得た数をハッシュ表の要素数で割った余りをハッシュ値とする。

def hash(s)
  h = 0
  s.each_byte() do |ch|
    h ^= ch
    h <<= 1
  end
  h % TABLE.size()
end

何やってるかよくわからなかったので、irbで実行してみる。

irb(main):001:0> h = 0
=> 0
irb(main):003:0> s = "hello"
=> "hello"
irb(main):004:0> s.each_byte() do |ch|
irb(main):005:1* h^=ch
irb(main):006:1> puts h
irb(main):007:1> h <<= 1
irb(main):008:1> puts("h <<= 1: #{h}")
irb(main):009:1> end
104
h <<= 1: 208
181
h <<= 1: 362
262
h <<= 1: 524
608
h <<= 1: 1216
1199
h <<= 1: 2398
=> "hello"

あー。うーん。どうなってるんだ・・・"<<="を調べ中です。