トップに関する質問英和辞書を作成しているのですが、ハッシュ関数の選び方についてアドバイスを頂きたいです。

編集履歴

質問編集履歴

もう少し情報を追加しました

2020/05/18 02:14

投稿

aardvark

スコア17

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -514,4 +514,9 @@
 ・
 ・
 ```
-が延々と続いてしまうのです！！！！！
+が延々と続いてしまうのです！！！！！
+編集2:
+ごめんなさい、よく考えたらr=hash_search(H, s);→slist_insert_tail(L, r);のときは次のリストの要素を指すポインタもそのままコピーされるのですから、そりゃ無限ループになりますよね、、、
+もう少し考えます

質問文に説明を追加

2020/05/18 02:14

投稿

aardvark

スコア17

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -492,7 +492,7 @@
     return 0;
 }
 ```
-例えば、
+例えば、ハッシュ関数が常に1を出力するよう変更し、
 ```
 3
 coffee コーヒー

コードにコメントした

2020/05/18 02:08

投稿

aardvark

スコア17

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -419,7 +419,7 @@
     int h=hfunc(H, key);
     p = H.T[h]->head;
     while(p!=NULL){
-        if(string_compare(p->key, key)==0){
+        if(string_compare(p->key, key)==0){ //keyと一致するような要素を同じスロットにあるリストから探索していきます
            return p;
        }
         p = p->next;

コードを書き直しましたが、やはりうまくいきません

2020/05/18 02:06

投稿

aardvark

スコア17

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -259,4 +259,259 @@
 　自分で調べててみたところ、どうもハッシュ関数を改良したほうがよさそうなので、mの値を数万程度ではなく数百万程度の素数に変えるなどをしてみました。しかし、mにどのような値を入れてもうまくいきません。
-　どこを改良するべきか、アドバイスいただけるでしょうか。宜しくお願いします。
+　どこを改良するべきか、アドバイスいただけるでしょうか。宜しくお願いします。
+編集：
+衝突が起きる場合を想定して書き直しましたが、今度は同じスロットの要素を出力するときにおかしくなります。
+```C
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <math.h>
+#define NEW(p, n){p = malloc((n)*sizeof(p[0]));}
+typedef char* String;
+//後々使いやすくするため、ここでStringタイプを定義しちゃいます
+//英和辞書用のオブジェクトです(英語の見出しと日本語の意味のペア)
+typedef struct slobj_{
+    struct slobj_* next;
+    String key;
+    String jpn;
+}* slobj;
+//連結リスト
+typedef struct{
+    slobj head;
+    slobj tail;
+}* slist;
+typedef struct{
+    int n; //ハッシュに格納されている要素数
+    int m; //ハッシュ表のサイズ
+    slist* T; //リストの配列
+} hash;
+ハッシュ関数
+int hfunc(hash H, String key){
+    int h=0, i=0;
+    while (key[i] != 0){
+        h = h*3659+key[i]; //ハッシュ値を計算
+        i++;
+    }
+    return abs(h) % H.m; //非負の値にして、表のサイズで割った余り
+    //return 1; //ハッシュ関数が全て同じ値を出す場合で実験してみました。
+}
+//文字列の長さを求める
+int string_len(String str){
+    int len=0;
+    while(str[len]!=0){
+        len++;
+    }
+    return len;
+}
+//文字列を標準入力から読む
+String string_input(void){
+    int i, len;
+    char buf[1000];
+    String str;
+    scanf("%999s", buf);
+    len = string_len(buf);
+    NEW(str, len+1);
+    for(i=0; i<len; i++){
+        str[i]=buf[i];
+    }
+    str[len] = 0;
+    return str;
+}
+//文字列が同じかどうかを判定する関数
+int string_compare(String p, String q){
+    int c1, c2;
+    int i=0;
+    while(1){
+        c1=p[i]; c2=q[i];
+        if(c1<c2) return -1;
+        if(c1>c2) return 1;
+        if(c1==0) break;
+        i++;
+    }
+    return 0;
+}
+//新しい連結リストを作成
+slist slist_new(void){
+    slist L;
+    NEW(L, 1);
+    L -> head = NULL;
+    L -> tail = NULL;
+    return L;
+}
+//新しいリスト要素(つまり英和辞典における英語の見出しと対応する日本語のペア)
+slobj slobj_new(String x, String y){
+    slobj p;
+    NEW(p, 1);
+    p -> key = x;
+    p -> jpn = y;
+    p -> next = NULL;
+    return p;
+}
+//連結リストの先頭に挿入
+void slist_insert_head(slist L, slobj p){
+    p -> next = L -> head;
+    L -> head = p;
+}
+//連結リストの末尾に挿入
+void slist_insert_tail(slist L, slobj p){
+    if(L -> head == NULL){
+        L -> tail = p;
+        L -> head = p;
+    }
+    else if(L -> head == L -> tail){
+        L -> tail = p;
+        L -> head -> next = p;
+    }
+    else{
+        L -> tail -> next = p;
+        L -> tail = p;
+    }
+}
+//連結リストをプリント
+void slist_print(slist L)
+{
+    slobj p;
+    p = L->head;
+    while (p != NULL){
+        if(string_compare(p->jpn, "NO")==0){
+            printf("%s\n", p->jpn);
+        }
+        else{
+            printf("%s %s\n", p -> key, p -> jpn);
+        }
+        p = p-> next;
+    }
+}
+//表のサイズがmのハッシュ表を作る
+hash hash_new(int m){
+    hash H;
+    int i;
+    NEW(H.T, m);
+    H.m = m;
+    for(i=0; i<= m-1; i++){
+        H.T[i]=slist_new();
+    }
+    return H;
+}
+//キーがkeyである要素を返す
+slobj hash_search(hash H, String key){
+    slobj p;
+    int h=hfunc(H, key);
+    p = H.T[h]->head;
+    while(p!=NULL){
+        if(string_compare(p->key, key)==0){
+           return p;
+       }
+        p = p->next;
+       }
+    return p;
+}
+//ハッシュに入力する関数。同じスロットにハッシュされたすべての要素が連結リストに格納されるようにします。
+void hash_insert(hash H, slobj obj){
+    int h=hfunc(H, obj->key);
+    slist_insert_head(H.T[h], obj);
+}
+void slist_free(slist L){
+    slobj p, q, r;
+    p = L->head;
+    q = p->next;
+    while (q != NULL){
+        r = q;
+        q = q-> next;
+        free(p);
+        p = r;
+    }
+    free(p);
+    free(L);
+}
+void hash_free(hash H){
+    int i;
+    for(i = 0; i <= H.m-1; i++){
+        if(H.T[i] -> head != NULL){
+            slist_free(H.T[i]);
+        }
+    }
+    free(H.T);
+}
+int main(){
+    int i, j, k, n;
+    String eng, jpn, s;
+    double v;
+    slobj p, r;
+    hash H;
+    slist L=slist_new(); //ここに出力する実数を格納していく
+    int m=81239; //数千から数万程度の素数がいいらしい
+//ここから英和辞典を作成します。
+    scanf("%d", &n); //英和辞典に記録していく英語日本語ペアの数
+    H=hash_new(m);
+    H.n = n;
+//英語日本語ペアを順次入れていく
+    for(i=1; i<=n; i++){
+        eng=string_input();
+        jpn=string_input();
+        p=slobj_new(eng, jpn);
+        hash_insert(H, p);
+    }
+//ここからはkeyを入力していきます。各keyに対応する英和辞典の見出しがある場合はそのkeyおよびそれに対応する日本語を、ない場合は-1と出力します
+    scanf("%d", &k);//以後の問い合わせの数
+    for(j=1; j<=k; j++){
+        s=string_input();
+        r=hash_search(H, s);
+        if(r==NULL){
+            r=slobj_new(NULL, "NO");
+        }
+        slist_insert_tail(L, r);
+    }
+    slist_print(L);
+    //slist_free(L);
+    //hash_free(H);
+    return 0;
+}
+```
+例えば、
+```
+3
+coffee コーヒー
+milk 牛乳
+water 水
+2
+milk
+coffee
+```
+という入力にした場合、
+```
+milk 牛乳
+coffee コーヒー
+milk 牛乳
+coffee コーヒー
+milk 牛乳
+coffee コーヒー
+・
+・
+・
+```
+が延々と続いてしまうのです！！！！！

文章を追加

2020/05/18 02:04

投稿

aardvark

スコア17

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -255,7 +255,7 @@
 aucltz
 (中略)
 ```
-のような長いインプットで正しく動作しないようです。
+のような長いインプットだと、間違ったkeyに対応する見出しが何個か出力されてしまい、正しく動作しないようです。
 　自分で調べててみたところ、どうもハッシュ関数を改良したほうがよさそうなので、mの値を数万程度ではなく数百万程度の素数に変えるなどをしてみました。しかし、mにどのような値を入れてもうまくいきません。

コードの修正

2020/05/18 00:14

投稿

aardvark

スコア17

title CHANGED Viewed

File without changes

body CHANGED Viewed

@@ -34,10 +34,9 @@
 int hfunc(hash H, String key){
     int h=0, i=0;
     while (key[i] != 0){
-        h = h*3659+key[i]; //ハッシュ値を計算
+        h = h*101+key[i]; //ハッシュ値を計算
         i++;
     }
-    h = h*1000;
     return abs(h) % H.m; //非負の値にして、表のサイズで割った余り
 }

タイトルの変更

2020/05/18 00:10

投稿

aardvark

スコア17

title CHANGED Viewed

	@@ -1,1 +1,1 @@
1	- ハッシュ関数の選び方についてアドバイスを頂きたいです。
1	+ 英和辞書を作成しているのですが、ハッシュ関数の選び方についてアドバイスを頂きたいです。

body CHANGED Viewed

File without changes