C言語　ダブルハッシュ法のハッシュ関数のコードが理解できない

C言語でアルゴリズムを学んでいる初学者です。
ハッシュを使ったアルゴリズムのコードで理解できない部分があり質問です。
問題はこちらです。ALDS1_4_C

##ダブルハッシュ法の生成式がどのような考えを元に作られているのかわからない。
下記のダブルハッシュ法を使ってハッシュ値を生成するコードが理解できないです。

ダブルハッシュ法の解説に
h(k,i) = (h1(k) + i * h2(k)) mod n
のように解説されていますが、このh1,h2の中の式を解説しているものがなくうまく理解ができないです。
この書き方は公式として、覚えてしまった方がよいのでしょうか。

###わからない部分

c
1int hash_func1(int key)
2{
3    return key % HASH_TABLE_LEN;
4}
5
6int hash_func2(int key)
7{
8    /* HASH_TABLE_LENと,HASH_TABLE_LEN - 1は「互いに素」 */
9    /* なぜこの書き方をしているのか、理解できない。プラス１は何？ */
10    return (1 + (key % (HASH_TABLE_LEN - 1)));
11}
12
13int hash_func(int key, int i)
14{
15    return ((hash_func1(key) + i * hash_func2(key)) % HASH_TABLE_LEN);
16}

###全コード

c
1#include <stdio.h>
2#include <string.h>
3
4/* ダブルハッシュ法を使うのでハッシュテーブルのサイズは素数である必要がある */
5#define HASH_TABLE_LEN 1046527
6
7/* Hash_tableash Table */
8/* グローバル宣言:ゼロクリアされているため初期化は不要 */
9static char Hash_table[HASH_TABLE_LEN][13];
10
11/* 文字列から数値に変換 */
12int getChar(char ch)
13{
14    if (ch == 'A')
15        return 1;
16    else if (ch == 'C')
17        return 2;
18    else if (ch == 'G')
19        return 3;
20    else if (ch == 'T')
21        return 4;
22
23    return 0;
24}
25
26/* convert a string into an integer value */
27int getKey(char str[])
28{
29    int str_convert = 0;
30    int p = 1;
31    int str_len = (int)strlen(str);
32
33    for (int i = 0; i < str_len; i++)
34    {
35        str_convert += p * (getChar(str[i]));
36        /* ここで5を乗算しているのは、文字を1から4の数値に置き換えているため */
37        p *= 5;
38    }
39    return str_convert;
40}
41
42int hash_func1(int key)
43{
44    return key % HASH_TABLE_LEN;
45}
46
47int hash_func2(int key)
48{
49    /* HASH_TABLE_LENと,HASH_TABLE_LEN - 1は「互いに素」 */
50    /* なぜこの書き方をしているのか、理解できない。プラス１は何？ */
51    return (1 + (key % (HASH_TABLE_LEN - 1)));
52}
53
54int hash_func(int key, int i)
55{
56    return ((hash_func1(key) + i * hash_func2(key)) % HASH_TABLE_LEN);
57}
58
59int find(char str[])
60{
61    int key, hash_index;
62    key = getKey(str);
63    for (int i = 0;; i++)
64    {
65        hash_index = hash_func(key, i);
66
67        /* 文字列が一致すれば1,値が格納されていなければ0 */
68        if (strcmp(Hash_table[hash_index], str) == 0)
69            return 1;
70        else if (Hash_table[hash_index][0] == '\0')
71            return 0;
72    }
73}
74
75int insert(char str[])
76{
77    int key;
78    int i;
79    int hash_index;
80
81    key = getKey(str);
82
83    for (i = 0;; i++)
84    {
85        hash_index = (hash_func1(key) + i * hash_func2(key)) % HASH_TABLE_LEN;
86        if (strcmp(Hash_table[hash_index], str) == 0)
87            return 1;
88        else if (strlen(Hash_table[hash_index]) == 0)
89        {
90            strcpy(Hash_table[hash_index], str);
91            return 0;
92        }
93    }
94
95    for (i = 0;; i++)
96    {
97        hash_index = (hash_func1(key) + i * hash_func2(key)) % HASH_TABLE_LEN;
98        if (strcmp(Hash_table[hash_index], str) == 0)
99            return 1;
100        else if (strlen(Hash_table[hash_index]) == 0)
101        {
102            strcpy(Hash_table[hash_index], str);
103            return 0;
104        }
105    }
106    return 0;
107}
108
109int main()
110{
111    int i, N;
112    char str[12];
113    char order[7];
114
115    scanf("%d", &N);
116    for (i = 0; i < N; i++)
117    {
118        scanf("%s %s", order, str);
119        if (order[0] == 'i')
120            insert(str);
121        else
122        {
123            if (find(str))
124                printf("yes\n");
125            else
126                printf("no\n");
127        }
128    }
129    return 0;
130}

行動規範の内容に同意します

回答2件

大学の宿題か試験などかと推測しますが、授業での説明などはなかったのでしょうか。

「問題はこちらです」のリンク先は閲覧できませんでした。権限などの問題でしょうか。

さて、ダブルハッシュ法のGoogle検索でたまたま見つけた下記の資料を参照ください。

ハッシュ法アルゴリズム論第5回講義

上記資料のP18「オープンアドレス法」の(1)線形探索を改良したものが(3)ダブルハッシュ法です。

/* なぜこの書き方をしているのか、理解できない。プラス１は何？ */

ダブルハッシュの第2のハッシュ関数の要件はP26に書いてあります。「０が作られることのある関数であってはならない」を満たすために1を足しています。

投稿2020/04/06 09:15

ockeghem

総合スコア11705

Kchan_01

2020/04/06 09:21

リンクを訂正しました。ご指摘ありがとうございます。０が作られてしまうと衝突が回避できたいということですね。理解できました。ありがとうございます。

行動規範の内容に同意します

ベストアンサー

それをしなかったときにどうなるかという考え方をしてみてください。

範囲をひとつ狭め (HASH_TABLE_LEN-1) た上で 1 を足すという操作をしなければ hash_func2 が返す値が 0 になる可能性があり、そうなったら i の値がいくつであっても 0 のままです。やりたいのは最終的にテーブルを全部辿って空いているところを探すということなのですから、 0 が出てきたら無限ループになってしまいますよ。

投稿2020/04/06 09:12

編集2020/04/06 09:14