マップとハッシュ（ハッシュ値生成）
7月 8th, 2008 admin Posted in Ruby, アルゴリズムとデータ構造 | 
今回も「アルゴリズムとデータ構造シリーズ」です。本日は第7章「マップとハッシュ」について。
マップとハッシュ
この章で学びたいのは「文字列をキーにして値を取り出せるデータ構造」である。それを実現するにはまずツリーマップという方法があり、それを改良したものがハッシュマップと呼ばれる一般的なハッシュというやつですよ。というのが今回のお勉強である。
ツリーマップ
まず前章でやったツリー構造を使うのがツリーマップである。キーとなる文字列をstrcmp()関数などで数値化して2分木で保持するというものだ。ツリーのどこにデータがあるかによって計算時間にばらつきがでるので安定していないのが欠点である。
ハッシュマップ
ツリーマップの欠点を克服したのがハッシュマップになる。メモリの消費量は多くなるが、なんと計算量オーダはO(1)と最速。すごい！
これはどのようにやるかと言うと
(1)データの検索キーを数値化する（ハッシュ値）
(2)ハッシュ値を記憶する大きな配列を用意し（ハッシュ表という。array[100]とか）、ハッシュ値に対応する位置にデータを格納する（ハッシュ値が78ならarray[78]に）
(3)データを検索するときには、検索キーを数値化し配列の要素を参照する
という感じだ。僕はなんだか本の索引を思い出しました。検索キーからページ番号がわかるので、そのページを開くと情報が得られるという一旦数字に直すところが面白い。
んで、この段階で以下のような疑問が出てきた
・ハッシュ値は重複しないのか
・ハッシュのサイズに合わせていたらハッシュ表がいくら大きくても足りないのではないか
だけど当然こういうのはクリアされているみたいだ。
コード
今回はまずハッシュ値の生成コードを書くところまで行った。
ハッシュ値はハッシュ表のサイズを抑えるために、ある程度小さい数に抑える必要があるため必ず重複してしまうが、重複に対応できるようにするので多少は問題ない。
-
#make hash
-
def make_hash(str, hashmax)
-
weight = 0
-
hash = 0
-
str.each_byte{|s|
-
weight = 0 if weight> 7
-
hash += s * (256 ** weight)
-
weight+=1
-
}
-
hash % hashmax
-
end
まとめ
今回はハッシュマップの実装の前準備だけを行った。不思議なのはハッシュ表のサイズを素数にすると（上記のコードのhashmax）ハッシュ値の重複が、それが素数でない場合より少なくなるというTipsだ。んーだれか教えて。
※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。
7月 13th, 2008 at 5:37:13
[...] ハッシュ値の生成 [...]