C言語でハッシュマップを実装してみた【チェイン法】
- 作成日: 2021-12-24
- 更新日: 2023-12-24
- カテゴリ: C言語
C言語でハッシュマップを実装してみた
ハッシュマップとは文字列のキーに対して値をセットできるデータ構造のことです。
文字列のキーからハッシュ値を生成し、そのハッシュ値を使ってテーブルにアクセスします。
計算量的には最良でO(1)で目的の値を取得できるデータ構造で、計算機科学の分野で広く使われています。
プログラミング言語には「ハッシュマップ」とか「辞書」などの名前で、標準ライブラリとして備わっていることが多い言語です。
カーニハン曰く「プログラマが無人島に持って行きたいデータ構造」ということで、プログラマから絶大な人気があります。
今回はこのハッシュマップをC言語で実装してみました。
C言語による実装
まずデータ構造としてはHashMap型の構造体と、HashMapNode型の構造体があります。
typedef struct HashMapNode {
char key[1024];
void *data;
struct HashMapNode *next;
} HashMapNode;
typedef struct {
HashMapNode *table[HASH_MAP__NTABLE];
void (*deleter)(void *);
} HashMap;
HashMapのほうではHashMapNodeのポインタ配列をtableとして定義してあります。
このtableにデータを持ったノードがセットされます。そしてtableはデータの参照でも使われます。
HashMapNode *table[HASH_MAP__NTABLE];
実際にハッシュマップに値をセットする場合、その値はvoid *型に変換されます。
void *は特定の型を持たない抽象化されたポインタです。
こうすることで汎用的なハッシュマップとして使えます。
HashMapNodeのメンバにdataというvoid *型の変数がありますが、これにデータがセットされます。
データのセットにはHashMap_Set()という関数を使います。
HashMap *
HashMap_Set(HashMap *self, const char *key, void *data) {
...
}
HashMap_Set()はデータのセットに成功するとselfを返し、失敗したらNULLを返します。
HashMap_Set()の実装を見てみます。
まず関数の冒頭でkeyのハッシュ値を計算します。
long hash = create_hash(key);
hash %= HASH_MAP__NTABLE;
create_hash()はハッシュ値を計算する関数です。
そのハッシュ値をHASH_MAP__NTABLEで割って余りを出しています。
HASH_MAP__NTABLEはtableのサイズを表す定数です。
create_hash()は非常にシンプルな実装です。
static long
create_hash(const char *s) {
long n = 0;
long weight = 1;
for (const char *p = s; *p; p += 1) {
n += weight * (*p);
weight += 1;
}
return n;
}
create_hash()の仕様は基本的には引数の文字列sを1文字ずつ見て行って、その値をnに加算していくだけです。
このような実装だとたとえばaという文字列からは97というハッシュ値が得られます。
abだと97 + 98で195というハッシュ値を得られます。
この実装だと、たとえばbaという文字列の場合にabと同じハッシュ値が求まります。
そのためこれを防ぐためにweightという変数を加算ごとにインクリメントさせ、その値を文字の値に乗算しています。
こうするとabとbaが違うハッシュ値になります。
ハッシュ値の計算は非常に重要です。
この実装は簡易的なものですが、本格的なハッシュ値を計算しようとする場合はライブラリなどを使う必要があります。
ハッシュ値の精度が低いと、ハッシュ値のコリジョン（衝突）が発生しやすくなります。
コリジョンが発生した場合は、その応答処理を書く必要があります。
これにはチェイン法などが有名です。
今回実装しているハッシュマップはチェイン法を使ってコリジョンを解消しています。
HashMap_Set()に戻りますが、ハッシュ値が求まったらそのハッシュ値のテーブルの要素にアクセスします。
HashMapNode *node = self->table[hash];
if (!node) {
node = HashMapNode_New(key, data, NULL);
if (!node) {
goto error;
}
self->table[hash] = node;
return self;
}
ハッシュの位置のノードがNULLである場合は、つまりその位置には何もノードがセットされていません。
HashMapNode_New()でノードを新しく作成し、そのノードをテーブルのハッシュの位置にセットします。
これで新規のノードの挿入処理は完了です。
HashMapNode_New()ではキーとデータをノードにセットし、そのノードを返します。
動的メモリアロケートを使っています。
HashMapNode *
HashMapNode_New(
const char *key,
void *data,
HashMapNode *next
) {
HashMapNode *self = calloc(1, sizeof(*self));
if (!self) {
return NULL;
}
snprintf(self->key, sizeof self->key, "%s", key);
self->data = data;
self->next = next;
return self;
}
HashMap_Set()に戻ります。
テーブルにノードがすでに存在している場合は、それは上書きかコリジョンのどちらかになります。
コリジョンの場合はノードのnextというメンバに次のノードを繋げていきます。
そのためfor文でノードのリンクを走査して、チェックします。
ノードのキーが被っていたら、それはノードの上書きになります。
deleter()というメモリを解放するコールバック関数でdataを解放して、新しくdataをセットします。
deleterがセットされていない場合はメモリを解放しないため、メモリリークになります。
deleterをセットするにはHashMap_SetDeleter()という関数を使います。
ノードのnextがNULLだった場合、そのノードは一番末尾のノードになります。
末尾のノード（tail）が見つかったら、そのノードのnextに新しいノードをセットします。
こうすることでコリジョンしたノードの末尾にどんどんノードが繋がっていくようになります。
これがチェイン法と呼ばれるアルゴリズムです。
for (HashMapNode *cur = node; cur; cur = cur->next) {
if (strcmp(cur->key, key) == 0) {
// found node. overwrite data
if (self->deleter) {
self->deleter(cur->data);
}
cur->data = data;
break;
} else if (!cur->next) {
// found tail
cur->next = HashMapNode_New(key, data, NULL);
if (!cur->next) {
goto error;
}
break;
}
}
以上でHashMap_Set()の処理は終わりです。
この関数が成功すると、テーブルにノードがセットされていきます。
プログラムをコンパイルして実行すると動作を確認することができます。
コリジョンの動作を見るためにHASH_MAP__NTABLEの値を2に設定してあります。
key > c
value > 1123
0: abc: 123
0: def: 223
0: ghi: 323
0: jkl: 423
0: mno: 523
0: ABC: 623
0: DEF: 723
0: aaa: 8123
0: b: 1023
1: a: 923
1: c: 1123
keyとvalueのプロンプトに適当にキーと値をセットしていきます。
そうすると上のようにテーブルが構築されます。
0: abc: 123という行は左からハッシュ値、キー、値を表しています。
インデントされているノードはnextに繋がっているノードです。
テーブルのサイズが2だと上のようにかなり偏ったテーブルになります。
テーブルのサイズを適切に設定することでこのような偏りは減り、コリジョンも少なくなります。
🦝 < テーブルサイズが2だとほぼ線形探索やね
🐭 < ハッシュマップの良いとこが台無しやな
おわりに
今回はC言語でハッシュマップを実装してみました。
C言語はこういった基礎的なデータ構造の勉強に適した言語と言えます。
🦝 < C言語でアルゴリズム制覇するのら！
🐭 < のら・・・？