2005年度 データ構造とアルゴリズム 第6回 「ハッシュ法を用いた探索」

Presentation on theme: "2005年度 データ構造とアルゴリズム 第6回 「ハッシュ法を用いた探索」"— Presentation transcript:

1 2005年度 データ構造とアルゴリズム 第6回 「ハッシュ法を用いた探索」
2005年度 データ構造とアルゴリズム 第6回 「ハッシュ法を用いた探索」 西尾 信彦 立命館大学情報理工学部 情報システム学科

2 O(log n)よりも高速な探索 配列のインデックスとキーを一致させればO(1)である！！！ キーの範囲だけの大きさの配列が必要
非実用的 キーから配列のインデックスに変換する適切な関数を作成，これをハッシュ関数という 均等に分配するような関数 キーを100で割れば大きさは100分の1になる 同じハッシュ値となるレコードは同じハッシュバケットに入る

3 ハッシュ関数 キーのとりうる範囲を一定の範囲(0～M-1)する ハッシュの衝突は極力避けたい 例えば，整数のキーであれば剰余系を利用する
均等に分散させるため 例えば，整数のキーであれば剰余系を利用する 文字列によるキーの場合 頭の数文字で生成するのはダメ 同じ文字セットの順番が変っていたら違うハッシュ値が欲しい KnuthやWeinbergの例を参照 ハッシュ関数自体のコストがかかっていたらそもそもダメ

4 分離連鎖法 ハッシュ値の衝突を許容し 計算の手間はN/M？ ハッシュバケットをリストで生成する
各ハッシュ値のリストの先頭からなる配列を用意する ハッシュ関数でバケットを選択して，リストを逐次検索 計算の手間はN/M？ 適切なMの選び方 バケットを構成するリストを工夫する

5 上図のような入力ファイルを用いて，データ入力を行い，キーボードから検索キーを入力し，リストにあるかどうかを調べる
Hash 分離連鎖法の例： 実行結果： bucket[0] Jamaica bucket[0] France bucket[0] China . bucket[12] Belguim bucket[12] Argentina 検索ワード：Japan Japan が見つかりました． 入力ファイル #include <stdio.h> #include <stdlib.h> #include <string.h> #define HASHSIZE 13 #define STR_MAX 256 typedef struct _listelem{ struct _listelem *next; char *s; }listelem, *list; list bucket[HASHSIZE]; char *word; unsigned long hashpjw(unsigned char* str){ unsigned long hash = 0, g; for( ; *str; ++str){ hash = (hash << 4) + *str; if((g = hash & 0xf )){ hash ^= g >> 24; hash ^= g; } return hash; Afghanistan Albania Algeria Andorra Angola . Kenya Kiribati Korea 上図のような入力ファイルを用いて，データ入力を行い，キーボードから検索キーを入力し，リストにあるかどうかを調べる

6 Hash 分離連鎖法の例： char *search_add(char *s, int flag){ int h; list l;
　　　　h = hashpjw(s) % HASHSIZE; /* ハッシュ値を算出 */ 　　　　for(l = bucket[h]; l; l = l->next){ 　　　　　　　if(strcmp(l->s, s) == 0) return l->s; 　　　　} 　　　　if(flag == 0) return NULL; 　　　　l = (list)malloc(sizeof(listelem)); 　　　　l->s = s; 　　　　l->next = bucket[h]; 　　　　bucket[h] = l; 　　　　return l->s; } void RegistryList(char *filename){ 　　　FILE *fpIn; 　　　char str[STR_MAX], tmp[STR_MAX]; 　　　int i, start; 　　　if((fpIn = fopen(filename, "r")) == NULL){ 　　　　fprintf(stderr, "Cannot open file [%s].\n", filename); 　　　　exit(1); 　　　} 　　　　while(fgets(str, STR_MAX, fpIn) != NULL){ 　 sscanf(str, "%s", tmp); word = (char *)malloc(sizeof(char)*strlen(tmp)); strcpy(word, tmp); 　　/* リストへの登録を行うので，第二引数を0以外にしておく */ search_add(word, 1); 　　　　fclose(fpIn); int main(int argc, char **argv){ 　　　　int i; 　　　　list p; 　　　　char input[STR_MAX]; 　　　　/* ファイルから読み込んだデータをリストに格納 */ 　　　　RegistryList(argv[1]); 　　　　for(i = 0; i < HASHSIZE ; i++){ 　　　　　　　　　for(p = bucket[i]; p != NULL ; p = p->next){ 　　　　printf("bucket[%d] %s\n", i, p->s); } 　　　　} 　　　　printf("検索ワード："); 　　　　scanf("%s", input); 　　　　/* 検索のみなので，第二引数のflagを0にする */ 　　　　if(search_add(input, 0) != NULL){ printf("%s が見つかりました．\n", input); 　　　　else{ printf("%s は見つかりませんでした．\n", input); 　　　　　}