C言語-ハッシュ法

C言語アルゴリズム-ハッシュ法

6 ハッシュ法(hashing)

6.1　ハッシュ法

　データxを0 <= h(x) < Mの範囲のなるべく一様に分布する整数に変換する関数h(x)をハッシュ関数という。簡単なハッシュ関数としては、データxを整数化して、Mで割り、その余りを関数値とする。

　例　文字データA,B,C,1,2,3,AAAをハッシュテーブルに格納する。

①　データ個数分の配列t(7個)を用意する。
Hash
②　データAを整数化する。Aの文字コード65(0x41)を利用し、ハッシュテーブル(配列)の個数で割った余りを求める。
　　　　余り=2
③　求めた余りを配列の添字にして格納する。
Hash
④　同様にデータ2までの余りを求めると次のようになるので、該当する配列に格納していく。
　　　　B:3, C:4, 1:0, 2:1
Hash
⑤　データ3の余りは2となり、t(2)にはすでにデータAが格納されており、これを衝突という。
　　このような場合は、適当な計算式(例えば、配列数-余り)を用意しておいて再計算するようにする。
　　　　7-2=5
Hash
⑥　データAAAの場合は、文字コードをすべて加算して整数化する。
　　　　65+65+65=195 195/7=27･･･6
Hash

　データを検索する場合も同じ計算方法でハッシュテーブルの場所を求めることでデータが得られる。
　実際には、データ個数より大きいハッシュテーブル(配列t(M))を用意し、その配列へ登録していく。
　まず、登録データからhash1を求め、配列t(hash1)が空なら登録し、空でなければhash2を求め、(hash1 + hash2 * 2) mod M, (hash1 + hash2 * 3) mod M, ･････のようにして空の配列(ハッシュテーブル)を探して登録する。
　このときMを素数にしておくとデータのばらつきが良くなり、衝突が少なくなる。

6.2 素数 (prime number, primes)

　正の約数を2個(1と自分自身)しか持たない2以上の整数を素数といい､素数でない2以上の整数を合成数という｡合成数は､素数の積に分解できる(素因数分解)｡

入力したデータ以下の最大の素数を計算する。[prime.c]

 1:
 2:
 3:
 4:
 5:
 6:
 7:
 8:
 9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int     primes(int);
    char    indata[80];

    printf("入力データ以下の最大の素数を計算する。\n\n");
    printf("数値データ(%dByte) > ", sizeof(int));
    gets(indata);
    printf("最大の素数は %d です。\n\n", primes(atoi(indata)));
}

int primes(int max)
{
    int     m, i;
    for(m = max; m >= 2; --m){
        /* max/2以下の値で割り切れるかどうかを調べる */
        for(i = max / 2; i >= 2; --i){
            if(m % i == 0)
                break;
        }
        /* max/2以下の値で割り切れなかった */
        if(i == 1)
            break;
    }
    return(m);
}

実行結果
入力データ以下の最大の素数を計算する。数値データ(2Byte) > 300 最大の素数は 293 です。

入力した文字列データをハッシュテーブルに格納する。[hashing1.c]

 1:
 2:
 3:
 4:
 5:
 6:
 7:
 8:
 9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

int hashsize;           /*ハッシュテーブルサイズ */
char    t[100][21];     /* ハッシュテーブル */

int hashing(char *);    /* ハッシュテーブルへ登録 */
int hash1(char *);      /* ハッシュ関数1 */
int hash2(int);         /* ハッシュ関数2 */
int primes(int);        /* 素数計算 */

int main(void)
{
    char    buff[80];
    int     i, cnt, cntmax = 1;

    hashsize = primes(100);     /* 100以下の最大の素数を計算 */
    printf("Hash Size=%d\n", hashsize);
    while(1){                   /* ハッシュテーブルへの登録 */
        printf("文字列データ(MAX=20) : ");
        gets(buff);
        if(!strcmp(buff, "end"))
            break;
        cnt = hashing(buff);
        if(cnt > cntmax)         /* 最大衝突回数 */
            cntmax = cnt;
    }
    printf("ハッシュ関数最大再計算回数 = %d\n", cntmax);
    printf("Return key\n");
    gets(buff);
    for(i = 0; i <= hashsize; ++i){ /* ハッシュテーブル格納状況表示 */
        if(t[i][0] == '\0')
            printf("0 ");
        else
            printf("1 ");
    }
    printf("\nReturn key\n");
    gets(buff);
    for(i = 0; i <= hashsize; ++i){ /* ハッシュテーブル内容表示 */
        if(t[i][0] == '\0')
            printf(". ");
        else
            printf("%s ", t[i]);
    }
}
int hashing(char *key)
{
    int     h, h1, h2 = 0;
    int     cnt = 1;        /* 衝突回数 */

    h1 = hash1(key);        /* ハッシュ関数1値計算 */
    while(1){
        h = (h1 + h2 * cnt) % hashsize;   /* ハッシュテーブル番号計算 */
        if(t[h][0] == '\0'){              /* 登録 */
            strcpy(t[h], key);
            break;
        }
        h2 = hash2(h1);                   /* ハッシュ関数値再計算 */
        ++cnt;                            /* 衝突回数カウント */
    }
    --cnt;
    printf("データ=%-12s  ハッシュ値=%3d  衝突回数=%4d\n", key, h, cnt);
    return(cnt);
}
int hash1(char *s)
{
    int     x = 0;

    do{
        x = (x * 0x60 + *s - 0x20) % hashsize;
    }while(*++s);
    return(x);
}
int hash2(int h1)
{
    if(h1 == 0)
        return(1);
    else
        return(hashsize - h1);
}
int primes(int max)
{
    int     m, i;
    for(m = max; m >= 2; --m){
        for(i = max / 2; i >= 2; --i){
            if(m % i == 0)
                break;
        }
        if(i == 1)
            break;
    }
    return(m);
}

　7行目でハッシュテーブルを100個用意している。各テーブルには、最大20文字まで格納することができる。外部変数として宣言することで、このファイルのすべての関数からアクセスできるようにしている。
　19行目では、100以下の最大の素数を計算し、その値を実際のハッシュテーブルのサイズとしている。
　31～46行目は、ハッシュテーブルへの格納状況を表示しているだけである。
　72行目で最初のハッシュ関数値の計算をしている。

(x * 0x60 + *s - 0x20) *s : 文字コード

　この部分は、適当に変更しても良い。実際には、格納するデータにあわせて計算式を調整する方がよい。

【！！注意！！】
　用意したハッシュテーブルのサイズを越えてデータを格納するとハッシュ関数の再計算が無限に繰り返されるので注意すること。テーブルサイズを越えたときエラーとして終了する処理を追加する方がよい。