ハッシュ法-2 オープンアドレス法
今度は衝突した場合に連結リストで対処するのではなく再ハッシュ値を求めてそこに要素を配置する方法。ここでは再ハッシュの手順を以下のようにする。
h1(x) = (h(x) + k) mod B
※Bは要素の個数
例
| キー | ハッシュ値 |
| a | 1 |
| b | 5 |
| c | 8 |
| d | 5 |
| e | 6 |
| f | 6 |
上記の要素を配置する場合、bとdのハッシュ値が衝突してしまう。そのため、dの再ハッシュ値を求める。
h(d) = (h(d) + 1) mod 10
= (5 +1) mod 10
= 6
データを登録した状態は次のようになる。
| 添字 | キー |
| 0 | |
| 1 | a |
| 2 | |
| 3 | |
| 4 | |
| 5 | b |
| 6 | d |
| 7 | e |
| 8 | c |
| 9 |
この方法で問題になるのは要素を削除する場合。データdを削除した後にデータeを検索する場合、eのハッシュ値は6なので６番目の要素を探すが削除されているので探索を終了してしまう。これを回避するため削除する時に要素を消さないで「削除済み」マークをつけて削除されていることを表現する
| 添字 | キー |
| 0 | |
| 1 | a |
| 2 | |
| 3 | |
| 4 | |
| 5 | b |
| 6 | deleted |
| 7 | e |
| 8 | c |
| 9 |
プログラムのサンプル
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUCKET_SIZE 10
#define EMPTY "empty"
#define DELETED "deleted"
typedef struct BUCKET {
char *key;
int data;
} Bucket;
/* キーのハッシュ値がテーブルの添字になる */
Bucket table[BUCKET_SIZE];
/* 与えられた文字列のハッシュ値を返却する */
int hash(char *str) {
int i = 0;
while (*str) {
i += *str++;
}
return i % BUCKET_SIZE;
}
/* ハッシュ値の再計算を行う */
int rehash(int hash) {
return (hash + 1) % BUCKET_SIZE;
}
/* キーが同じ場合1を返却、異なる場合0を返却 */
int keyequal(char *str1, char *str2) {
if (strcmp(str1, str2) == 0) {
return 1;
} else {
return 0;
}
}
/* tableの初期化 */
void init () {
int i;
char *key;
for(i = 0; i < BUCKET_SIZE; i++) {
key = malloc(strlen(EMPTY) + 1);
strcpy(key, EMPTY);
table[i].key = key;
}
}
/* 与えられたキーがテーブルに存在する場合1を返却。無い場合0を返却 */
int find(char *key) {
int h, count;
char *k;
h = hash(key);
count = 0;
while (keyequal((k = table[h].key), EMPTY) != 1) {
if (keyequal(k, DELETED) != 1 && keyequal(k, key) == 1) {
return 1;
}
if (++count >= BUCKET_SIZE) {
return 0;
}
h = rehash(h);
}
return 0;
}
int insert(char *key, int data) {
int h, count;
char *bucketkey;
/* 既に登録済みの場合終了する */
if (find(key) != 0) {
printf("既に登録済み\n");
return 0;
}
h = hash(key);
count = 0;
while (keyequal((table[h].key), EMPTY) != 1
&& keyequal((table[h].key), DELETED) != 1) {
if (++count >= BUCKET_SIZE) {
return 0;
}
h = rehash(h);
}
bucketkey = malloc(strlen(key) + 1);
strcpy(bucketkey, key);
table[h].data = data;
table[h].key = bucketkey;
return 1;
}
int delete(char *key) {
int h, count;
char *delkey;
char *k;
if (find(key) == 0) {
printf("そのキーは登録されていません\n");
return 0;
}
h = hash(key);
count = 0;
while(keyequal((k = table[h].key), EMPTY) != 1) {
if (keyequal(k, DELETED) != 1
&& keyequal(k, key) == 1) {
delkey = malloc(strlen(DELETED) + 1);
strcpy(delkey, DELETED);
table[h].key = delkey;
free(k);
k = NULL;
return 1;
}
if (++count >= BUCKET_SIZE) {
return 0;
}
h = rehash(h);
}
return 0;
}
void print_table() {
int i;
for (i = 0; i < BUCKET_SIZE; i++) {
if (keyequal(table[i].key, DELETED) != 1
&& keyequal(table[i].key, EMPTY) != 1) {
printf("%d番目 key:%s data:%d\n",
i, table[i].key, table[i].data );
}
}
}
int main(void) {
char buf[256];
char key[256];
int x, data;
init();
while (1) {
print_table();
printf("1:insert 2:delete 9:quit :");
fgets(buf, 256, stdin);
sscanf(buf, "%d", &x);
if (x == 9) {
break;
}
switch (x) {
case 1:
printf("please enter insert key:");
fgets(key, 256, stdin);
key[strlen(key) -1] = '\0';
printf("please enter insert data:");
fgets(buf, 256, stdin);
sscanf(buf, "%d", &data);
insert(key, data);
break;
case 2:
printf("please enter delete key: ");
fgets(key, 256, stdin);
key[strlen(key) -1] = '\0';
delete(key);
break;
}
}
}
追記
チェイン法とは違い最大の要素数を想定しハッシュ表を割り当てなければいけない。最大1000個のデータを扱うためには、使用率85%とすると1176個の要素を持つハッシュ表が必要。データを1個しか登録しなくてもこの数だけ必要になる。
