質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
87.20%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

ハッシュマップ

ハッシュ関数を用いてキーを関連する値にマッピングするデータ構造です。

関数

関数(ファンクション・メソッド・サブルーチンとも呼ばれる)は、はプログラムのコードの一部であり、ある特定のタスクを処理するように設計されたものです。

ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

解決済

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

aardvark
aardvark

総合スコア17

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

ハッシュマップ

ハッシュ関数を用いてキーを関連する値にマッピングするデータ構造です。

関数

関数(ファンクション・メソッド・サブルーチンとも呼ばれる)は、はプログラムのコードの一部であり、ある特定のタスクを処理するように設計されたものです。

ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

2回答

0評価

0クリップ

221閲覧

投稿2020/05/18 00:09

編集2020/05/18 02:14

ハッシュテーブルを用いて英和辞典を作成するプログラムをCで書いています。
コードは以下の通りです。

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*101+key[i]; //ハッシュ値を計算 i++; } return abs(h) % H.m; //非負の値にして、表のサイズで割った余り } //文字列の長さを求める 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){ int h=hfunc(H, key); return H.T[h]->head; } void hash_insert(hash H, slobj obj){ int h=hfunc(H, obj->key); slist_insert_tail(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; }

こちらのコードだと、例えば

4 coffee コーヒー milk 牛乳 water 水 milkcoffee ミルクコーヒー 5 mizu milk coffe milkcoffee sake

のような比較的小さめなインプットだと正しい結果が出るのですが、それに対して

1021 hq め meayl かヨはみカヘ cvscxggb まねとそカらほ fnf ンホろトこ jprep うかフハホ vy ンてうすぬのて cqpev ム ffmznim テヲちりロちコ (中略) 992 jdysejw hit gqlakd xxy dburfwkbk xwpw aucltz (中略)

のような長いインプットだと、間違ったkeyに対応する見出しが何個か出力されてしまい、正しく動作しないようです。

 自分で調べててみたところ、どうもハッシュ関数を改良したほうがよさそうなので、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){ //keyと一致するような要素を同じスロットにあるリストから探索していきます 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; }

例えば、ハッシュ関数が常に1を出力するよう変更し、

3 coffee コーヒー milk 牛乳 water 水 2 milk coffee

という入力にした場合、

milk 牛乳 coffee コーヒー milk 牛乳 coffee コーヒー milk 牛乳 coffee コーヒー ・ ・ ・

が延々と続いてしまうのです!!!!!

編集2:
ごめんなさい、よく考えたらr=hash_search(H, s);→slist_insert_tail(L, r);のときは次のリストの要素を指すポインタもそのままコピーされるのですから、そりゃ無限ループになりますよね、、、

もう少し考えます

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

まだ回答がついていません

会員登録して回答してみよう

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

ハッシュマップ

ハッシュ関数を用いてキーを関連する値にマッピングするデータ構造です。

関数

関数(ファンクション・メソッド・サブルーチンとも呼ばれる)は、はプログラムのコードの一部であり、ある特定のタスクを処理するように設計されたものです。

ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。