Chain型ハッシュ: 超基本編
Coarse-Grained Hash Table(粗粒度ハッシュテーブル)
最も簡単なChain型ハッシュから復習。 ハッシュ全般とこのアルゴリズムの位置付けについてはこちらを必読。
プログラムのソースは:
ほとんどの教科書に載っているソースコードはLockを考慮していないし、
衝突(collision)が多発した場合のハッシュテーブルの再構成(resize)には触れていない。
ここではテーブルに1つのLockを設定し、基本操作(add, delete, find)の相互排他に用いる。
また、ある程度以上のノードが登録されたら、ハッシュテーブルの大きさを2倍に拡大して
衝突を避けるresize()機能を実装する。
なお、通常のアルゴリズム解説ならば必須の、ハッシュ関数に関する議論は一切行わない。 ここではハッシュ関数hashCode()を"keyをテーブルサイズで割った余り"で定義する。
static unsigned int hashCode(lkey_t key, const hashtable_t * ht)
{
return (key % ht->table_size);
}
データ構造
データ構造node_t、list_t、hashtable_tを定義する。
hashtable_tはハッシュテーブルの本体、
list_tはハッシュテーブルの各要素に付属するList、node_tはListに連結するnodeのデータ構造である。
簡単に図示する。
hashtable [0|head]->[4]->[16]->[32] [1|head] [2|head]->[2]->[6] [3|head]->[3]->[7]->[10]
以降、共通のデータ型として"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とlist、およびhashtableのデータ構造を示す。
Hash.h
typedef struct _node_t
{
lkey_t key; /* key */
val_t value; /* 値 */
struct _node_t *next; /* 次のnodeへのポインタ*/
} node_t;
typedef struct _list_t
{
node_t *head;
} list_t;
typedef struct _hashtable_t
{
unsigned long long int setSize; /* 全node数 */
list_t *bucket; /* ハッシュテーブル本体 */
unsigned int table_size; /* ハッシュテーブルの大きさ(長さ) */
list_t *old_bucket; /* resizeする際に、一時的に利用するハッシュテーブル */
unsigned int old_table_size; /* old_bucketの大きさ = resize前のテーブルの大きさ */
pthread_mutex_t mtx;
} hashtable_t;
node_tは(key,val)のペアと、次のnodeへのポインタを保持する。
list_tにはリストの先頭headが確保される。
hashtable_tには全ノード数を記録するsetSize、
ハッシュテーブル本体であるbucketとその大きさを記録するtable_size、
およびresize()でテーブルサイズを変更する際に、一時的にこれまでのテーブル(へのポインタ)を保持する
old_bucketとそのサイズを記録するold_table_sizeがある。
さらに、全操作(add,delete,find)毎にハッシュテーブル全体をロックするためのpthread_mutex変数mtxがある。
基本関数
ハッシュテーブルの生成
/*
* bool_t *init_list(list_t *l)
*
* list_t *lにノードheadを生成する。
*
* 成功すればtrue、失敗ならfalseを返す。
*
*/
static bool_t init_list(list_t * l)
{
if ((l->head = (node_t *) calloc(1, sizeof(node_t))) == NULL) {
elog("calloc error");
return false;
}
l->head->next = NULL;
return true;
}
/*
* bool_t init_bucket(hashtable_t * ht, const unsigned int table_size)
*
* ハッシュテーブルhtの各要素を初期化(リストの初期化)する。
*
* 成功すればtrue、失敗すればfalseを返す。
*/
static bool_t init_bucket(hashtable_t * ht, const unsigned int table_size)
{
unsigned int i;
if ((ht->bucket =
(list_t *) calloc(table_size, sizeof(list_t))) == NULL) {
elog("calloc error");
return false;
}
for (i = 0; i < table_size; i++)
if (init_list(&ht->bucket[i]) == false)
return false;
return true;
}
/*
* hashtable_t *init_hashtable(const unsigned int table_size)
*
* 大きさtable_sizeのハッシュテーブルを生成する。
*
* 成功すれば、そのポインタを返す。失敗すればNULLを返す。
*
*/
hashtable_t *init_hashtable(const unsigned int table_size)
{
hashtable_t *ht;
if ((ht = (hashtable_t *) calloc(1, sizeof(hashtable_t))) == NULL) {
elog("calloc error");
return NULL;
}
ht->table_size = table_size;
ht->setSize = 0;
ht->mtx = (pthread_mutex_t) PTHREAD_MUTEX_INITIALIZER;
if (init_bucket(ht, table_size) != true) {
free(ht);
return NULL;
}
return ht;
}
ノードの追加
ノードの追加だが、後半部分に一定数以上のノードになった場合のテーブル再構築(resize()) がある以外、特に目新しいことはない。
/*
* bool_t add(list_t * list, const lkey_t key, const val_t val)
*
* listにnode(key,val)を追加する。
* 追加位置はkeyの昇順に従う。すでに同じkeyを持つnodeがある場合は失敗。
*
* 成功すればtrue、失敗すればfalseを返す。
*/
/*
* bool_t add(hashtable_t * ht, const lkey_t key, const val_t val)
*
* ハッシュテーブルhtにnode(key,val)を追加する。
*
* 成功すればtrue、失敗すればfalseを返す。
*/
bool_t add(hashtable_t * ht, const lkey_t key, const val_t val)
{
bool_t ret = true;
unsigned int myBucket;
lock(ht->mtx);
myBucket = hashCode(key, ht);
if (add_node(&ht->bucket[myBucket], key, val) == true)
ht->setSize++;
else
ret = false;
if (policy(ht)) {
resize(ht);
fprintf (stdout, "Resized\n"); fflush(stdout);
}
unlock(ht->mtx);
return ret;
}
/*
* bool_t add_node(list_t * l, const lkey_t key, const val_t val)
*
* リストlにノード(key,val)を生成して追加する。
*
* 成功するとtrue、失敗するとfalseを返す。
*
*/
static bool_t add_node(list_t * l, const lkey_t key, const val_t val)
{
node_t *newNode;
if ((newNode = create_node(key, val)) == NULL)
return false;
if (add_node_op(l, newNode) != true) {
free_node(newNode);
return false;
}
return true;
}
/*
* bool_t add_node_op(list_t * l, node_t * newNode)
*
* ノードnewNodeをリストlに追加する。
*
* 成功すればtrue、失敗ならfalseを返す。
*
*/
static bool_t add_node_op(list_t * l, node_t * newNode)
{
node_t *pred, *curr;
bool_t ret = true;
pred = l->head;
curr = pred->next;
if (curr == NULL) {
l->head->next = newNode;
newNode->next = NULL;
} else {
while ((curr != NULL) && (curr->key < newNode->key)) {
pred = curr;
curr = curr->next;
}
if (curr == NULL || newNode->key != curr->key) {
newNode->next = curr;
pred->next = newNode;
} else
ret = false;
}
return ret;
}
関数add_node()内部で呼ぶnode生成関数create_node()を示す。
/*
* node_t *create_node(const lkey_t key, const val_t val)
*
* (key, val)を持つnodeを生成する。
*
* 成功すればnodeへのポインタを返す。失敗すればNULLを返す。
*/
static node_t *create_node(const lkey_t key, const val_t val)
{
node_t *newNode;
if ((newNode = (node_t *) calloc(1, sizeof(node_t))) == NULL) {
elog("calloc error");
return NULL;
}
newNode->key = key;
newNode->value = val;
return newNode;
}
nodeの削除
/*
* bool_t delete(hashtable_t * ht, const lkey_t key, val_t * getval)
*
* ハッシュテーブルhtからkeyを持つnodeを削除し、そのnodeのvalを*valに書き込む。
* keyが存在しない場合は失敗。
*
* 成功すればtrue、失敗すればfalseを返す。
*/
bool_t delete(hashtable_t * ht, const lkey_t key, val_t * getval)
{
bool_t ret = true;
unsigned int myBucket;
lock(ht->mtx);
myBucket = hashCode(key, ht);
if (delete_node(&ht->bucket[myBucket], key, getval) == true)
ht->setSize--;
else
ret = false;
unlock(ht->mtx);
return ret;
}
/*
* bool_t delete_node(list_t * l, const lkey_t key, val_t * getval)
*
* リストlからノード(key,val)を削除する。
*
* 成功するとgetvalにvalを代入してtrueを返す。失敗するとfalseを返す。
*
*/
static bool_t delete_node(list_t * l, const lkey_t key, val_t * getval)
{
node_t *pred, *curr;
pred = l->head;
curr = pred->next;
if (curr == NULL)
return false;
while ((curr != NULL) && (curr->key < key)) {
pred = curr;
curr = curr->next;
}
if ((key == curr->key) && (curr != NULL)) {
*getval = curr->value;
pred->next = curr->next;
free_node(curr);
} else
return false;
return true;
}
ノードの検索
/*
* bool_t find(hashtable_t * ht, const lkey_t key)
*
* ハッシュテーブルhtからkeyを持つnodeを検索し、そのnodeのvalを*valに書き込む。
* keyが存在しない場合は失敗。
*
* 成功すればtrue、失敗すればfalseを返す。
*/
bool_t find(hashtable_t * ht, const lkey_t key)
{
unsigned int myBucket;
bool_t ret;
lock(ht->mtx);
myBucket = hashCode(key, ht);
ret = find_node(&ht->bucket[myBucket], key);
unlock(ht->mtx);
return ret;
}
/*
* bool_t find_node(list_t * l, lkey_t key)
*
* リストlにkeyを持つノードがあるか否か調べる。
*
* 成功すればtrue、失敗すればfalseを返す。
*/
static bool_t find_node(list_t * l, lkey_t key)
{
node_t *pred, *curr;
pred = l->head;
curr = pred->next;
if (curr == NULL) {
return false;
} else {
while ((curr != NULL) && (curr->key < key)) {
pred = curr;
curr = curr->next;
}
if ((curr == NULL) || (key != curr->key))
return false;
}
return true;
}
ハッシュテーブルの再構築(resize())
static bool_t policy(hashtable_t * ht)
{
return ((int) (ht->setSize / ht->table_size) > 4 ? true : false);
}
static void resize(hashtable_t * ht)
{
list_t *l;
node_t *pred, *curr;
unsigned int i, myBucket;
ht->old_table_size = ht->table_size;
ht->old_bucket = ht->bucket;
if (init_bucket(ht, ht->table_size * 2) == false)
return;
ht->table_size *= 2;
for (i = 0; i < ht->old_table_size; i++) {
l = &ht->old_bucket[i];
pred = l->head;
curr = pred->next;
while (curr != NULL) {
pred->next = curr->next; /* <==> next = curr->next; pred->next = next; */
myBucket = hashCode(curr->key, ht);
add_node_op(&ht->bucket[myBucket], curr);
curr = pred->next;
}
}
free_bucket(ht->old_bucket, ht->old_table_size);
}
実行
プログラムのソースは:
# gcc -Wall -m32 -D_SINGLE_THREAD_ -o Hash Hash.c -lpthread # ./Hash
# gcc -Wall -m32 -c -o Hash.o Hash.c # gcc -Wall -m32 -D_Hash_ -o Hash Hash.o hash_test.c -lpthread
Last-modified: 2010-3-13