4．5 ハッシュ法
番号 以下をクリックすると，該当箇所にジャンプします （１） ハッシュ法（hashing）とは （２） キー値の衝突 （３） チェイン法 （４） オープンアドレス法 （５） 文字列のハッシュ値 （１）ハッシュ法(hashing)とは ２分探索法を使うと， 効率のよい探索ができますが， 配列は，ソート済みでなければなりません。 そこでソート済み配列への データの挿入を考えてみると， 以下のように配列をずらす必要があります。 　　　　 すなわち，挿入のためのコストが大きくなります。 ［配列をずらす処理］ そこで，ハッシュ法では， 配列に格納するキーをもとに，簡単な計算で 格納する位置（配列の添え字）を計算します。 たとえば，キーの値を１３で割った余りを ハッシュ値とする場合，次のように格納します。 　　 ハッシュ法では，ハッシュ値を計算するだけで， 目的の値があるかどうかが分かることになります。 ハッシュ法では， ■配列の各要素をバケット（bucket） ■ハッシュ値を計算する関数をハッシュ関数（hashing function） と呼びます 番号 以下をクリックすると，該当箇所にジャンプします （１） ハッシュ法（hashing）とは （２） キー値の衝突 （３） チェイン法 （４） オープンアドレス法 （５） 文字列のハッシュ値 （２）キー値の衝突 例えば，キー地３５（１３の剰余＝９）を 挿入することを考えてみましょう。 しかし，キー値３２（１３の剰余＝６）を挿入しようとすると， 以下のように，既にキー値が埋まっていますので， 挿入することができません。 これを「キーの衝突」といいます。 　　 これを「キーの衝突」といいます。 キーの衝突を避けるには，以下の方法があります。 ■チェイン法 ：同一値をもつ要素を線形リストで管理する方法 ■オープンアドレス法 ：空きバケットを見つけるまでハッシュを繰り返す方法 番号 以下をクリックすると，該当箇所にジャンプします （１） ハッシュ法（hashing）とは （２） キー値の衝突 （３） チェイン法 （４） オープンアドレス法 （５） 文字列のハッシュ値 （３）チェイン法 チェイン法とは，以下のように，各バケットに， キー値を持つノードを連結した線形リストへのポインタを 格納する方法です。 　　 線形リストとして挿入しますので，衝突することはありません。 削除も線形リストの削除として処理されます。 　　 ［確認用プログラム例］ 線形リストを使いますので，その領域管理， 線形リストの操作用関数をも合わせて示します。 確認用プログラムでは，領域管理のテスト用ルーチンも示します。 　　　 // データ宣言 public struct NumberListData { 　　public int Data; 　　public int Pointer; } public const int AREASIZE = 50; public const int HASHSIZE = 16; public int ErasePointer; public static NumberListData[] 　　 NumberList=new NumberListData[AREASIZE]; public int[] Bucket=new int[HASHSIZE]; // バケット領域の初期化 public void BucketInitialize() { 　　for(int i=0;i<Bucket.Length;i++) Bucket[i]=-1; } // 線形リスト格納領域の管理 public void AreaInitialize() { 　　int i; 　　for(i=0;i<NumberList.Length;i++) NumberList[i].Pointer=i+1; 　　NumberList[NumberList.Length-1].Pointer=-1; 　　 ErasePointer=0; } public int GetArea() { 　　if (ErasePointer<0) return -1; 　　int P=ErasePointer; 　　ErasePointer=NumberList[ErasePointer].Pointer; 　　return P; } public void FreeArea(int P) {　　NumberList[P].Pointer=ErasePointer; 　　ErasePointer=P; } // 線形リストの操作 public int replaca(int P, int A) { NumberList[P].Data=A; return P; } public int replacd(int P, int A) { NumberList[P].Pointer=A; return A;} public int car(int P) { return NumberList[P].Data;} public int cdr(int P) { return NumberList[P].Pointer;} public int cons(int A, int B) { 　　int P=GetArea(); if(P<0) return -1; 　　NumberList[P].Data=A; NumberList[P].Pointer=B; 　　return P; } //　処理初期設定と共通ルーチン private void Form1_Load(object sender, System.EventArgs e) {　 BucketInitialize(); AreaInitialize(); ポインタ部の表示(); } private void ポインタ部の表示() { 　　listBox1.Items.Clear(); 　　listBox1.Items.Add("Erase Pointer=" + ErasePointer.ToString()); 　　listBox1.Items.Add("(ポインタ部のみ)"); 　　int i=ErasePointer; 　　while(i>=0) { i=cdr(i);listBox1.Items.Add(i.ToString());} } // 領域管理のテスト private void button1_Click(object sender, System.EventArgs e) { 　　int P=GetArea(); string PS=P.ToString(); 　　textBox1.Text=PS; ポインタ部の表示(); 　　MessageBox.Show (PS); } private void button2_Click(object sender, System.EventArgs e) { 　　FreeArea(int.Parse(textBox1.Text)); ポインタ部の表示(); } // ハッシュテーブルの表示 private void ハッシュ表示() { 　　　string S; int P; 　　　listBox1.Items.Clear(); 　　　for(int i=0;i<Bucket.Length;i++) 　　　{ 　　　　　 S=i.ToString()+" "; P=Bucket[i]; 　　　　　if(P>=0) 　　　　　{ 　　　　　　　　while(P>=0) { S += " " + car(P).ToString(); P=cdr(P); } 　　　　　　　　listBox1.Items.Add(S); 　　　　　　} 　　　　　 else listBox1.Items.Add(S+"(空)"); 　　　　} } //　線形リストの表示 private int SearchKey(int Key, int P) { 　　int PP=P; 　　while(PP>=0) 　　{ 　　　　if(car(PP)==Key) return PP; 　　　　PP=cdr(PP); 　　} 　　return -1; } // 　ハッシュ設定 private void ハッシュ設定(int Key, int Mod) { 　　　int ID = Key % Mod; 　　　if(SearchKey(Key, Bucket[ID])<0) Bucket[ID]=cons(Key, Bucket[ID]); } private void button3_Click(object sender, System.EventArgs e) { 　　int Mod = Bucket.Length; 　　int Key = int.Parse(textBox1.Text) ; 　　ハッシュ設定(Key, Mod); 　　ハッシュ表示(); } //　ハッシュ探索 private int ハッシュ探索(int Key, int Mod) { 　　　int ID = Key % Mod; return SearchKey(Key, Bucket[ID]); } private void button4_Click(object sender, System.EventArgs e) { 　　int Mod = Bucket.Length; 　　int Key = int.Parse(textBox1.Text) ; 　　int P = ハッシュ探索(Key, Mod); 　　MessageBox.Show(P.ToString()); } //　ハッシュ削除 private int ハッシュ削除(int Key, int Mod) { 　　int ID = Key % Mod; 　　int Befor = -1;　int P = Bucket[ID]; 　　if(P<0) return -1; 　　while(P >= 0) 　　{ 　　　　if(car(P) == Key) break; 　　　　Befor = P; 　　　　P = cdr(P); 　　} 　　int After = cdr(P); FreeArea(P); 　　if(Befor < 0) Bucket[ID] = After; 　　else replacd(Befor, After); 　　return After; } private void button5_Click(object sender, System.EventArgs e) { 　　int Mod = Bucket.Length; 　　int Key = int.Parse(textBox1.Text) ; 　　int P = ハッシュ削除(Key, Mod); 　　ハッシュ表示(); } 番号 以下をクリックすると，該当箇所にジャンプします （１） ハッシュ法（hashing）とは （２） キー値の衝突 （３） チェイン法 （４） オープンアドレス法 （５） 文字列のハッシュ値 （４）オープンアドレス法 衝突が発生した際，別のバケットに入れるために 再ハッシュ（rehashing）を行う方法です。 この方法は， オープンアドレス法（open addressing）あるいは クローズドハッシュ法（closed hashing）と呼ばれます。 　　 ここでは，再ハッシュの方法として，簡単化するために， キー値に１を加えて１３の剰余をとる方法で 挿入する方法を考えます。 　　　　 削除するには，削除フラグをバケットに付けます。 ここでは削除を「×」で示す。 　　　　 要素を探索するには， 　�@）１５を探索しようとすると，１５ mod １３＝２ 　 　　のバケットが空であるので，探索失敗。 　�A）１８を探索しようとすると，１８ mod １３＝５ 　 　　のパケットが削除済みなので，再ハッシュ， 　 　　更に，キー値が異なるので，再ハッシュ， 　 　　探索値が入っているので，探索成功。 再ハッシュした結果，バケット空に行き当たると， 探索失敗となります。 番号 以下をクリックすると，該当箇所にジャンプします （１） ハッシュ法（hashing）とは （２） キー値の衝突 （３） チェイン法 （４） オープンアドレス法 （５） 文字列のハッシュ値 （５）文字列のハッシュ値 これまで，整数値に対するハッシュ値の例を 挙げましたが，表に登録しておき， それを参照する例の多くは， 一般に名前などの文字列データです。 文字列データでも，例えば，以下のようなハッシュを 考えることができます。 　　■文字列内のChar値の合計値の１６の剰余 ただし，加算の際，１６の剰余の合計値に対する １６の剰余も同じ値ですので， 計算途上でオーバフローしないようにするため， Char値の１６の剰余を加算することにします。 　　［ハッシュ値の計算］ 　　 private int ハッシュ値(string S, int H) { 　　int CH = 0; 　　for(int i = 0; i < S.Length; i++) 　　　　{ CH +=(int) (S[i] % H); CH %= H; } 　　return CH; } 衝突に避ける方法としては，オープンアドレス法を用います。 ここで，バケットには文字列が入りますが， 削除バケットや未登録バケットは以下のようにすることにします。 ■削除マーク　 ：　“\n” ■未登録バケット　　 ：　“\r” すなわち"\n"や"\r"という文字列は 登録しないものとします。 また再ハッシュは１を加えるだけの簡単な方法によります。 ［確認用プログラム例］ private const int HASHVALUE=16; private string[] Bucket = new string[HASHVALUE*2]; private void ハッシュ登録(string Str, int HashMod) { 　　int ID=ハッシュ値(Str, HashMod); 　　while(Bucket[ID]!="\r" && Bucket[ID]!="\n" && ID<Bucket.Length) 　　{ 　　　　　if(Str==Bucket[ID]) 　　　　　{ 　　　　　　　 MessageBox.Show("同一文字列が登録されています"); 　　　　　　　　return; 　　　　　} 　　　　　ID++; 　　　} 　　　if (ID>=Bucket.Length)MessageBox.Show("登録できません"); 　　　else Bucket[ID]=Str; } private int ハッシュ探索(string Str, int HashMod) { 　　int ID=ハッシュ値(Str, HashMod); 　　while(Bucket[ID]!="\r" && ID<Bucket.Length) 　　{ 　　　　if(Str==Bucket[ID]) return ID; 　　　　ID++; 　　} 　　return -1; } private void ハッシュ削除(string Str, int HashMod) { 　　int ID = ハッシュ探索(Str , HashMod); 　　if(ID>=0) Bucket[ID]="\n"； } private void ハッシュ表示() { 　　listBox1.Items.Clear(); 　　for(int i=0;i<Bucket.Length;i++) 　　{ 　　　　if(Bucket[i]=="\r")　　　　listBox1.Items.Add("----"); 　　　　else if(Bucket[i]=="\n") listBox1.Items.Add("****"); 　　　　else　　　　　　　　　　　　　　listBox1.Items.Add(Bucket[i]); 　　} } private void button1_Click(object sender, System.EventArgs e) { 　　string V = textBox1.Text; ハッシュ登録(V , HASHVALUE); 　　ハッシュ表示(); } private int ハッシュ値(string S, int H) { 　　int CH = 0; 　　for(int i = 0; i < S.Length; i++) 　　　　　　　　{ CH +=(int) (S[i] % H); CH %= H; } 　　return CH; } private void Form1_Load(object sender, System.EventArgs e) { 　　for(int i=0;i<Bucket.Length;i++) Bucket[i]="\r"; 　　ハッシュ表示(); } private void button2_Click(object sender, System.EventArgs e) { 　　string V = textBox1.Text; 　　int ID = ハッシュ探索(V , HASHVALUE); 　　listBox1.SelectedIndex = ID; } private void button3_Click(object sender, System.EventArgs e) { 　　string V = textBox1.Text;　ハッシュ削除(V , HASHVALUE); 　　ハッシュ表示(); } // listBox1が選択されたら，その文字列をtextBox1に移す。 private void listBox1_SelectedIndexChanged 　　　　　　　　　(object sender, System.EventArgs e) 　{ textBox1.Text=listBox1.Text; } 番号 以下をクリックすると，該当箇所にジャンプします （１） ハッシュ法（hashing）とは （２） キー値の衝突 （３） チェイン法 （４） オープンアドレス法 （５） 文字列のハッシュ値 1. 基本的なアルゴリズム 2. 基本的なデータ構造 3. 操作を伴うデータ構造 4. 探索 5. 再帰的アルゴリズム 6. ソート 7. 集合 8. 文字列処理 9. 色々なアルゴリズム 上のタイトルをクリックします