自分のhash算法に対する理解は正しいかどうか、皆さんにお伺いしたいのです。
例えば 下記の例では左の文字列はキーで、右はキーで索引しようとするvalueとします
キー abcd : 123
キー abcdef : ABCDF
キー xcvbdfgdf : 9800
キー GBA : X11V777
のようなキーセットが予め指定された場合、hash算法はこのキーのセットに対して総合処理して
それぞれのキーを順番値0,1,2,3へのmaping規則を決めます。
abcd ---> 0
abcdef ---> 1
xcvbdfgdf ---> 2
GBA ---> 3
すると、以降は
例えば、キーとしての文字列"abcd"を上記maping規則で直に0に変換され、value 保存アドレスのindexになります。
これで非常に高速検索できるようになります。
上記考え方は正しいかどうか
ご指摘頂ければ幸いです。
hash算法に対する理解
Re: hash算法に対する理解
https://ja.wikipedia.org/wiki/%E3%83%8F ... 2%E6%95%B0
ハッシュ関数 (ハッシュかんすう、英: hash function) - Wikipedia(ja)
>それぞれのキーを順番値0,1,2,3へのmaping規則を決めます。
順番値 ? は、出てこない。
ハッシュ関数 (ハッシュかんすう、英: hash function) - Wikipedia(ja)
>それぞれのキーを順番値0,1,2,3へのmaping規則を決めます。
順番値 ? は、出てこない。
VTuber:
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。
中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。
中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。
Re: hash算法に対する理解
「キーのセットに対して総合処理してmaping規則を決める」なんてことはしないと思います。
自分の理解では、ハッシュ関数はキーを配列の要素数などの定義域の値の中の(被りにくい)適当な値に(高速に)変換します。
すなわち、ハッシュ関数自体がmaping規則です。
abcd ---> 489
abcdef ---> 26
xcvbdfgdf ---> 817
GBA ---> 95
のような感じ。
この値を用いることで、保存用の配列全体を見ず、指定された値を添字としてそこだけ見に行けばいいので、高速に検索できます。
自分の理解では、ハッシュ関数はキーを配列の要素数などの定義域の値の中の(被りにくい)適当な値に(高速に)変換します。
すなわち、ハッシュ関数自体がmaping規則です。
abcd ---> 489
abcdef ---> 26
xcvbdfgdf ---> 817
GBA ---> 95
のような感じ。
この値を用いることで、保存用の配列全体を見ず、指定された値を添字としてそこだけ見に行けばいいので、高速に検索できます。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: hash算法に対する理解
key と value のセットが 100個あったとします。
登録順に並んでいたら、検索のとき先頭から順番に見ていかないと
いけないので時間がかかります。
登録時にソートしておけば、二分探索により少ない回数の比較で
検索ができます。
ハッシュ関数を使うと、ほぼ 1発で value が見つかります。
ダメな場合でも、2, 3回の比較で済みます。
実際のコードで見たほうが分かりやすいでしょう。
実行例
登録順に並んでいたら、検索のとき先頭から順番に見ていかないと
いけないので時間がかかります。
登録時にソートしておけば、二分探索により少ない回数の比較で
検索ができます。
ハッシュ関数を使うと、ほぼ 1発で value が見つかります。
ダメな場合でも、2, 3回の比較で済みます。
実際のコードで見たほうが分かりやすいでしょう。
#include <stdio.h> // scanf, printf, puts
#include <stdlib.h> // malloc
#include <string.h> // strcmp, strdup
#define NHASH 999
#define MUL 37
typedef struct KV {
char *key, *val;
struct KV *next;
} KV;
KV *table[NHASH];
unsigned hash(const char *key)k
{
unsigned char *p = (unsigned char *)key;
unsigned h = 0;
while (*p) h = h * MUL + *p++;
return h % NHASH;
}
KV *lookup(const char *key, const char *val, int reg)
{
unsigned h = hash(key);
KV *p;
printf("DEBUG: hash('%s') = %u\n", key, h);
for (p = table[h]; p; p = p->next)
if (!strcmp(key, p->key)) return p;
if (reg) {
p = malloc(sizeof(KV));
p->key = strdup(key);
p->val = strdup(val);
p->next = table[h];
table[h] = p;
}
return p;
}
int main(void)
{
KV *p;
char key[100];
lookup("abcd", "123", 1); // 登録 reg = 1
lookup("abcdef", "aBCDEF", 1); // 登録 reg = 1
lookup("xcvbdfgdf", "9800", 1); // 登録 reg = 1
lookup("GBA", "X11V777", 1); // 登録 reg = 1
while (printf("key: "), scanf("%99s", key) == 1 && *key != '.') {
p = lookup(key, NULL, 0); // 検索 reg = 0
if (p) printf(" %s\n", p->val);
else puts(" not found");
}
}
Re: hash算法に対する理解
余りいい加減なことは言わないでほしい。かずま さんが書きました:ハッシュ関数を使うと、ほぼ 1発で value が見つかります。
ダメな場合でも、2, 3回の比較で済みます。
衝突の可能性はキーの数・性質/ハッシュテーブルの大きさ/ハッシュ関数の質に依存するので一概にはいえないはず。
衝突時の処理もハッシュアルゴリズム自体とは無関係。2, 3回の比較で済むかどうかはその方式による。
Re: hash算法に対する理解
maru さんのコメントは素晴らしく、非常に勉強になりました。
そのコメントの内容をしっかり覚えたいのです。
でも、かずま さんがおっしゃったのは「理想な場合」かなと思います。
かずま さんにも感謝します。
そのコメントの内容をしっかり覚えたいのです。
でも、かずま さんがおっしゃったのは「理想な場合」かなと思います。
かずま さんにも感謝します。
Re: hash算法に対する理解
皆様
いろいろコメント頂きまして本当に有難うございます。
どっちも啓発的です!
特にかずま様がわざわざサンプルコードを組んでくださって、hashに関する理解を深めました。
それに、かずま様から頂いたサンプルコードは実に完璧なものです----ほんとうに吟味に値します。
自分がこれまでhash値衝突したらどうなるの?という疑問がありましたが、
概念的に解決法は一応知っているようなものの、具体的なソリューションが知りませんでした。
かずま様のサンプルコードを見て、hashに対して、概念的にも、実現法に関しても、随分分かるような気がします。
忘れないために、自分がサンプルコードの一部に対する理解を加えておきたいのです。
不適切な処があれば、是非ご指摘頂きたいと思います。
またどうぞ宜しくお願い致します。
いろいろコメント頂きまして本当に有難うございます。
どっちも啓発的です!
特にかずま様がわざわざサンプルコードを組んでくださって、hashに関する理解を深めました。
それに、かずま様から頂いたサンプルコードは実に完璧なものです----ほんとうに吟味に値します。
自分がこれまでhash値衝突したらどうなるの?という疑問がありましたが、
概念的に解決法は一応知っているようなものの、具体的なソリューションが知りませんでした。
かずま様のサンプルコードを見て、hashに対して、概念的にも、実現法に関しても、随分分かるような気がします。
忘れないために、自分がサンプルコードの一部に対する理解を加えておきたいのです。
不適切な処があれば、是非ご指摘頂きたいと思います。
KV *lookup(const char *key, const char *val, int reg)
{
unsigned h = hash(key);
KV *p;
printf("DEBUG: hash('%s') = %u\n", key, h);
for (p = table[h]; p; p = p->next)// ★検索目的か登録目的を問わずこのループを実行する:登録の場合、キーが重複に現れたら、これで終わり---再度登録しない。
if (!strcmp(key, p->key)) return p; // 検索成功!
if (reg) {
p = malloc(sizeof(KV));
p->key = strdup(key);
p->val = strdup(val);
//↓ 衝突対策:同じhash code がすでに生成・利用されている可能性を考え、それに対応するデータpointerの保管場所をnextに移転。
p->next = table[h]; //hがこれまで利用されていない場合、table[h]==NULLであり、nextないという意味。
//↑この実装ではtable[..]はglobal memoryなので、NULLで初期化するのは不要だが、table[..]が動的に取得したメモリなら、必ず事前NULL初期化必要!
table[h] = p;
}
return p;// 検索失敗の時、pの値=NULL
}
Re: hash算法に対する理解
いい加減なことを書いたつもりはありません。maru さんが書きました: 余りいい加減なことは言わないでほしい。
衝突の可能性はキーの数・性質/ハッシュテーブルの大きさ/ハッシュ関数の質に依存するので一概にはいえないはず。
衝突時の処理もハッシュアルゴリズム自体とは無関係。2, 3回の比較で済むかどうかはその方式による。
「ハッシュ関数を使えば、どんな場合でも 4回以上の比較を
行わなうことはない」と誤読されたようですが、
私は、回答の先頭で、
「key と value のセットが 100個あったとします。」と書き、
「実際のコードで見たほうが分かりやすいでしょう。」と書いて、
そのコードを提示しました。
キーの数は 100。ハッシュテーブルのサイズは 999、
ハッシュ関数も通常の文字列について、ハッシュ値が
ばらけるように適切なものにしています。
実際にどの程度衝突が起こるか見てみましょう。
乱数で、a~z が 3~8文字になるものをキーとしています。
#include <stdio.h> // printf
#include <stdlib.h> // malloc, srand, rand
#include <string.h> // strcmp, strdup
#include <time.h> // time
#define NKEY 100
#define NHASH 999
#define MUL 37
typedef struct KV {
char *key, *val;
struct KV *next;
} KV;
KV *table[NHASH];
int count[NHASH];
int count2[NHASH];
unsigned hash(const char *key)
{
unsigned char *p = (unsigned char *)key;
unsigned h = 0;
while (*p) h = h * MUL + *p++;
return h % NHASH;
}
KV *lookup(const char *key, const char *val, int reg)
{
unsigned h = hash(key);
KV *p;
printf("DEBUG: hash('%s') = %u\n", key, h);
count[h]++;
for (p = table[h]; p; p = p->next)
if (!strcmp(key, p->key)) return p;
if (reg) {
p = malloc(sizeof(KV));
p->key = strdup(key);
p->val = strdup(val);
p->next = table[h];
table[h] = p;
}
return p;
}
int main(void)
{
KV *p;
char key[100];
srand(time(0));
for (int j, i = 0; i < NKEY; i++) {
int n = rand() % 6 + 3;
for (j = 0; j < n; j++)
key[j] = rand() % 26 + 'a';
key[j] = '\0';
lookup(key, key, 1);
}
for (int i = 0; i < NHASH; i++)
count2[count[i]]++;
for (int i = 0; i < 20; i++)
printf("%3d: %d\n", i, count2[i]);
}
DEBUG: hash('bpjjlssj') = 822
DEBUG: hash('wohtk') = 440
DEBUG: hash('eiof') = 176
DEBUG: hash('dmydn') = 36
DEBUG: hash('mfrxv') = 599
DEBUG: hash('yznc') = 506
DEBUG: hash('ynhlqj') = 240
DEBUG: hash('mlnlb') = 875
DEBUG: hash('jwov') = 895
(中略)
DEBUG: hash('dpbupsps') = 301
DEBUG: hash('okmn') = 887
DEBUG: hash('lqpq') = 113
DEBUG: hash('rppjrgd') = 764
0: 908
1: 83
2: 7
3: 1
4: 0
5: 0
6: 0
7: 0
(以下略)
衝突なしが 83回、2つが衝突するのが 7回、3つが 1回です。
83 + 2 x 7 + 3 x 1 = 100。これで全部です。
何度も実行してみると分かりますが、3つが衝突するのは稀です。
もちろん 4つが衝突することもないわけではありません。
キーの数を 200 や 300 にしてもあまり変わりません。
さすがに 500 にすると、5つが衝突することもあります。
ソースを提示したことにより、それを理解すれば、
衝突回数がサイズにより変わることは自明です。
ハッシュ関数の質ですが、
例えば、すべての文字を足し合わせるものにすると、
"abc", "acb", "bac", "bca", "cab", "cba" が同じハッシュ値
になって、それはダメなハッシュ関数となるでしょう。
Re: hash算法に対する理解
誤読したわけではありません。一般論を書いただけです。かずま さんが書きました:いい加減なことを書いたつもりはありません。maru さんが書きました: 余りいい加減なことは言わないでほしい。
衝突の可能性はキーの数・性質/ハッシュテーブルの大きさ/ハッシュ関数の質に依存するので一概にはいえないはず。
衝突時の処理もハッシュアルゴリズム自体とは無関係。2, 3回の比較で済むかどうかはその方式による。
「ハッシュ関数を使えば、どんな場合でも 4回以上の比較を
行わなうことはない」と誤読されたようですが、
私は、回答の先頭で、
「key と value のセットが 100個あったとします。」と書き、
「実際のコードで見たほうが分かりやすいでしょう。」と書いて、
そのコードを提示しました。
キーの数は 100。ハッシュテーブルのサイズは 999、
ハッシュ関数も通常の文字列について、ハッシュ値が
ばらけるように適切なものにしています。
かずまさんが記述した条件ではほとんど衝突しないことは確認するまでもありません。
ただ、この条件はかずまさんが設定したものであり、質問主であるNBCさんが提示したものではありませんよね。
自分の設定した条件で、アルゴリズムの性質を決めつけるのはどうかと思っただけです。
Re: hash算法に対する理解
hash mappingは奥深いですね。
自分はこれからさらに勉強したいと思います。
特にneural networkで衝突の少ないmapping生成できるのではと思い、勉強したいのです。
皆さん どうも有難うございました。
自分はこれからさらに勉強したいと思います。
特にneural networkで衝突の少ないmapping生成できるのではと思い、勉強したいのです。
皆さん どうも有難うございました。