トップC-Tips > ハッシュ法

ハッシュ法

1.文字列に対するハッシュ関数

自分がよく使うハッシュ関数を下に示す。 実際には、ハッシュサイズ(HASHSIZE) はもっと大きな値を使うが、 ここでは説明のために小さな値としている。

下のプログラムでは、"abs", "atof" など12個の関数名について、 ハッシュ値(ハッシュ関数で得られた値)を求めている。

hash01.c
#include <stdio.h> 

#define HASHSIZE  19
// 素数 ... , 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61
char *func[] = {
    "abs",   "atof",  "atoi",  "atol",  "close", "feof", 
    "fgetc", "fgets", "fopen", "fputc", "fputs", "free"
};

int hash(char *key) {
    int n, h = 0;
    for (n = 0; key[n] != '\0'; n++) {
        h = (h * 137 + key[n]) % HASHSIZE;
    }
    return h;
}

int main() {
    int n;
    printf("HASHSIZE = %d\n", HASHSIZE);
    for (n = 0; n < sizeof(func)/sizeof(char*); n++) {
        printf("%-6s", func[n]);
    }
    printf("\n");
    for (n = 0; n < sizeof(func)/sizeof(char*); n++) {
        printf(" %2d   ", hash(func[n]));
    }
}

実行結果を下に示す。

c:\MH\www\c-tips\data-structure>hash01
HASHSIZE = 19
abs   atof  atoi  atol  close feof  fgetc fgets fopen fputc fputs free
  7     3     6     9    13     7    18    15    11    14    11     3

ハッシュ法による文字列管理では、ハッシュサイズに等しい要素数を持つ配列が用いられる。 例えば "abs" のハッシュ値は7であるから、下図に示すように、 第7番目(先頭が第0番目)の配列要素にそのアドレスが格納される。 "atof"、"atoi" と順に割り当てていく。 "feof" の番になると、第7番目の要素は既に割り当て済みなので、配列の添え字を進めて、 未割り当て要素を探す。 この例では、直ぐ隣が空きであったため、"feof"には第8番目の要素が割り当てられる。 同様に、"fputs"、"free" も本来のハッシュ値とは違う場所が割り当てられる。

ある文字列例えば "feof" が登録されているかどうかを調べるには、 "feof"のハッシュ値が 7 であるから、もし、第7要素が空きであれば、登録されていないことになる。 何らかの文字列が登録されていたら、この文字列と "feof" を比較する。 もし、一致すれば登録されていたことになる。一致しなかった場合、配列の添え字を先に進めて、 ここが空きなら、"feof" は登録されていないことが確定する。 何らかの文字列が登録されていた場合は前と同じ処理を繰り返す。 なお、添え字が配列の末尾まで達したら、 配列の先頭に戻って同じことを行う。

衝突により、本来の場所と異なる位置に登録されることがあるため、 文字列の比較は2回以上になるケースもあるが、衝突がなければ、文字列の比較は精々1回で済む。

以上のように、ハッシュ法は登録処理も検索処理も非常に高速に行われるため、 広く使われる技術である。 ハッシュ表に格納するのは、文字列とは限らず、数値とか構造体データなど、どのようなデータでもよい。

なるべく衝突を減らすためには、ハッシュ表のサイズは、 登録する文字列の個数に比べて、十分に余裕を持たせることが必要である。 また、HASHSIZEはきりのいい数字にせず、素数にした方がよい。 このハッシュ関数では 137 という中途半端な数値が使われているが、 これもなるべく衝突が起こらないようにするためである。

以上述べたことをプログラム化したものを下に示す。

#include <stdio.h> 

#define HASHSIZE  19
char *hashTable[HASHSIZE];

// 素数 ... , 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61
char *func[] = {        // 登録する単語
    "abs",   "atof",  "atoi",  "atol",  "close", "feof", 
    "fgetc", "fgets", "fopen", "fputc", "fputs", "free"
};

char *check[] = {        // チェックする単語
    "strcmp", "atof",  "printf", "free"
};

int hash(char *key) {
    int n, h = 0;
    for (n = 0; key[n] != '\0'; n++) {
        h = (h * 137 + key[n]) % HASHSIZE;
    }
    return h;
}

int put(char *str) {
    int n, h = hash(str);
    for (n = 0; n < HASHSIZE; n++) {
        int ix = (h + n) % HASHSIZE;
        if (hashTable[ix] == NULL) {
            hashTable[ix] = str;        
            return ix;                // 新規登録
        } else if (strcmp(hashTable[ix], str) == 0) {
            return ix;                // 登録済み
        }
    }
    printf("Error: Hash Table Full");
    return -1;
}

int contain(char *str) {
    int n, h = hash(str);
    for (n = 0; n < HASHSIZE; n++) {
        int ix = (h + n) % HASHSIZE;
        if (hashTable[ix] == NULL) {
            return -1;                // 登録なし
        } else if (strcmp(hashTable[ix], str) == 0) {
            return ix;                // 登録済み
        }
    }
    return -1;
}

int main() {
    int n;
    printf("HASHSIZE = %d\n", HASHSIZE);
    for (n = 0; n < sizeof(func)/sizeof(char*); n++) {
        put(func[n]);
    }
    for (n = 0; n < sizeof(check)/sizeof(char*); n++) {
        printf("\"%s\"は登録されて%s\n", 
                check[n], contain(check[n]) >= 0 ? "います" : "いません");
    }
}

実行結果を以下に示す。

c:\MH\www\c-tips\data-structure>hash02
HASHSIZE = 19
"strcmp"は登録されていません
"atof"は登録されています
"printf"は登録されていません
"free"は登録されています

自作ミニC言語コンパイラMCCでは、if, for, int といった予約語や変数名、関数名などをそのまま文字列で扱うのは処理時間がかかるため、 上のput関数で得られた値をID として扱う。 これは、学生の成績などの管理を学生番号で行うのと同じである。

文字列に日本語を含む場合には、int hash(unsigned char *key) とするか、 または h * 137 + key[n]h * 137 + (key[n] & 0xff) に変える。

2.連想メモリ

JavaScriptには言語仕様として連想メモリがあるが、C言語にはない。 これに似た機能として、JavaのHashTableと同等機能はハッシュ法で実現できる。 下にプログラム例を示す。

#include <stdio.h> 

#define HASHSIZE  19

typedef struct _Data {
    char *key;
    char *val;
} Data;

Data *hashTable[HASHSIZE];

Data data[] = {        // 登録データ
    { "one", "ひとつ" },
    { "two", "ふたつ" },
    { "tree", "みっつ" },
    { "four", "よっつ" },
    { "five", "いっつ" }
};

char *test[] = { "tree", "five", "one", "seven" };

int hash(char *key) {
    int n, h = 0;
    for (n = 0; key[n] != '\0'; n++) {
        h = (h * 137 + key[n]) % HASHSIZE;
    }
    return h;
}

int put(Data *data) {
    int n, h = hash(data->key);
    for (n = 0; n < HASHSIZE; n++) {
        int ix = (h + n) % HASHSIZE;
        if (hashTable[ix] == NULL) {
            hashTable[ix] = data;        
            return ix;                // 新規登録
        } else if (strcmp(hashTable[ix]->key, data->key) == 0) {
            return ix;                // 登録済み
        }
    }
    printf("Error: Hash Table Full");
    return -1;
}

char *get(char *key) {
    int n, h = hash(key);
    for (n = 0; n < HASHSIZE; n++) {
        int ix = (h + n) % HASHSIZE;
        if (hashTable[ix] == NULL) {
            return NULL;                // 登録なし
        } else if (strcmp(hashTable[ix]->key, key) == 0) {
            return hashTable[ix]->val;  // 登録あり
        }
    }
    return NULL;
}

int main() {
    int n;
    for (n = 0; n < sizeof(data)/sizeof(Data); n++) {
        put(&data[n]);
    }
    for (n = 0; n < sizeof(test)/sizeof(char*); n++) {
        printf("\"%s\" → \"%s\"\n", test[n], get(test[n]));
    }
}
c:\MH\www\c-tips\data-structure>hash03
"tree" → "みっつ"
"five" → "いっつ"
"one" → "ひとつ"
"seven" → "(null)"

3.ハッシュ表の拡大について

ハッシュ表への登録数が予測できないことがある。 このような場合、ハッシュ表に余裕が少なくなってきたら、 ハッシュ表を拡大して、登録をやり直す。 この結果、これまでに登録されていたものの場所も変わるため、 ハッシュ配列の添え字を直接、IDとすることはできない。 (例えば、登録順に通し番号をIDとする。余分に管理テーブルが必要となる。) 登録の有無をチェックする関数や、連想メモリ風に使うget関数では、 これらの関数の外で、ハッシュ配列の添え字を使うわけではないので、 問題はない。

ハッシュ表の空きが少なくなったら、自動的に、配列サイズを拡大するプログラム例を下に示す。 占有率が 2/3 を超えたら、サイズを 3/2 倍にしている。

// hash04.c 2012-07-17  Hatada
#include <stdio.h> 
#include <stdlib.h> 

typedef struct _Data {
    char *key;
    void *val;
} Data;

Data *hashTable;
int HASHSIZE;
int entries;

void allocHash(int size) {
    HASHSIZE = size;
    hashTable = calloc(HASHSIZE, sizeof(Data));
    entries = 0;
}

void reallocHash(int newSize) {
    printf("reallocHash: %d -> %d [%d]\n", HASHSIZE, newSize, entries);
    Data *oldTable = hashTable;
    int oldSize = HASHSIZE;
    allocHash(newSize);
    int n;
    for (n = 0; n < oldSize; n++) {
        if (oldTable[n].key != NULL)
            put(oldTable[n].key, oldTable[n].val);
    }
    free(oldTable);
}

int hash(char *key) {
    int n, h = 0;
    for (n = 0; key[n] != '\0'; n++) {
        h = (h * 137 + (key[n]&0xff)) % HASHSIZE;
    }
    return h;
}

int put(char *key, void *val) {
    int n, h = hash(key);
    for (n = 0; n < HASHSIZE; n++) {
        int ix = (h + n) % HASHSIZE;
        if (hashTable[ix].key == NULL) {
            hashTable[ix].key = key;        
            hashTable[ix].val = val;        
            entries++;
            if (entries * 3 > HASHSIZE * 2)
                reallocHash(HASHSIZE * 3 / 2);
            return ix;                // 新規登録
        } else if (strcmp(hashTable[ix].key, key) == 0) {
            return ix;                // 登録済み
        }
    }
    printf("Error: Hash Table Full");
    return -1;
}

void *get(char *key) {
    int n, h = hash(key);
    for (n = 0; n < HASHSIZE; n++) {
        int ix = (h + n) % HASHSIZE;
        if (hashTable[ix].key == NULL) {
            return NULL;                // 登録なし
        } else if (strcmp(hashTable[ix].key, key) == 0) {
            return hashTable[ix].val;   // 登録あり
        }
    }
    return NULL;
}

int main() {
    allocHash(2);
    put("1", "one");
    put("2", "two");
    put("3", "three");
    put("4", "four");
    put("5", "five");
    printf("4->%s\n", get("4"));
    printf("2->%s\n", get("2"));
    printf("1->%s\n", get("1"));
    printf("5->%s\n", get("5"));
    printf("3->%s\n", get("3"));
}

このプログラムの実行結果を下に示す。

c:\MH\www\c-tips\data-structure>hash04
reallocHash: 2 -> 3 [2]
reallocHash: 3 -> 4 [3]
reallocHash: 4 -> 6 [3]
reallocHash: 6 -> 9 [5]
4->four
2->two
1->one
5->five
3->three

4.ライブラリ関数化

これまでに述べたプログラムでは、独立したハッシュ表を同時に複数使用することはできない。 ハッシュ関数を自前のライブラリ関数風に使えるようにするには、構造体を導入し、 hash, put, get関数に次のように引数を追加する必要がある。 インタフェースの一例を下に示す。 ハッシュ表に関わる変数を構造体HASHに包み込む形となる。

typedef struct _Data { 
    char *key; 
    void *val;
} Data;

typedef struct _HASH {
    Data *hashTable;
    int   type;
    int   size, entries;        // サイズ、登録数
} HASH;

void allocHash(int type, int size, HASH *pHash);
void reallocHash(int newSize, HASH *pHash);     // 内部関数
void freeHash(HASH *pHash);
int  hash(char *key, int size);                 // 内部関数
int  put(char *key, void *val, HASH *pHash);
void *get(char *key, HASH *pHash);