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