オープンアドレス型ハッシュ: 超基本編

ソースはGitHubに移行しました。

Open-Addressed Hash Table (オープンアドレスハッシュテーブル)

目先をかえてOpen-Addressedハッシュを実装する。これは次のCuckooハッシュの下準備である。
Open-Addressed系はリスト処理がないので削除や追加も簡単にでき、実装は楽、且つ頑健である。
ハッシュ全般とこのアルゴリズムの位置付けについてはこちらを必読。

ソースはGitHubに移行しました。

なお、通常のアルゴリズム解説ならば必須の、ハッシュ関数に関する議論は一切行わない。 ここではハッシュ関数hashCode()を"keyをテーブルサイズで割った余り"で定義する。 

static unsigned int hashCode(lkey_t key, const hashtable_t * ht)
{
    return (key % ht->table_size);
}

データ構造

データ構造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のデータ構造を示す。 

OpenAddressedHash.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 *bucket;                   /* ハッシュテーブル本体 */
  unsigned int table_size;          /* ハッシュテーブルの大きさ(長さ) */

  node_t *old_bucket;               /* resizeする際に、一時的に利用するハッシュテーブル */
  unsigned int old_table_size;      /* old_bucketの大きさ = resize前のテーブルの大きさ */

  pthread_mutex_t mtx;
} hashtable_t;

node_tは(key,val)のペアを保持する。

hashtable_tには全ノード数を記録するsetSize、 ハッシュテーブル本体であるbucketとその大きさを記録するtable_size、 およびresize()でテーブルサイズを変更する際に、一時的にこれまでのテーブル(へのポインタ)を保持する old_bucketとそのサイズを記録するold_table_sizeがある。
さらに、ハッシュテーブルをロックするためのpthread_mutex変数mtxがある。

基本関数

ハッシュテーブルの生成
/*
 * 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 =
	 (node_t *) calloc(table_size, sizeof(node_t))) == NULL) {
      elog("calloc error");
      return false;
    }

    for (i = 0; i < table_size; i++)
	set_node(&ht->bucket[i], (lkey_t) NULL, (val_t) NULL, EMP);

    ht->setSize = 0;

    return true;
}

static void free_bucket(node_t * bucket)
{
    free(bucket);
}


/*
 * hashtable_t *init_hashtable(const unsigned int table_size)
 *
 * 大きさtable_sizeのハッシュテーブルを生成する。
 *
 * 成功すれば、そのポインタを返す。失敗すればNULLを返す。
 * 
 */
hashtable_t *init_hashtable(const unsigned int size)
{
    hashtable_t *ht;
    unsigned int table_size = (0x0001 << size);

    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_bucket(ht, table_size) != true) {
	free(ht);
	return NULL;
    }

    return ht;
}
要素の書き込み
static void
set_node(node_t * node, const lkey_t key, const val_t val,
	 const node_stat stat)
{
    assert(node != NULL);
    node->key = key;
    node->value = val;
    node->stat = stat;
}


static void
add_op(hashtable_t * ht, node_t * node, const lkey_t key,
       const val_t val)
{
    set_node(node, key, val, OCC);
    ht->setSize++;
}


/*
 * 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, myBucket;
    node_t *node;
    bool_t ret = false;

    lock(ht->mtx);

    for (i = 0; i < ht->table_size; i++) {
	myBucket = hashCode(key, i, ht);
	node = &ht->bucket[myBucket];

	if (node->stat != OCC) {
	    add_op(ht, node, key, val);
	    ret = true;
	    break;
	}
    }

    if (policy(ht)) {
      resize(ht);
      fprintf (stderr, "Resized\n");
    }
    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)
{
    unsigned int i, myBucket;
    node_t *node;
    bool_t ret = false;

    lock(ht->mtx);

    for (i = 0; i < ht->table_size; i++) {
	myBucket = hashCode(key, i, ht);
	node = &ht->bucket[myBucket];
	if (node->stat == EMP) {
	    ret = false;
	    break;
	} else if (node->stat != DEL && node->key == key) {
	    ret = true;
	    *getval = node->value;
	    del_op(ht, node);
	    break;
	}
    }

    unlock(ht->mtx);

    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)
{
    unsigned int i, myBucket;
    node_t *node;
    bool_t ret = false;

    lock(ht->mtx);

    for (i = 0; i < ht->table_size; i++) {
	myBucket = hashCode(key, i, ht);
	node = &ht->bucket[myBucket];
	if (node->stat == EMP) {
	    ret = false;
	    break;
	} else if (node->stat != DEL && node->key == key) {
	    ret = true;
	    break;
	}
    }

    unlock(ht->mtx);

    return ret;
}
ハッシュテーブルの再構築(resize())
static bool_t policy(hashtable_t * ht)
{
    //  return ((ht->table_size * 3 / 4) < ht->setSize ? true : false);
    return ((ht->table_size * 4 / 5) < ht->setSize ? true : false);
}

static void resize(hashtable_t * ht)
{
    node_t *old_node, *new_node;
    unsigned int i, j, 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++) {
	old_node = &ht->old_bucket[i];

	if (old_node->stat == OCC) {
	    for (j = 0; j < ht->table_size; j++) {
		myBucket = hashCode(old_node->key, j, ht);
		new_node = &ht->bucket[myBucket];
		if (new_node->stat != OCC) {
		    add_op(ht, new_node, old_node->key, old_node->value);
		    break;
		}
	    }
	}
    }
    free_bucket(ht->old_bucket);
}

実行

ソースはGitHubに移行しました。

Last-modified: 2014-7-6