言語のしくみを読む

ライブラリとして使われているkhash.hを調べる。

C言語用のハッシュテーブルライブラリ。ヘッダファイルkhash.hをインクルードするだけで利用できる。マクロが多用してありその点、気をつけないとこける。

ハッシュテーブルに名前をつけ他のハッシュテーブルと区別する。ハッシュテーブルの要素はバケット（bucket）と呼ばれている。このバケットにvalueを入れていく。バケットにアクセスするにはイーサレータでおこなう。データの追加時の衝突対策をどうやっているのかはよくわからない。ハッシュテーブルにはmap型とset型があるが違いがよくわからない主にmap型を使用している。
コード例

An example:(khash.hにあるコード例)
#include "khash.h"

KHASH_MAP_INIT_INT(32, char) //ここでハッシュテーブルに'32'という名前を付けている。charはハッシュテーブルのデータ(value)型を指定
int main() {
  int ret, is_missing;
  khiter_t k; //ハッシュテーブルのバスケット(bucket)にアクセスするためのイーサレータ
  khash_t(32) *h = kh_init(32); //ｈはハッシュテーブルへのポインタ
  //kh_putが指定されたハッシュテーブルの任意のkeyに対してバスケットを作成する（この時点ではvalueは入っていない）
  //ret変数にはkeyがすでにハッシュテーブルに存在する場合は0、存在しない場合は1。この値でユーザー側が衝突対策をするのかな？
  k = kh_put(32, h, 5, &ret);
  kh_value(h, k) = 10; //ハッシュテーブルへのポインタ(h)とイーサレータ(k)で指定したバスケットにvalueを代入する
                                 //代入文ではなくprintf("bucket=%d\n",kh_value(h, k))とするとバスケットにvalueがあればそれを返してくる。
  k = kh_get(32, h, 10); //指定したハッシュテーブル・ポイントの指定したkey(ここでは10)に対応するバスケットがあればそのイーサレータを返す
                                    //なければ特別なイーサレータkh_end(h)を返すのでkeyに対応したバスケットはないことがわかる。次の文がそれを判定している。
  is_missing = (k == kh_end(h));
  k = kh_get(32, h, 5); 
  kh_del(32, h, k); //イーサレータ(k)に対応したバスケットを削除
  for (k = kh_begin(h); k != kh_end(h); ++k) //イーサレータをスキャンすることでハッシュテーブルを舐めることができる
    if (kh_exist(h, k)) kh_value(h, k) = 1; //kh_exist関数はイーサレータにデータがあれば1なければ0
  kh_destroy(32, h);  //ハッシュテーブルの破壊
  return 0;
}

ハッシュテーブルの生成

//整数キーを持つセット型ハッシュテーブルを作る
KHASH_SET_INIT_INT(name)->KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
//整数キーを持つマップ型ハッシュテーブルを作る
KHASH_MAP_INIT_INT(name, khval_t)->KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
//整数キー（64bit）を持つセット型ハッシュテーブルを作る
KHASH_SET_INIT_INT64(name)->KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
//整数キー(64bit)を持つマップ型ハッシュテーブルを作る
KHASH_MAP_INIT_INT64(name, khval_t)->KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
//文字列キーを持つセット型ハッシュテーブルを作る
KHASH_SET_INIT_STR(name)->KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
//文字列キーを持つマップ型ハッシュテーブルを作る
KHASH_MAP_INIT_STR(name, khval_t)->KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)

ハッシュテーブルの操作

整数キー同士が同じか判定する
kh_int_hash_equal(a,b) #整数キーの同一判定をする
kh_int64_hash_equal(a,b) #整数キー(64bit)の同一判定をする

与えられた整数キーをハッシュテーブルのindexにする関数
kh_int_hash_func(key)  #32bit
kh_int64_hash_func(key) #64bit->32bitのインデックスに変換する

与えられた文字列キーをハッシュテーブルのindexにする関数
kh_str_hash_func(key)

文字列キー同士が同じか判定する
kh_str_hash_equal(a,b)

名前を与えられたハッシュテーブルの初期化とインスタンス変数
khash_t, kh_init
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前

ハッシュテーブルのリセット
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
 ..
kh_clear(hashtable_name,h) #メモリはそのまま

ハッシュテーブルのリサイズ
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
 ..
kh_resize(hashtable_name,h,s) #sはリサイズ数

ハッシュテーブルにkeyを挿入（valueはまだ）
int ret;
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
kh_put(hashtable_name,h,key,&ret)
    ret変数の解釈
    keyがハッシュテーブルに存在する場合は0,存在しない場合は1
    戻り値：
    挿入された要素のイテレータ、この時点ではhashtableにvalueのための領域(bucketと呼んでいる模様)がputされた
    だけでvalue自体はまだ。

ハッシュテーブルからキーを削除する
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
kh_put(hashtable_name,h,key,&ret)
 ... 
kh_del(hashtable_name,h,key)

ハッシュテーブルのkeyにデータが入っているかテストする
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
kh_put(hashtable_name,h,key,&ret)
 ...  
kh_exist(h,key)
 戻り値：データがあれば1,なければ0

ハッシュテーブルの要素数を取得
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
kh_size(h)

 ハッシュテーブル内のバケット数を取得する
 khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
khint_t size = kh_n_buckets(h)

イーサレータ

ハッシュテーブルからkeyに対応したイーサレータを取得
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
khiter_t iter;
iter = kh_get(hashtable_name,h,key)

イータレータを指定してkeyを取得
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
kh_put(hashtable_name,h,key,&ret)
 ...  
kh_key(h,iter)

イータレータを指定してvalueを取得、設定
khash_t(hashtable_name) *h = kh_init(hashtable_name) #hashtable_nameはハッシュテーブルの名前
...
kh_put(hashtable_name,h,key,&ret)
...  
kh_val(h,iter) #kh_value(h,iter)としてもOK

スタートイータレータを取得
kh_begin(h) #最初のイータレータを返す

エンドイータレータを取得
kh_end(h) #最後のイータレータを返す

ハッシュテーブルの破壊

kh_destroy

khash_t(hashtable_name) *h = kh_init(hashtable_name)
....

kh_destroy(hashtable_name,h)