C言語アルゴリズム-オープンアドレス法

オープンアドレス法(open addressing)について

ハッシュ法について

ハッシュ法とは、キー値からハッシュ関数によって「ハッシュ値」を求め、ハッシュ値をバケット（bucket：ハッシュテーブルの各要素）に結びつけるデータ構造を生成し、高速な探索を実現する手法です。ハッシュ法を用いることで、データの数に関わらず挿入・探索・削除の操作を実質的に「O(1)」で行うことができます。

ハッシュ関連の用語は以下の通りです。

• ハッシュ値(hash value)
  • ハッシュ関数の返す値。キーを格納する配列の添え字。
• ハッシュ表(hash table)
  • データを格納する配列。
• バケット(bucket)
  • ハッシュ表の各要素。
• 衝突(collision)
  • 異なったキーの値から同じハッシュ値が得られること。

オープンアドレス法(開番法)とは

オープンアドレス法とは、ハッシュ値の衝突が発生した場合に、再ハッシュ（rehashing：別のバケットにデータを格納すること）を行い、データを登録する方法です。ハッシュ値の衝突が発生した場合には、ハッシュ値を変更しながら空いているバケットを調べていき、空いているバケットを発見したらデータを格納します。ハッシュテーブルのバケットにはデータを直接登録するため、登録可能なデータ数は有限（ハッシュテーブルの大きさ）となります。

なお、オープンアドレス法は「クローズドハッシュ法(closed hashing)」とも呼ばれます。

• 挿入方法
  • ハッシュ値の衝突が発生した場合には、再ハッシュを繰り返して「空状態」バケットを調べていき、空いているバケットを発見したらデータを格納します。
• 探索方法
  • キーからハッシュ値を求め、バケットのデータがキーに対応する値であればならばそれが探しているデータです。そうでなければ再ハッシュを繰り返してテーブル全体から探索します。
• 削除方法
  • バケットを空にしてしまうと以後の探索ができなくなってしまうため、バケットは空にせずに「削除済み」というマークを付けます。探索においては、削除済みマークが付いたバケットをスキップする処理を行う必要があります。
• 再挿入方法
  • 「削除済み」のバケットは「空状態」のバケットと同等に扱います。削除済みバケットと同一キーで再登録を行うと、削除済みバケットに「使用中」マークを付けてデータを登録します。

オープンアドレス法におけるデータ構造

キーから求めたハッシュ値が同一になった（衝突が発生）場合、再ハッシュします。

Insert  key[one]:hashval[2]
Insert  key[two]:hashval[2]  -> Conflict
Rehash  key[two]:hashval[3]
Insert  key[three]:hashval[0]
Insert  key[four]:hashval[4]
Insert  key[five]:hashval[2] -> Conflict
Rehash  key[five]:hashval[3] -> Conflict
Rehash  key[five]:hashval[4] -> Conflict
Rehash  key[five]:hashval[5]

上記のハッシュ登録を行った結果、以下のデータ構造となります。

table[0]:{three:val3}
table[1]: empty
table[2]:{one:val1}
table[3]:{two:val2}
table[4]:{four:val4}
table[5]:{five:val5}
table[6]: empty

C言語によるオープンアドレス法のサンプルプログラム

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

/* ハッシュテーブルの要素数 */
#define BUCKET_SIZE 5

/* バケットの状態 */
enum bucket_status{
    BUCKET_EMPTY,  /* 空状態 */
    BUCKET_USE,    /* 使用中 */
    BUCKET_DELETE  /* 削除済み */
};
typedef enum bucket_status bucket_stat;

/* バケット定義 */
struct bucket{
    char *key;
    char *data;
    bucket_stat stat;
};
typedef struct bucket bucket_t;

/*!
 * @brief          ハッシュの初期化処理
 * @param[in/out]  table  ハッシュテーブル
 */
void
hash_init(bucket_t *table)
{
    int cnt = 0;

    /* バケットを空状態に設定する */
    for(cnt = 0; cnt < BUCKET_SIZE; cnt++){
        table[cnt].stat = BUCKET_EMPTY;
        table[cnt].key  = NULL;
        table[cnt].data = NULL;
    }
    return;
}

/*!
 * @brief      ハッシュテーブルのデータを解放する
 * @param[in]  table  ハッシュテーブル
 */
void
hash_free(bucket_t *table)
{
    int cnt = 0;

    for(cnt = 0; cnt < BUCKET_SIZE; cnt++){
        if(table[cnt].key  != NULL) free(table[cnt].key);
        if(table[cnt].data != NULL) free(table[cnt].data);
    }
    return;
}

/*!
 * @brief      ハッシュ値を取得する
 * @param[in]  key  キー値
 * @return     ハッシュ値（BUCKET_SIZE - 1の範囲）
 */
static int
get_hash_value(char *key)
{
    int hashval = 0;

    while(*key){
        hashval += *key++;
    }
    return(hashval % BUCKET_SIZE);
}

/*!
 * @brief      再ハッシュの値を取得する
 * @param[in]  hashval  ハッシュ値
 * @return     ハッシュ値（BUCKET_SIZE - 1の範囲）
 */
static int
get_rehash_value(int hashval)
{
    return((hashval + 1) % BUCKET_SIZE);
}

/*!
 * @brief      文字列を領域確保してコピーする
 * @param[out] dest  文字列のコピー先
 * @param[in]  src   文字列
 * @return     0     success
 * @return     -1    failure
 */
static int
strcpy_alloc(char **dest, char *src)
{
    int length = 0;

    length = strlen(src);
    if(length <= 0){
        fprintf(stderr, "ERROR: Invalid parameter(%d line)\n", __LINE__);
        return(-1);
    }

    *dest = (char *)malloc(length);
    if(*dest == NULL){
        fprintf(stderr, "ERROR: %s(%d line)\n", strerror(errno), __LINE__);
        return(-1);
    }

    if(strcpy(*dest, src) == NULL){
        fprintf(stderr, "ERROR: %s(%d line)\n", strerror(errno), __LINE__);
        return(-1);
    }

    return(0);
}

/*!
 * @brief      ハッシュ表を探索して、キーに対応するデータを取得する
 * @param[in]  table  ハッシュテーブル
 * @param[in]  key    ハッシュキー
 * @return     データへのポインタ。存在しない場合にはNULLを返す。
 */
char *
hash_search(bucket_t *table, char *key)
{
    int hashval = 0;
    int cnt = 0;

    hashval = get_hash_value(key);
    while(table[hashval].stat == BUCKET_USE){
        /* 削除済みマークでないキーを探す */
        if((strcmp(table[hashval].key, key) == 0) &&
           (table[hashval].stat != BUCKET_DELETE)){
            return(table[hashval].data);
        }

        /* 再ハッシュを行い、テーブル全てを走査する */
        if(++cnt > BUCKET_SIZE) break;
        hashval = get_rehash_value(hashval);
    }

    return(NULL);
}

/*!
 * @brief       バケットにキーとデータを登録する
 * @param[out]  table  ハッシュテーブル
 * @param[in]   key    ハッシュキー
 * @param[in]   data   登録するデータ
 * @return      0      success
 * @return      -1     failure
 */
static int
bucket_savedata(bucket_t *bucket, char *key, char *data)
{
    /* 使用中マークを付ける */
    bucket->stat = BUCKET_USE;

    /* 再登録が発生する場合には古いデータを削除する */
    if(bucket->key != NULL){
        free(bucket->key);
        bucket->key = NULL;
    }
    if(bucket->data != NULL){
        free(bucket->data);
        bucket->data = NULL;
    }

    /* キーとデータを登録する */
    if(strcpy_alloc(&(bucket->key),  key)  != 0) return(-1);
    if(strcpy_alloc(&(bucket->data), data) != 0) return(-1);

    return(0);
}

/*!
 * @brief       ハッシュテーブルに登録する
 * @param[out]  table  ハッシュテーブル
 * @param[in]   key    ハッシュキー
 * @param[in]   data   登録するデータ
 * @return      0      success
 * @return      -1     failure
 */
int
hash_insert(bucket_t *table, char *key, char *data)
{
    int hashval = 0;
    int cnt = 0;

    /* 同一キーがすでに登録されているか確認する */
    if(hash_search(table, key) != NULL){
        fprintf(stderr, "key[%s] is already exist in hash table.\n", key);
        return(-1);
    }

    /* 空バケットが見つかるまで再ハッシュする */
    hashval = get_hash_value(key);
    while(table[hashval].stat == BUCKET_USE){
        if(++cnt > BUCKET_SIZE){
            fprintf(stderr, "Insert key[%s] hash table overflow.\n", key);
            return(-1);
        }
        hashval = get_rehash_value(hashval);
    }

    /* キーとデータをバケットに保存する */
    if(bucket_savedata(&(table[hashval]), key, data) != 0) return(-1);

    return( 0 );
}

/*!
 * @brief      ハッシュテーブルから削除する
 * @param[in]  table  ハッシュテーブル
 * @param[in]  key    ハッシュキー
 * @return     0      success
 * @return     -1     failure
 */
int
hash_delete(bucket_t *table, char *key)
{
    int hashval = 0;
    int cnt = 0;

    hashval = get_hash_value(key);
    while(table[hashval].stat != BUCKET_EMPTY){
        /* 削除済みマークでないキーを探す */
        if((strcmp(table[hashval].key, key) == 0) &&
           (table[hashval].stat != BUCKET_DELETE)){
            /* 削除済みマークを付ける */
            table[hashval].stat = BUCKET_DELETE;
            return(0);
        }

        /* 再ハッシュを行い、テーブル全てを走査する */
        if(++cnt > BUCKET_SIZE) break;
        hashval = get_rehash_value(hashval);
    }

    fprintf(stderr, "key[%s] not found.\n", key);
    return(-1);
}

/*!
 * @brief      ハッシュテーブルのデータ一覧を表示する
 * @param[in]  table  ハッシュテーブル
 */
static void
hash_print_table(bucket_t *table)
{
    int cnt = 0;

    for(cnt = 0; cnt < BUCKET_SIZE; cnt++){
        if(table[cnt].stat == BUCKET_USE){
            printf("table[%d]:", cnt);
            printf("{%s:%s}\n", table[cnt].key, table[cnt].data);
        }else if(table[cnt].stat == BUCKET_DELETE){
            printf("table[%d]: deleted\n", cnt);
        }else{
            printf("table[%d]: empty\n", cnt);
        }
    }
    putchar('\n');
}

int
main(void)
{
    bucket_t table[BUCKET_SIZE];

    /* ハッシュの初期化 */
    hash_init(table);

    /* データを登録する */
    hash_insert(table, "one", "value 1");
    hash_insert(table, "ten", "value 10");
    hash_insert(table, "thirteen", "value 13");
    hash_print_table(table);

    /* データを検索する */
    printf("Search: key:ten=val:%s\n", hash_search(table, "ten"));

    /* データを削除する */
    hash_delete(table, "ten");
    hash_delete(table, "thirteen");
    hash_print_table(table);

    /* 再登録する */
    hash_insert(table, "thirteen", "value 13-2");
    hash_insert(table, "ten", "value 10-2");
    hash_print_table(table);

    /* ハッシュテーブルを解放する */
    hash_free(table);

    return(0);
}

関連ページ

• C言語
• C言語アルゴリズム-スタック
• C言語アルゴリズム-待ち行列(キュー)
• C言語アルゴリズム-連結リスト
• C言語アルゴリズム-線形探索法
• C言語アルゴリズム-二分探索法
• C言語アルゴリズム-力まかせ探索
• C言語アルゴリズム-KMP法
• C言語アルゴリズム-BM法
• C言語アルゴリズム-ハッシュチェイン法
• C言語アルゴリズム-オープンアドレス法
• C言語アルゴリズム-二分探索木