C言語アルゴリズム-ハッシュチェイン法



ハッシュチェイン法 (hash chain)

ハッシュ法について

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


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


ハッシュチェイン法(直接連鎖法)について

ハッシュチェイン法とは、ハッシュ値の「衝突(collision)」を回避するために、同一ハッシュ値をもつデータを連結リストとして構造する方法です。

登録できるデータ数は、連結リストの性質上、論理的には無限(メモリ容量内)となります。ただし、データ探索においては連結リストを探索することになるため,同一ハッシュ値が出ることが少ないように工夫(連結リストをできるだけ短くすること)をしなければ、ハッシュ法の高速性が損なわれることとなります。


ハッシュチェインのデータ構造

同一のハッシュ値が生成される要素(セル)を連結リストにしてハッシュテーブルに登録します。

table[0]:->{key1:val1}->{key2:val2}
table[1]:->{key3:val3}
table[2]:->{key4:val4}->{key5:val5}->{key6:val6}
  :
  :

C言語によるハッシュチェイン法のサンプルプログラム

ハッシュキー(文字列)とデータ(文字列)をハッシュチェイン法で登録します。

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

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

struct cell{
    char *key;
    char *data;
    struct cell *next;
};
typedef struct cell cell_t;

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

    /* ハッシュテーブルをNULLで初期化する */
    for(cnt = 0; cnt < BUCKET_SIZE; cnt++){
        table[cnt] = NULL;
    }
    return;
}

/*!
 * @brief      ハッシュリストからセルを解放する
 * @param[in]  cell  セルへのアドレス
 */
static void
cell_free(cell_t *cell)
{
    if(cell->key  != NULL) free(cell->key);
    if(cell->data != NULL) free(cell->data);
    free(cell);
    return;
}

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

    for(cnt = 0; cnt < BUCKET_SIZE; cnt++){
        temp = table[cnt];
        /* リストの解放 */
        while(temp != NULL){
            swap = temp->next;
            cell_free(temp);
            temp = swap;
        }
    }
    hash_init(table);
    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]  table  ハッシュテーブル
 * @param[in]  key    ハッシュキー
 * @return     データへのポインタ。存在しない場合にはNULLを返す。
 */
char *
hash_search(cell_t **table, char *key)
{
    int hashval = get_hash_value(key);
    cell_t *hp  = table[hashval];

    for(; hp != NULL; hp = hp->next){
        if(strcmp(key, hp->key) == 0) return(hp->data);
    }

    return(NULL);
}

/*!
 * @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(strncpy(*dest, src, length) == NULL){
        fprintf(stderr, "ERROR: %s(%d line)\n", strerror(errno), __LINE__);
        return(-1);
    }

    return(0);
}

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

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

    /* セル領域を確保する */
    p = (cell_t *)malloc(sizeof(cell_t));
    if(p == NULL){
        fprintf(stderr, "ERROR: %s(%d line)\n", strerror(errno), __LINE__);
        return(-1);
    }

    /* キーとデータをセルに保存する */
    if(strcpy_alloc(&(p->key), key) != 0) return(-1);
    if(strcpy_alloc(&(p->data), data) != 0) return(-1);

    /* セルをハッシュテーブルに登録する */
    hashval = get_hash_value(key);
    p->next = table[hashval];
    table[hashval] = p;

    return( 0 );
}

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

    /* ハッシュキーがハッシュテーブルに存在しているか確認する */
    target = table[hashval];
    if(target == NULL){
        fprintf(stderr, "target[%s] is not exist in hash table.\n", key);
        return(-1);
    }
    chain = target->next;

    /* リストの先頭要素を削除する場合 */
    if(strcmp(key, target->key) == 0){
        table[hashval] = chain;
        cell_free(target);
        return(0);
    }

    /* 先頭以外の要素を削除する場合 */
    while(target != NULL){
        if(strcmp(key, target->key) == 0){
            chain->next = target->next;
            cell_free(target);
            return( 0 );
        }
        chain  = target;
        target = target->next;
    }

    return(-1);
}

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

    for(cnt = 0; cnt < BUCKET_SIZE; cnt++){
        if(table[cnt] != NULL){
            printf("table[%d]:{", cnt);
            chain = table[cnt];
            /* リスト内部を走査して出力する */
            for(; chain != NULL; chain = chain->next){
                printf("{%s:", (chain->key));
                printf("%s}", (chain->data));
            }
            printf("}\n");
        }
    }
}

int
main(void)
{
    cell_t *table[BUCKET_SIZE];

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

    /* データを登録する */
    hash_insert(table, "one",   "val1");
    hash_insert(table, "two",   "val2");
    hash_insert(table, "three", "val3");
    hash_insert(table, "four",  "val4");
    hash_insert(table, "five",  "val5");
    hash_insert(table, "seven", "val7");
    hash_print_table(table);

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

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

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

    return(0);
}

関連ページ



スポンサード リンク