STEP 2.3 (ハッシュ法の基礎）

<問題> ５けたの数 a1a2a3a4a5 (たとえば 67891 ならa1 = 6, a3= 8, a5=1ということ）を、ハッシュ法を用いて配列に格納する。
ハッシュ関数を mod (a1+a2+a3+a4+a5, 23) とし、求めたハッシュ値に対応する位置の配列要素に格納する。

control z (UNIXでは control d ) が入力されるまで5けたのデータを受け付け、配列のどこに格納したのかを示せ。ただし、ハッシュ値が衝突した（かち合いを起こした）場合は、格納しなくてよい。


<実行結果>　

67891(←　入力）
data[8] = 67891（←　格納情報)
1094
data[14] = 1094
55550
data[20] = 55550
54321
data[15] = 54321
5822
data[17] = 5822
3
data[3] = 3
34
data[7] = 34
4631
衝突 (collision) : hash key of 4631  = 14, data[14] is 1094 (← 4631を data[14]には格納できない。衝突の際の処理は、別に作る）

(ここで、control z。すると、配列を一覧）

data[0] = 0
data[1] = 0
data[2] = 0
data[3] = 3
data[4] = 0
data[5] = 0
data[6] = 0
data[7] = 34
data[8] = 67891
data[9] = 0
data[10] = 0
data[11] = 0
data[12] = 0
data[13] = 0
data[14] = 1094
data[15] = 54321
data[16] = 0
data[17] = 5822
data[18] = 0
data[19] = 0
data[20] = 55550
data[21] = 0
data[22] = 0 

<背景>

• 検索する時に一発で見つけられるよう、前もってデータをうまく格納しておく作戦。ハッシュ関数により、配列の位置を対応づける。（ハッシュ関数により作られるデータの格納テーブルのことを、ハッシュ表という）
  • さまざまな関数が考えられるが、上の例では、23で割った余り。
  • ハッシュ関数が同じ値をとると、衝突（かちあい）が起こる。データの性質に応じて、衝突（かちあい）がおきない関数を用意できるかどうかが問題
    • 衝突を起こすデータについて、先のデータをホーム、後のデータをシノニムとよぶ。上の実行例では、1094がホーム、4631がシノニム。
  • 衝突を避けるため、ハッシュ関数は、データを、偏らずに（一様に）対応づけできる（ハッシュ値が散らばる）一様関数の性質をもつものがよい。
  • 衝突が起きた場合の格納手法にも、いろいろな方法が考えられているけれども、今回は、「格納しない」というプログラムとしておく。

<プログラム関係>

• 5の文字の列をうけとって、操作。1文字は1バイトのアスキーコード。Cの絵本p187。よくわかるC p69。0が48, 9が57。だから、'0'を引き算すると、1桁の整数値が得られる（いろいろな例題に出てくる定番手法）
• 5つの文字の列を、1つの整数に変換するには、atoi。Ｃの絵本 p69

解答例

#include <stdio.h>
#include <stdlib.h> /* atoiを使う */

#define D 6  /* 5文字(5桁) + \0 */
#define N 23 /* 格納用配列のサイズ */

int main(void) {
    char s[D];  /* D桁の数を、D文字の列としてうけとるための変数 */
    int data[N]; /* N 23で割った余りをハッシュ関数とすると、0-22 */
    int i; /* 配列カウンター用 */
    int k;  /* 計算値 */
    int hk; /* ハッシュ関数値 */

    for (i = 0 ; i < N; i ++) /* データ格納用配列初期化 */
        data[i] = 0;

    for (i = 0 ; i < D; i ++) /* 文字列初期化。0でうめる */
        s[i] = 0;               /* D-1桁の入力を確認すべき */

    while (scanf("%s", s) != EOF) { /* Control zで入力終了 */
        i = 0;
        k = 0;

        while (s[i] != '\0') {  /* 各桁の数を足し算する */
            k = k + s[i] - '0'; /* アスキーコードを使った定番の作戦 */
            i++;
        }

        hk = k % N; /* ハッシュ関数は、5桁の数をa1a2a3a4a5とするとき、mod (a1+a2+a3+a4+a5, N) */

        if (data[hk] == 0) {
            data[hk] = atoi(s); /* 文字列を整数へ型変換 "12345"が、12345になる */
            printf ("data[%d] = %d\n", hk, data[hk]); /* 格納 */
        } else {
            printf ("衝突 (collision) : hash key of %s  = %d, data[%d] is %d \n", s, hk, hk, data[hk]); /* 同じハッシュ値を持つ別のデータが格納済 */
        }


        for (i = 0 ; i < D; i ++)  /* 文字列受け取り用変数を、再初期化 */
            s[i] = 0;
    }

    for (i = 0; i < N; i ++) /* 全データの格納終了。格納状況の一覧表示。0は空いている。*/
        printf("data[%d] = %d \n", i, data[i]);

    return 0;

}