hash算法に対する理解

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
NBC

hash算法に対する理解

#1

投稿記事 by NBC » 3ヶ月前

自分の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になります。
これで非常に高速検索できるようになります。

上記考え方は正しいかどうか
ご指摘頂ければ幸いです。

アバター
あたっしゅ
記事: 149
登録日時: 7年前
住所: 東京23区
連絡を取る:

Re: hash算法に対する理解

#2

投稿記事 by あたっしゅ » 3ヶ月前

https://ja.wikipedia.org/wiki/%E3%83%8F ... 2%E6%95%B0
ハッシュ関数 (ハッシュかんすう、英: hash function) - Wikipedia(ja)

>それぞれのキーを順番値0,1,2,3へのmaping規則を決めます。

順番値 ? は、出てこない。
手提鞄あたっしゅ、[MrAtassyu]

アバター
みけCAT
記事: 6012
登録日時: 7年前
住所: 千葉県
連絡を取る:

Re: hash算法に対する理解

#3

投稿記事 by みけCAT » 3ヶ月前

「キーのセットに対して総合処理してmaping規則を決める」なんてことはしないと思います。
自分の理解では、ハッシュ関数はキーを配列の要素数などの定義域の値の中の(被りにくい)適当な値に(高速に)変換します。
すなわち、ハッシュ関数自体がmaping規則です。
abcd  ---> 489
abcdef ---> 26
xcvbdfgdf ---> 817
GBA ---> 95
のような感じ。
この値を用いることで、保存用の配列全体を見ず、指定された値を添字としてそこだけ見に行けばいいので、高速に検索できます。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

かずま

Re: hash算法に対する理解

#4

投稿記事 by かずま » 3ヶ月前

key と value のセットが 100個あったとします。

登録順に並んでいたら、検索のとき先頭から順番に見ていかないと
いけないので時間がかかります。

登録時にソートしておけば、二分探索により少ない回数の比較で
検索ができます。

ハッシュ関数を使うと、ほぼ 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");
    }
}
実行例

コード:

DEBUG: hash('abcd') = 322
DEBUG: hash('abcdef') = 539
DEBUG: hash('xcvbdfgdf') = 286
DEBUG: hash('GBA') = 805
key: abcd
DEBUG: hash('abcd') = 322
 123
key: gba
DEBUG: hash('gba') = 874
 not found
key: xcvbdfgdf
DEBUG: hash('xcvbdfgdf') = 286
 9800
key: .

maru
記事: 134
登録日時: 7年前

Re: hash算法に対する理解

#5

投稿記事 by maru » 3ヶ月前

かずま さんが書きました:ハッシュ関数を使うと、ほぼ 1発で value が見つかります。
ダメな場合でも、2, 3回の比較で済みます。
余りいい加減なことは言わないでほしい。
衝突の可能性はキーの数・性質/ハッシュテーブルの大きさ/ハッシュ関数の質に依存するので一概にはいえないはず。
衝突時の処理もハッシュアルゴリズム自体とは無関係。2, 3回の比較で済むかどうかはその方式による。

NBC

Re: hash算法に対する理解

#6

投稿記事 by NBC » 3ヶ月前

maru さんのコメントは素晴らしく、非常に勉強になりました。
そのコメントの内容をしっかり覚えたいのです。

でも、かずま さんがおっしゃったのは「理想な場合」かなと思います。
かずま さんにも感謝します。

NBC

Re: hash算法に対する理解

#7

投稿記事 by NBC » 3ヶ月前

皆様 
いろいろコメント頂きまして本当に有難うございます。
どっちも啓発的です!

特にかずま様がわざわざサンプルコードを組んでくださって、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算法に対する理解

#8

投稿記事 by かずま » 3ヶ月前

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" が同じハッシュ値
になって、それはダメなハッシュ関数となるでしょう。

maru
記事: 134
登録日時: 7年前

Re: hash算法に対する理解

#9

投稿記事 by maru » 3ヶ月前

かずま さんが書きました:
maru さんが書きました: 余りいい加減なことは言わないでほしい。
衝突の可能性はキーの数・性質/ハッシュテーブルの大きさ/ハッシュ関数の質に依存するので一概にはいえないはず。
衝突時の処理もハッシュアルゴリズム自体とは無関係。2, 3回の比較で済むかどうかはその方式による。
いい加減なことを書いたつもりはありません。

「ハッシュ関数を使えば、どんな場合でも 4回以上の比較を
行わなうことはない」と誤読されたようですが、
私は、回答の先頭で、
「key と value のセットが 100個あったとします。」と書き、
「実際のコードで見たほうが分かりやすいでしょう。」と書いて、
そのコードを提示しました。

キーの数は 100。ハッシュテーブルのサイズは 999、
ハッシュ関数も通常の文字列について、ハッシュ値が
ばらけるように適切なものにしています。
誤読したわけではありません。一般論を書いただけです。
かずまさんが記述した条件ではほとんど衝突しないことは確認するまでもありません。
ただ、この条件はかずまさんが設定したものであり、質問主であるNBCさんが提示したものではありませんよね。
自分の設定した条件で、アルゴリズムの性質を決めつけるのはどうかと思っただけです。

NBC

Re: hash算法に対する理解

#10

投稿記事 by NBC » 3ヶ月前

hash mappingは奥深いですね。
自分はこれからさらに勉強したいと思います。
特にneural networkで衝突の少ないmapping生成できるのではと思い、勉強したいのです。

皆さん どうも有難うございました。

返信

“C言語何でも質問掲示板” へ戻る