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



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

ハッシュ法について

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


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


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

オープンアドレス法とは、ハッシュ値の衝突が発生した場合に、再ハッシュ(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);
}

関連ページ



スポンサード リンク