- ベストアンサー
初めてのハッシュ関数を理解しよう!
- ハッシュ関数についての基礎知識、計算速度と一様な分布の重要性について説明します。
- ハッシュ関数を使用したサンプルコードの解説と、いくつかの簡単なハッシュ関数の提案を行います。
- ハッシュ関数の選び方についての不安を相談し、適切な選択肢についてアドバイスを求めます。
- みんなの回答 (3)
- 専門家の回答
関連するQ&A
- ハッシュ関数
ハッシュ関数について悩んでいます. ハッシュ関数の例として以下Wikiの引用です http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E9%96%A2%E6%95%B0 unsigned int hash(char *s) { unsigned int h = 0; for (;*s != '\0'; s++) { h = h * 137 + *s; } return h % 1987; } このハッシュ関数において, 「hの更新計算で用いる137という数は、2(7乗)+2(3乗)+2(0乗) というものであり、乗法した後にも2進数表現の下位の桁にも 情報が残るようになっている。そのため前の方の文字の情報が 桁あふれによって失われることはない。」 と記述されているのですが,私が考えてしまうのは以下の通りです. 「最終的にハッシュ値は合計を1987で割った余りになるのだから, 下位の桁(1~1987)に情報を残さなければならない. それぞれのsの上位から下位までの情報を合計の数値の下位に 残すのであれば,137は掛けるのではなく割るべき.」 もちろん私の考え方が間違っているのはわかりますが, なぜ137を掛けるのかを理解できません. どなたかわかりやすくご教授いただけたら幸いです.
- ベストアンサー
- C・C++・C#
- c言語 ハッシュ表
下のハッシュ表のプログラムについて質問です.関数enterを二回呼び出して,valueの値を変更して表示させても値が更新されません.値が更新せれるにはどうすればよいのでしょうか? #include <stdio.h> #include <stdlib.h> #include <string.h> #define HASH_SIZE 997 /* ハッシュ表の内部配列のサイズ */ #define HASH_RADIX 97 /* ハッシュ関数用の基数 */ /* ハッシュ表内の連結リストに含まれるノードの構造体 */ struct hash_node { /* ハッシュ表内の連結リストのノード */ char *key; /* キー */ int value; /* キーに対応する値 */ int id; /* キーに付与された通し番号 */ struct hash_node *next; /* 次のノードへのポインタ */ }; typedef struct hash_node HashNode; typedef HashNode *HashNodePtr; /* ハッシュ表の構造体 */ struct hashtable { HashNodePtr *heads; /* 内部配列 */ int serial_id; /* 通し番号管理用の変数 */ int size; /* 内部配列のサイズ */ }; typedef struct hashtable HashTable; typedef HashTable *HashTablePtr; /* 文字列 s のハッシュ値を計算する */ unsigned int hash(char *s) { unsigned int v; v = 0; while (*s != '\0') { v = v * HASH_RADIX + *s; s++; } return v; } /* ハッシュ表を一つ生成し,そのポインタを返す */ HashTablePtr create_hashtable() { HashTablePtr t = NULL; int i; t = malloc(sizeof(HashTable)); t->serial_id = 0; t->size = HASH_SIZE; t->heads = malloc(sizeof(HashNodePtr) * t->size); /* 各連結リストの先頭要素へのポインタは必ず NULL に初期化する */ for (i = 0; i < t->size; i++) { t->heads[i] = NULL; } return t; } /* 指定したポインタ変数に NULL を代入して終わるためのマクロ */ #define delete_hashtable(t) \ (delete_hashtable0(t),t=NULL) /* 実質的な削除作業を行う関数(free 後の NULL 代入は省略)*/ void delete_hashtable0(HashTablePtr t) { HashNodePtr n = NULL, m = NULL; int i; /* 各連結リストの領域を解放 */ for (i = 0; i < t->size; i++) { n = t->heads[i]; while (n != NULL) { m = n; n = n->next; free(m); } } /* 最後に連結リストの先頭ポインタの領域を解放 */ free(t->heads); free(t); } /* ハッシュ表 t に登録されているキーと値のペアの数を返す */ int get_cardinality(HashTablePtr t) { return t->serial_id; } /* ハッシュ表 t にてキー key に対応する値を調べる */ int lookup(HashTablePtr t, char *key) { HashNodePtr n = NULL; int index; /* ハッシュ表の内部配列の添え字を計算 */ index = hash(key) % t->size; /* index 番目の連結リストを先頭から順に走査 */ n = t->heads[index]; while (n != NULL) { /* 引数で指定された key とハッシュ表内のキーが一致したら 直ちに対応する値を返す */ if (strcmp(key, n->key) == 0) return n->value; /* 走査を次に進める */ n = n->next; } /* ここではキーに対応する値は非負であると仮定し, 見つからなかったら -1 を返す */ return -1; } /* キー key と値 value のペアをハッシュ表 t に登録し,その通し番号を返す */ int enter(HashTablePtr t, char *key, int value) { HashNodePtr n = NULL, m = NULL; int index; index = hash(key) % t->size; /* 内部配列の添え字を計算 */ /* キーが既に存在しているかどうかチェック(lookup() と同じ処理)*/ n = t->heads[index]; while (n != NULL) { if (strcmp(key, n->key) == 0) return n->id; /* 通し番号を返す */ n = n->next; } /* 新しいノードを生成 */ m = malloc(sizeof(HashNode)); m->key = _strdup(key); m->id = t->serial_id; m->value = value; /* 連結リストの add_first() と同様にして連結リストに追加 */ m->next = t->heads[index]; t->heads[index] = m; t->serial_id++; /* 次の通し番号に更新 */ return m->id; /* 登録したキーと値のペアに付与された通し番号を返す */ } /* * ハッシュ表 t に登録されるキーの配列を返す *(この配列のサイズは get_cardinality() で取得可能) */ char **get_keys(HashTablePtr t) { char **keys = NULL; HashNodePtr n = NULL; int i; keys = malloc(sizeof(char *) * t->serial_id); /* 各連結リストを走査し,配列に詰め込む */ for (i = 0; i < t->size; i++) { n = t->heads[i]; while (n != NULL) { keys[n->id] = n->key; /* 通し番号を配列添え字に */ n = n->next; } } return keys; /* 後で free() する必要あり */ } void print_hashtable(HashTablePtr t) { printf("Taro => %d\n", lookup(t, "Taro")); } /* ハッシュ表の使用例 */ int main(void) { HashTablePtr t = NULL; t = create_hashtable(); enter(t, "Taro", 25); print_hashtable(t); enter(t, "Taro", 35); print_hashtable(t); delete_hashtable(t); }
- ベストアンサー
- C・C++・C#
- C言語でポインタを使ってピタゴラスの定理の関数を作りたいです
私は今あるプログラムを書いていて、その過程でどうしても関数を使ってピタゴラスの定理を作りたいのですが、ポインタの渡し方がうまくいきませんでした。ポインタを使わない場合は次の通りでした。 double pythagoras(double a, double b){ double c; c = a*a+b*b; c = sqrt(c); return c; } これはメイン関数で二つの値a,b(int型)をpythagoras関数に入れて、ピタゴラスの定理を適用させてメイン関数にc(double型)を戻り値として返すものです。 しかし2つの値a,bがint型ではなくポインタだとうまくいかないです。どのような関数を作ればいいか分かる人がいたらぜひ教えてください。ちなみに現在a,bは次のように宣言してあります。 struct node { int a; int b struct node *next; };
- 締切済み
- C・C++・C#
- 文字列をハッシュにしなければならないのですが
C言語にさ ファイルの中にある、3バイトunicodeの漢字文字列郡をハッシュテーブルに格納してハッシュを作りたいんですが、取っ掛かりすらつかない状況です。 とりあえず、配列から3バイトの16進数にして、後はその文字列分の16進数を足して、それを割ってキーをつくりテーブルにいれる、としようとしています。 配列から3バイトの16進数にする int joint(char a, char b, char c){ int join = 0; join = a<<8; join = (0x0000FF00 & join) + (0x000000FF & b); join = join<<8; join = (0x00FFFF00 & join) + (0x000000FF & c); return join; } このように16進数にするのですが、最初の取っ掛かりとしてのハッシュについては、どうやったらハッシュテーブルに格納でくるのかいまいちわからないのです。誰かわかりやすく教えてください。
- ベストアンサー
- C・C++・C#
- ハッシュ(オープンアドレス法) C言語の課題
努力はしてみたのですが、C言語の課題ができません。教えていただけないでしょうか。 問:名前と年齢を入力し、名前をキーとしてハッシュ(オープンアドレス法)に登録する。'-'が入力されると登録を終了し、次に入力された名前をハッシュ法で検索し、あればその人のデータをハッシュから削除する、その後、ハッシュ表の内容を出力するプログラムを作成せよ。ただしハッシュ表の大きさは5とする。 例 koizumi 入力 1 入力 fukuda 入力 2 入力 aso 入力 3 入力 - 入力 koizumi 入力 fukuda(2) 出力 aso(3) 出力 ハッシュ関数は int hash(char *name) { int ret=0; while (*name)ret += *name++; return ret%5; } 再ハッシュ関数は int rehash(int h) { return (h+1)%5; } を使おうと考えています。 内容を理解できないと困るので簡単なプログラムをお願いします。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 関数をまとめる
関数をつくるときにどうまとめれば良いのでしょうか? 例えば下のようなプログラムがあったとします. #include<iostream> int add(int, int); int multi(int, int); int main(void) { int a = 4; int b = 3; std::cout << add(a, b) << std::endl; std::cout << multi(a, b) << std::endl; } int add(int a, int b) { return a + b; } int multi(int a, int b) { return a * b; } add関数は足し算の結果,multi関数は掛け算の結果を返します. やっている内容はかわらずわざわざ2つに分ける必要があるか?と思ってしまいます. 要は, int arithmetic_operations(int a, int b, int pattern) { int result; switch(pattern) { case 1: result = a + b; break; case 2: result = a - b; break; case 3: result = a * b; break; case 4: if(0 == b) { exit(1); } result = a / b; break; default: break; } return result; } このような関数を用意してpattern変数で計算を制御するほうがまとまりがあると思います.ですが,いちいち中身を確認しながらプログラムを書く必要があるので可読性は低くなります. どちらがベターでしょうか?
- ベストアンサー
- C・C++・C#
- ハッシュのハッシュのソート
rubyでハッシュのソート方法についてはいくつか情報のサイトを見つけられました。 ですが今やりたいのは、ハッシュのハッシュのソートなのですが、うまいやり方がわかりませんでした。 具体的には、 h1 = {"user1"=>{"a"=>10, "b"=>20, "c"=>30"}, "user2"=>{"d"=>5, "e"=>8}, "user3"=>{"f"=>10, "g"=>5, "h"=>10} } というようなハッシュのハッシュを想定しています。ユーザごとに案件ごとの必要工数(時間)をハッシュとして持たせ、全工数が多いユーザ順にソートしたいのです。 上記の場合だと、 {"user1"=>{"a"=>10, "b"=>20, "c"=>30"}, "user3"=>{"f"=>10, "g"=>5, "h"=>10}, "user2"=>{"d"=>5, "e"=>8} } というようにソートしたいのですが、何かやり方がありましたらご教授いただけますでしょうか。
- ベストアンサー
- Ruby
- 理想的なハッシュ関数
C++での質問です. たとえば以下のようなmyclassクラスがあり, メンバ変数のx,y,ar[10]を使って 0~ 1020 の範囲のハッシュ値を得たいのですが, どうも偏った値しか得られません. できるだけ指定範囲の中で均一に値を生成するような myclass::hush() を作るとしたらどのような計算方法が考えられるでしょうか? ちなみにx,y,ar[10]の整数型変数はいずれも 0~50程度の値です. const int modnum = 1021 ; /* 素数 */ class myclass{ private: int x; int y; int ar[10]; public: int hush(); }; int myclass::hush(){ int sum; /* ここで x, y, ar[10]を使った計算を行う */ sum = /* x, y, ar[10]から導き出した値 */ return sum % modnum; }
- ベストアンサー
- C・C++・C#
お礼
あれっ!? そんな簡単なものでもいいのですか? 状況によってぜんぜんちがうものなんですね。 僕が一回見せてもらったハッシュ関数は何だか4~6行ぐらいあったので、ハッシュ関数って、もっと複雑なものかと……。 とりあえず、他にも色々な記事を読んで理解は深まりました。ありがとうございました。