オープンアドレス型ハッシュ: 基本編
ソースはGitHubに移行しました。
Cuckoo Hash Table (Cuckooハッシュテーブル)
Open-Addressedハッシュの一種であるCuckooハッシュテーブルを実装する。
オリジナル論文はこちら：
"Cuckoo hashing"
2004年に発表された論文である。
ハッシュテーブルの検索はO(1)であるが、実際はコリジョンなどで数ステップ必要な場合もある。
しかしCuckooは検索が1か2ステップで必ず完了するのが特徴である。
これは基本アルゴリズムで、追加削除などの基本操作は一つのロックで守られている。
ロックの細粒化はConcurrent Cuckoo Hashで行う。
ハッシュ全般とこのアルゴリズムの位置付けについてはこちらを必読。
ソースはGitHubに移行しました。
Cuckooハッシュは2つのハッシュ関数をつかう。以下に示す。
static unsigned int hashCode0(lkey_t key, const hashtable_t * ht)
{
return ((key * 269) % ht->table_size);
}
static unsigned int hashCode1(lkey_t key, const hashtable_t * ht)
{
return ((key * 271) % ht->table_size);
}
269と271は乗算して2^32より大きくなる最初の双子素数である。ただし、追加時のコリジョンが避けられるかどうかの分析は一切していない。
データ構造
データ構造node_tとhashtable_tを定義する。
以降、共通のデータ型として"common.h"に"bool_t"、"lkey_t"、"val_t"を定義する。 "bool_t"は自明、 "lkey_t"はnodeのkey、"val_t"はnodeのvalを保持する。
common.h: typedef bool bool_t; typedef uint64_t lkey_t; typedef int64_t val_t;
次に、nodeとおよびhashtableのデータ構造を示す。
CuckooHash.h
typedef enum { EMP = 0, DEL = 1, OCC = 2 } node_stat;
typedef struct _node_t
{
lkey_t key; /* key */
val_t value; /* 値 */
node_stat stat; /* ノードの状態 */
} node_t;
typedef struct _hashtable_t {
unsigned long int setSize; /* 全node数 */
node_t *table[2]; /* ハッシュテーブル本体 */
unsigned int table_size; /* ハッシュテーブルの大きさ(長さ) */
node_t *old_table[2]; /* resizeする際に、一時的に利用するハッシュテーブル */
unsigned int old_table_size; /* old_table[0]の大きさ = resize前のテーブルの大きさ */
pthread_mutex_t mtx;
} hashtable_t;
******* 図 *******
node_tは(key,val)のペアを保持する。
hashtable_tには全ノード数を記録するsetSize、
ハッシュテーブル本体であるtable[2]とその大きさを記録するtable_size、
およびresize()でテーブルサイズを変更する際に、一時的にこれまでのテーブル(へのポインタ)を保持する
old_table[2]とそのサイズを記録するold_table_sizeがある。
さらに、ハッシュテーブルをロックするためのpthread_mutex変数mtxがある。
基本関数
ハッシュテーブルの生成
/*
* bool_t init_tables(hashtable_t * ht, const unsigned int table_size)
*
* ハッシュテーブルhtの2つのテーブルtable[0],talbe[1]を初期化する。
*
* 成功すればtrue、失敗すればfalseを返す。
*/
static bool_t init_tables(hashtable_t * ht, const unsigned int table_size)
{
unsigned int i;
if ((ht->table[0] =
(node_t *) calloc(table_size, sizeof(node_t))) == NULL) {
elog("calloc error");
return false;
}
if ((ht->table[1] =
(node_t *) calloc(table_size, sizeof(node_t))) == NULL) {
elog("calloc error");
free(ht->table[0]);
return false;
}
for (i = 0; i < table_size; i++) {
set_node(&ht->table[0][i], (lkey_t) NULL, (val_t) NULL, EMP);
set_node(&ht->table[1][i], (lkey_t) NULL, (val_t) NULL, EMP);
}
ht->setSize = 0;
return true;
}
static void free_tables(node_t ** table)
{
free(table[0]);
free(table[1]);
}
/*
* hashtable_t *init_hashtable(const unsigned int size)
*
* 2^sizeのハッシュテーブルを生成する。
*
* 成功すれば、そのポインタを返す。失敗すればNULLを返す。
*
*/
hashtable_t *init_hashtable(const unsigned int size)
{
hashtable_t *ht;
unsigned int s;
unsigned int table_size;
if (CH_DEFAULT_MAX_SIZE <= size)
s = CH_DEFAULT_MAX_SIZE;
else
s = size;
table_size = (0x00000001 << s);
if ((ht = (hashtable_t *) calloc(1, sizeof(hashtable_t))) == NULL) {
elog("calloc error");
return NULL;
}
ht->table_size = table_size;
ht->mtx = (pthread_mutex_t) PTHREAD_MUTEX_INITIALIZER;
if (init_tables(ht, table_size) != true) {
free(ht);
return NULL;
}
return ht;
}
void free_hashtable(hashtable_t * ht)
{
free_tables(ht->table);
free(ht);
}
要素の書き込み
static void
set_node(node_t * node, const lkey_t key, const val_t val,
const node_stat stat)
{
node->key = key;
node->value = val;
node->stat = stat;
}
static bool_t
swap_node(hashtable_t * ht, const int no, node_t node, node_t * next)
{
node_t *tmp;
bool_t ret = false;
tmp = get_node(ht, no, node.key);
set_node(next, tmp->key, tmp->value, tmp->stat);
set_node(tmp, node.key, node.value, OCC);
if (next->stat != OCC)
ret = true;
return ret;
}
static node_t *get_node(hashtable_t * ht, const int no, const lkey_t key)
{
unsigned int myBucket;
node_t *node;
if (no == 0) {
myBucket = hashCode0(key, ht);
node = &ht->table[0][myBucket];
} else {
myBucket = hashCode1(key, ht);
node = &ht->table[1][myBucket];
}
return node;
}
/*
* bool_t add(hashtable_t * ht, const lkey_t key, const val_t val)
*
* ハッシュテーブルhtに要素(key,val)を書き込む。
*
* 成功すればtrue、失敗すればfalseを返す。
*/
bool_t add(hashtable_t * ht, const lkey_t key, const val_t val)
{
unsigned int i;
node_t node;
bool_t ret = false;
node_t tmp;
int try = 10;
lock(ht->mtx);
if (contains_op(ht, key) == true) {
unlock(ht->mtx);
return false;
}
set_node(&node, key, val, OCC);
retry:
for (i = 0; i < ht->table_size; i++) {
if ((ret = swap_node(ht, 1, node, &tmp)) == true) {
ht->setSize++;
break;
} else if ((ret = swap_node(ht, 2, tmp, &node)) == true) {
ht->setSize++;
break;
}
}
if (ret == false && try-- > 0) {
resize(ht);
printf ("Resized\n");
goto retry;
}
unlock(ht->mtx);
return ret;
}
要素の削除
オープンアドレスなので、論理的な削除である。
static void del_op(hashtable_t * ht, node_t * node)
{
set_node(node, (lkey_t) NULL, (val_t) NULL, DEL);
ht->setSize--;
}
/*
* bool_t delete(hashtable_t * ht, const lkey_t key, val_t * getval)
*
* ハッシュテーブルhtからkeyを持つ要素を削除し、そのvalを*valに書き込む。
* keyが存在しない場合は失敗。
*
* 成功すればtrue、失敗すればfalseを返す。
*/
bool_t delete(hashtable_t * ht, const lkey_t key, val_t * getval)
{
node_t *node;
bool_t ret = false;
int i;
lock(ht->mtx);
for (i = 0; i <= 1; i++) {
node = get_node(ht, i, key);
if (node->key == key && node->stat == OCC) {
*getval = node->value;
del_op(ht, node);
ret = true;
break;
}
}
unlock(ht->mtx);
return ret;
}
要素の検索
talbe[0]かtable[1]のみ調べればよい。完全にO(1)である。
static bool_t find_op(hashtable_t * ht, const lkey_t key)
{
node_t *node;
bool_t ret = false;
int i;
for (i = 0; i <= 1; i++) {
node = get_node(ht, i, key);
if (node->stat == OCC && node->key == key) {
ret = true;
break;
}
}
return ret;
}
/*
* bool_t find(hashtable_t * ht, const lkey_t key)
*
* ハッシュテーブルhtからkeyを持つ要素を検索し、そのvalを*valに書き込む。
* keyが存在しない場合は失敗。
*
* 成功すればtrue、失敗すればfalseを返す。
*/
bool_t find(hashtable_t * ht, const lkey_t key)
{
bool_t ret;
lock(ht->mtx);
ret = find_op(ht, key);
unlock(ht->mtx);
return ret;
}
ハッシュテーブルの再構築(resize())
再構築のタイミングは追加が失敗した場合である。
static void resize(hashtable_t * ht)
{
node_t *old_node;
node_t new_node;
unsigned int i, j, k;
node_t tmp;
ht->old_table_size = ht->table_size;
ht->old_table[0] = ht->table[0];
ht->old_table[1] = ht->table[1];
if (init_tables(ht, (ht->table_size * 2)) == false)
return;
ht->table_size *= 2;
for (i = 0; i <= 1; i++) {
for (j = 0; j < ht->old_table_size; j++) {
old_node = &ht->old_table[i][j];
if (old_node->stat == OCC) {
set_node(&new_node, old_node->key, old_node->value, OCC);
for (k = 0; k < ht->table_size; k++) {
if (swap_node(ht, 1, new_node, &tmp) == true) {
ht->setSize++;
break;
} else if (swap_node(ht, 2, tmp, &new_node) == true) {
ht->setSize++;
break;
}
}
}
}
}
free_tables(ht->old_table);
}
実行
ソースはGitHubに移行しました。
Last-modified: 2014-7-6