C言語アルゴリズム-ハッシュチェイン法
ハッシュチェイン法 (hash chain)
ハッシュ法について
ハッシュ法とは、キー値からハッシュ関数によって「ハッシュ値」を求め、ハッシュ値をバケット（bucket：ハッシュテーブルの各要素）に結びつけるデータ構造を生成し、高速な探索を実現する手法です。ハッシュ法を用いることで、データの数に関わらず挿入・探索・削除の操作を実質的に「O(1)」で行うことができます。
ハッシュ関連の用語は以下の通りです。
- ハッシュ値(hash value)
- ハッシュ関数の返す値。キーを格納する配列の添え字。
- ハッシュ表(hash table)
- データを格納する配列。
- バケット(bucket)
- ハッシュ表の各要素。
- 衝突(collision)
- 異なったキーの値から同じハッシュ値が得られること。
ハッシュチェイン法（直接連鎖法）について
ハッシュチェイン法とは、ハッシュ値の「衝突(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);
}
関連ページ
- C言語
- C言語アルゴリズム-スタック
- C言語アルゴリズム-待ち行列(キュー)
- C言語アルゴリズム-連結リスト
- C言語アルゴリズム-線形探索法
- C言語アルゴリズム-二分探索法
- C言語アルゴリズム-力まかせ探索
- C言語アルゴリズム-KMP法
- C言語アルゴリズム-BM法
- C言語アルゴリズム-ハッシュチェイン法
- C言語アルゴリズム-オープンアドレス法
- C言語アルゴリズム-二分探索木