C言語でHashMapを実装する。

はじめに

C 言語でのハッシュマップ（HashMap）の設計と実装について詳しく説明します。コードは細かく説明しています。

HashMap とは

HashMap とは、キーバリュー形式のデータ構造です。追加、検索、削除の計算量が O(1) という特徴を持ちます。

HashMap はプログラミングにおけるあらゆる場面で登場する便利なデータ構造です。例えば、Python の辞書型が HashMap です。C 言語では、標準ライブラリに HashMap がないため自分で実装することが多いです。

仕組み

HashMap は、与えられたキーに対してハッシュ値を計算し、その値を配列の引数として利用することで高速なアクセスを実現します。
ハッシュ値の計算と配列の読み出しが O(1)のため、全体の計算量も O(1)になります。

データ構造

HashMap のデータ構造は以下です。

typedef struct Entry Entry;
struct Entry {
  char *key;
  char *value;
  Entry *next;  // for chaining
};

typedef struct HashMap HashMap;
struct HashMap {
  Entry **entries;
  int size;  // size of entries
};

Entry の next は Hash 値がコリジョンした場合に利用します。コリジョンした場合の対応については後で説明します。size には配列のサイズが入ります。

初期化

HashMap の初期化は以下のように実装します。

HashMap *newHashMap(int size) {
  HashMap *hashmap = malloc(sizeof(HashMap));
  hashmap->size = size;

  // initialize entries
  hashmap->entries = malloc(sizeof(Entry) * size);
  for (int i = 0; i < size; i++) {
    hashmap->entries[i] = NULL;
  }

  return hashmap;
}

entries は NULL で初期化します。

Hash 関数

Hash 関数には以下を利用します。計算量が少なく単純なものが良いです。

unsigned int hash(const char *key, const int size) {
  unsigned int hash = 0;
  for (int i = 0; key[i] != '\0'; i++) {
    hash = 31 * hash + key[i];
  }
  return hash % size;
}

31は適当な素数です。素数を選ぶことで出力が均等になりやすく、ハッシュ値のコリジョンがしにくくなります。sizeは配列のサイズです。Hash 値がコリジョンした場合の回避方法は後で解説します。

書き込み

書き込みは以下のように実装します。

void insertToHashMap(const HashMap *hashmap, const char *key,
                     const char *value) {
  unsigned int index = hash(key, hashmap->size);

  // check if key already exists
  Entry *entry = hashmap->entries[index];
  if (entry != NULL) {
    return;
  }
  // create new entry
  entry = malloc(sizeof(Entry));
  entry->key = strdup(key);
  entry->value = strdup(value);
  hashmap->entries[index] = entry;
}

ここでは、Hash 値が重複した場合は何もしないように実装しています。

読み出し

読み出しは以下のように実装します。

char *getValueFromHashMap(const HashMap *hashmap, const char *key) {
  unsigned int index = hash(key, hashmap->size);

  Entry *entry = hashmap->entries[index];
  // check if key exists
  if (entry == NULL) {
    return NULL;
  }

  return entry->value;
}

与えられた key が存在しない時、NULL を返します。

使ってみる

これまで実装した関数は、以下のように使うことができます。

int main(void) {
  int size = 100;
  struct HashMap *hashmap = createHashMap(size);

  put(hashmap, "key1", "value1");
  put(hashmap, "key2", "value2");
  char *value = get(hashmap, "key1");

  printf("key1: %s\n", value); // key1: value1
  return 0;
}

ただ、これまでの実装では Hash 関数が被った場合にデータが勝手に上書きされてしまいます。これを防ぐためには、コリジョンへの対応が必要です。

コリジョンへの対応

Hash 値のコリジョンが発生した場合は、連携リストに書き込みます。

void insertToHashMap(const HashMap *hashmap, const char *key,
                     const char *value) {
  unsigned int index = hash(key, hashmap->size);

  // check if key already exists
  Entry *entry = hashmap->entries[index];
  while (entry != NULL) {
    if (strcmp(entry->key, key) == 0) {
      free(entry->value);
      entry->value = strdup(value);
      return;
    }
    entry = entry->next;
  }

  // create new entry
  entry = malloc(sizeof(Entry));
  entry->key = strdup(key);
  entry->value = strdup(value);
  entry->next = hashmap->entries[index];  // for chaining
  hashmap->entries[index] = entry;
}

読み出しの際には、連結リスト内で key を比較していき一致したものを返します。

char *getValueFromHashMap(const HashMap *hashmap, const char *key) {
  unsigned int index = hash(key, hashmap->size);

  Entry *entry = hashmap->entries[index];
  while (entry != NULL) {
    if (strcmp(entry->key, key) == 0) {
      return entry->value;
    }
    entry = entry->next;
  }

  return NULL;
}

このような連携リストを用いたコリジョンへの対策をチェイン法と言います。チェイン法によって HashMap 初期化時の size 以上の値を代入することができます。

メモリの解放

メモリ解放を実装します。

void freeEntry(Entry *entry) {
  while (entry != NULL) {
    Entry *next = entry->next;
    free(entry->key);
    free(entry->value);
    free(entry);
    entry = next;
  }
}

void freeHashMap(HashMap *hashmap) {
  for (int i = 0; i < hashmap->size; i++) {
    freeEntry(hashmap->entries[i]);
  }
  free(hashmap->entries);
  free(hashmap);
}

慎重に free を書きます。

要素の削除

要素を削除する関数は以下のように実装します。

int removeFromHashMap(const HashMap *hashmap, const char *key) {
  unsigned int index = hash(key, hashmap->size);
  Entry *entry = hashmap->entries[index];

  // find the entry and its predecessor
  Entry *pred = NULL;
  while (entry != NULL) {
    if (strcmp(entry->key, key) == 0) {
      break;
    }
    pred = entry;
    entry = entry->next;
  }

  if (entry == NULL) return -1;
  if (pred == NULL) {  // entry is the first in the list
    hashmap->entries[index] = entry->next;
  } else {  // entry is not the first in the list
    pred->next = entry->next;
  }

  free(entry->key);
  free(entry->value);
  free(entry);

  return 0;
}

連結リストを順番に探索していき、見つかったら要素を削除します。

終わりに

C 言語で HashMap を実装しました。HashMap の設計と内部動作、そして C 言語におけるメモリ管理の重要性について学びました。この知識は HashMap だけでなく、他の複雑なデータ構造を理解し、実装するための基礎となります。

コードは以下に公開しました。

https://github.com/derbuihan/c_hashmap