Cでハッシュテーブル

http://github.com/cubicdaiya/fnv

なんとなくCでハッシュテーブルを実装してみた。使い方はこんな感じ。

/* main.c */
#include <stdio.h>
#include "fnv.h"

int main (int argc, char *argv[]) {
  fnv_t tbl[FNV_TBL_CNT];
  const char *key = "KEY";
  const char *val = "VAL";
  fnv_tbl_init(tbl, FNV_TBL_CNT);
  fnv_put(tbl, key, val, strlen(key), strlen(val));
  printf("fnv_get(%s) = %s\n", key, fnv_get(tbl, key, strlen(key)));
  fnv_tbl_destroy(tbl, FNV_TBL_CNT);
  return 0;
}

キーのハッシュ値が衝突した際にエントリを連結リストでつないでいく部分の実装が微妙に面倒だったけど、それ以外は割とあっさりできた。

実行

$ gcc -std=c99 -Wall -O2 fnv.c main.c
$ ./a.out
fnv_get(KEY) = VAL
$

ハッシュ関数にはFNV hashを使用。

static uint_t fnv_hash(const char *k) {
  uint_t h = FNV_OFFSET_BASIS;
  for (uchar_t *p=(uchar_t *)k;*p!='\0';++p) {
    h *= FNV_PRIME;
    h ^= *p;
  }
  return h % FNV_TBL_CNT;
}