アルゴリズムを始めよう(ハッシュ探索法)

言語とフレームワークの勉強の他に実際にプログラミングの発想をだすための下地
が必要だと感じ、アルゴリズムを勉強する。教科書はこれ

アルゴリズムを、はじめよう

ハッシュ探索法の特徴

概要

データに一定の計算を施し、その計算結果の値と同じ添字を持つ要素に格納する。
リニア、バイナリについては配列を調べて行くだけ。この探索法はこちらの意図で格納するところから始まる。
例えば数字が書かれた4つのボールとしまうための箱を７個用意する。
ボールの数字の値に対して、同様の計算を施し計算の結果で箱にしまっていく。
この計算式を関数という。関数の中でも今回のように値を代表するような計算をする関数をハッシュ関数といい、ハッシュ関数から導かれる値をハッシュ値という。
4つのボールの値がそれぞれ、11,15,33,37だとするとこれらをハッシュ関数にかけて、箱0から箱6までに振り分けられるようにする。つまり、0から6を導くようにする。
ではどうするのか。箱が7つあるから0から6を割り振るには徐算をしてあまりを導く。
11 % 7 = 4
15 % 7 = 1
33 % 7 = 5
37 % 7 = 2
これをそれぞれ箱にしまっておく。
取り出す時も簡単で15という値が書かれたボールはどこにあるか。15を7
で割ってあまりは1だから1の箱に入っている。

中身

ハッシュ探索法のアルゴリズム構成は2つ。条件に沿って格納するアルゴリズムと、データを探索するアルゴリズムが必要

ハッシュ探索法を使ってデータを格納する

ポイント

配列を２つ用意する。１つは格納したいデータがもともと入っている配列。もう１つはハッシュ探索法を使用するための新しい配列。これは格納したいデータの個数の1.5倍〜2倍の個数格納できる配列とする。あとは格納に必要な変数を用意する。

Rubyで書いてみた

a = [12, 25, 36, 20, 30, 8, 42]
h = Array.new(11, 0) #=>　格納先の配列　元の要素の2倍未満　0で初期化
i = 0
while i < 7 do　#=> aの要素数だけ繰り返す
    k = a[i] % 11　# =>ハッシュ関数　11はhの要素数
     for u in 0..h.size　#=>　ポイント①
        if h[k] == 0
             h[k] = a[i]
             i += 1
             break　# => ポイント②
        elsif h[k] != 0
             k = (k + 1) % 11
        end
    end
 end
 p h　#=> [42, 12, 0, 25, 36, 0, 0, 0, 30, 20, 8]

本には疑似言語で回答が出ている。これをRubyにする上でわからなかった点はつ
。while文の直下に新しいハッシュの要素が0でない時、添字kを再計算するという
k = (k + 1) % 11をどうやってくりかえさすかわからなかった。
解決策はポイント①の通り、0からhの配列の要素数だけ繰り返させて、必ずどこかの箱に納める。もう１つはポイント②のbreak11回の繰り返しの中、箱が見つかれば、次の処理に映るためにfor_inの繰り返しから抜け出すようにする。

ハッシュ探索法を使ってデータを探索する

Rubyで書いてみた

puts "探したいものを入力して"
 x  = gets.to_i
 s = x % 11
 while h[s] != 0 # => ポイント　ハッシュの要素が0になるまでの間繰り返す
 if h[s] == x
  puts "格納場所は#{s}です"
   break
   elsif h[s] != x
    s = (s + 1) % 11
    end

end
if h[s] == 0
    puts "そのデータはありません"
end

ポイントはハッシュの要素が0になるまで繰り返すという点。先ほどの配列では用意した配列の初期値として0を入れていた。そしてハッシュ関数に該当する添字のところに順番に格納をして行ったが、ハッシュ関数に当てはめた結果格納するもののない箱も必ず出てくる。その箱の要素は初期値の０のままだ。例えば、シノニムとなってハッシュ値+1したものでも必ず、0以外の要素とヒットする。なので、0
の要素とヒットするものはそもそもデータとして無いと判断ができる。

仮に配列の中のあまりと該当するものと合致して、whileの中に入ったとしたら？
例えば19という値を入力するとあまりは8になり、元の配列8とあまりが同じ値になる。その場合、h[s] != 0なのでwhileに入る。ただし、h[s] != xなので、
s = (s + 1) % 11になり、繰り返すことになり、いずれ　h[s] == 0に当てハマる時がくる。