ハッシュ法の続きです。今回はオープンアドレス法について説明します。
オープンアドレス法の場合、チェイン法とは違ってハッシュ表に直接データをセットするので、衝突が発生したとき別の空き場所を探す手順が必要になります。この手順のことを｢再ハッシュ (rehashing)」といいます。
再ハッシュの手順はいくつかの方法がありますが、その中で最も簡単な方法が「線形走査法 (linear probing)」です。ハッシュ関数を h(x)、ハッシュ表の大きさを M とすると、k 回目の再ハッシュ関数 hk(x) は次の式で表すことができます。
最初の再ハッシュ関数 \(h_1(x)\) は (h(x) + 1) % M で、2 回目の再ハッシュ関数 \(h_2(x)\) は (h(x) + 2) % M になります。つまり、線形走査法はハッシュ表の空き場所を順番に調べていく「線形探索」と同じです。本ページでは線形走査法でオープンアドレス法の仕組みを説明することにします。このほかに「二重ハッシュ法 (double hashing)」という方法がありますが、これはあとで取り上げることにします。
最初にデータの挿入から説明します。下図を見てください。
ハッシュ表 ハッシュ表
┌───┐ ┌───┐
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ａ │ │ Ａ ┼─┐ 衝突 (E)
├───┤ ├───┤ │
│ ／ │ │ Ｅ │←┘
├───┤ ├───┤
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ｂ │ │ Ｂ ┼─┐ 衝突 (D, F)
├───┤ ├───┤ │
│ ／ │ │ Ｄ ┼←┤ 衝突 (F)
├───┤ ├───┤ │
│ Ｃ │ │ Ｃ ┼←┤ 衝突 (F)
├───┤ ├───┤ │
│ ／ │ │ Ｆ │←┘
└───┘ └───┘
A (1), B (4), C (6) を挿入 D (4), E (1), F (4) を挿入
図 : オープンアドレス法（線形走査法）
最初にデータ A, B, C を挿入します。ハッシュ値の場所 (1, 4, 6 番目) にデータをセットします。次に、データ D を挿入します。ハッシュ値は 4 ですが、B と衝突しています。線形走査法の場合、次の場所は (4 + 1) % 8 で 5 になります。そこで、D を 5 番目にセットします。同様に E を挿入しますが A と衝突しているので、その隣の場所 (2) に E をセットします。
最後に F を挿入しますが、B と衝突しています。そこで再ハッシュを行いますが、1 回目は (4 + 1) % 8 = 5 で D と衝突します。2 回目は (4 + 2) % 8 = 6 ですが、C と衝突します。3 回目で (4 + 3) % 8 = 7 になり、この場所に F を挿入します。
データの探索も簡単です。データのハッシュ値 n を求め、ハッシュ表の n 番目に格納されているデータと比較します。等しい場合は探索成功です。そうでなければ、再ハッシュを行って次のデータと比較します。そこが空き場所ならば、探索は失敗となります。
たとえば B を探す場合、ハッシュ値は 4 なので、ハッシュ表の 4 番目に格納されている値と比較します。この場合は等しいので探索成功です。F を探索する場合、最初に B と比較します。次に、再ハッシュを行い 5, 6, 7 番目と順番にデータを比較していきます。そして、7 番目の F で探索成功となります。ハッシュ値が 1 のデータ G を探索する場合は、最初に A と比較し、次に E と比較します。その次に 3 番目のデータと比較しますが、空き場所なので探索は失敗となります。
オープンアドレス法の場合、データの探索と挿入だけならば簡単なのですが、データの削除処理がからむとちょっと複雑になります。次の図を見てください。
ハッシュ表 ハッシュ表
┌───┐ ┌───┐
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ａ │ │ Ａ │
├───┤ ├───┤
│ Ｅ │ │ Ｅ │
├───┤ ├───┤
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ｂ │ │ Ｂ ┼─┐Ｆの探索
├───┤ ├───┤ │
│ Ｄ │ │ Ｄ ┼←┤探索継続
├───┤ ├───┤ │
│ Ｃ │─Ｃを削除→│ ／ │←┘終了（失敗）
├───┤ ├───┤
│ Ｆ │ │ Ｆ │
└───┘ └───┘
データを挿入した順番
A (1), B (4), C (6), D (4), E (1), F (4)
図 : データの削除 (1)
ハッシュ表 ハッシュ表
┌───┐ ┌───┐
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ａ │ │ Ａ │
├───┤ ├───┤
│ Ｅ │ │ Ｅ │
├───┤ ├───┤
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ｂ │ │ Ｂ ┼─┐Ｆの探索
├───┤ ├───┤ │
│ Ｄ │ │ Ｄ ┼←┤探索継続
├───┤ ├───┤ │
│ Ｃ │─Ｃを削除→│ＤＥＬ┼←┤探索継続
├───┤ ├───┤ │
│ Ｆ │ │ Ｆ │←┘成功
└───┘ └───┘
データを挿入した順番
A (1), B (4), C (6), D (4), E (1), F (4)
図 : データの削除 (2)
データ C を削除します。単純に考えると、ハッシュ表の 6 番目を空き場所にすればよさそうですが、実はそうはいかないのです。6 番目を空き場所にした状態で、データ F を探索してみましょう。F のハッシュ値は 4 で B と衝突します。そこで、再ハッシュを行うと (4 + 1) % 8 = 5 になりますが、ここでも D と衝突します。そして、再ハッシュを行い (4 + 2) % 8 = 6 になりますが、この場所は空き場所なので探索は失敗となります。
このように、データを単純に削除すると、再ハッシュを行ったデータをたどることができなくなるのです。そこで、削除したことを表すデータ DEL を用意します。そして、データが DEL のときは探索を続けるように手順を変更します。図 (2) を見てください。
データ C を削除する場合、その場所に DEL を書き込みます。そのあと、データ F を探索する場合、D と衝突したあとの再ハッシュで (4 + 2) % 8 = 6 になります。今度は空き場所ではなく DEL になっているので、再ハッシュを行って探索を続けます。今度はデータ F を見つけることができます。
なお、新しいデータを挿入する場合は、空き場所または削除した場所を探して、そこにデータを書き込むだけです。
オープンアドレス法の場合、データの最大数はハッシュ表の大きさに制限されます。また、データ数が多くなるとハッシュ値の衝突が頻発するため、その性能は劣化してしまいます。とくに線形走査法の場合、再ハッシュのたびに連続した領域を使用するため、データがハッシュ表に分散するのではなく、特定の領域に偏って存在するようになります。このような現象を「クラスター (clustering)」といいます。これがハッシュ値の衝突をさらに増やすことになり、線形走査法では性能が急激に悪くなります。参考文献『Ｃプログラマのためのアルゴリズムとデータ構造』によると、線形走査法の場合ハッシュ表の最大使用率は 80 % を目安にするとよいそうです。
それから、データの削除を行う場合、データだけではなく削除データ (DEL) が増えても性能が劣化することに注意してください。ようするに、オープンアドレス法の場合、ハッシュ表の空き場所が少なくなると性能が劣化するのです。データの挿入と削除を繰り返すと空き場所は減少していくので、データ数が少ない状態でも探索が遅くなる場合もあるのです。このため、オープンアドレス法で削除処理を行うときは、ハッシュ表の再構築を考慮する必要があると思われます。削除処理を行う場合は、チェイン法を使ったほうが簡単かもしれません。
それではプログラムを作りましょう。最初にデータ構造を定義します。次のリストを見てください。
リスト : データ型の定義
#define EMPTY 0
#define DEL 1
#define ANY 2
// ハッシュ表の要素
typedef struct {
int kind;
char *key;
int value;
} Item;
// ハッシュ表
typedef struct {
int size, count;
Item *table;
} HashTable1;
ハッシュ表の名前は HashTable1 としました。ハッシュ表の本体 table の要素を構造体 Item で表します。table のデータ型は Item * になります。メンバ変数 kind は空き場所 (EMPTY)、削除データ (DEL)、データ有り (ANY) を表します。メンバ変数 key がキーを、value が値を表します。
次はハッシュ表を生成する関数 make_hash_table1 を作ります。
リスト : ハッシュ表の生成と廃棄
// ハッシュ表の生成
HashTable1 *make_hash_table1(int size)
{
HashTable1 *ht = malloc(sizeof(HashTable1));
if (ht != NULL) {
ht->table = malloc(sizeof(Item) * size);
if (ht->table == NULL) {
free(ht);
return NULL;
}
ht->size = size;
ht->count = 0;
for (int i = 0; i < size; i++) {
ht->table[i].kind = EMPTY;
ht->table[i].key = NULL;
}
}
return ht;
}
最初に HashTable1 の領域を malloc で取得します。次に、table の本体を取得します。大きさは sizeof(Item) * size になります。そのあと、table を空き場所 (EMPTY) で初期化します。このとき、いっしょに key も NULL に初期化しておきます。
次は作業用の関数として、ハッシュ関数 hash_func1 とキーを探索する関数 search_keyを作ります。
リスト : 作業用関数
// ハッシュ関数
int hash_func1(HashTable1 *ht, const char *key)
{
unsigned int value = 0;
for (; *key != '\0'; key++)
value = (value << 3) + *key;
return value % ht->size;
}
// キーの探索
int search_key(HashTable1 *ht, const char *key)
{
int n = hash_func1(ht, key);
int c = 0;
Item *table = ht->table;
while (c < ht->size) {
if (table[n].kind == EMPTY) break;
if (table[n].kind == ANY && strcmp(key, table[n].key) == 0)
return n;
n = (n + 1) % ht->size;
c++;
}
return -1;
}
hash_func1 は前回作成したハッシュ関数と同じです。search_key はハッシュ表からキー key を探索し、見つけた場合はその位置 (添字) を返します。見つからない場合は -1 を返します。
最初にハッシュ値を求め変数 n にセットし、while ループでキーを探索します。table[n].kind が EMPTY であれば探索は失敗です。break で while ループを脱出して -1 を返します。kind が ANY で table[n].key と引数 key が等しい場合、探索は成功です。return で n を返します。そうでなければ、再ハッシュ (n + 1) % ht->size を行って探索を続行します。c が ht->size 以上になる場合は探索失敗です。while ループを終了して -1 を返します。
データの探索は search_key を使うと簡単です。
リスト : データの探索
int search_hash1(HashTable1 *ht, const char *key, bool *err)
{
int n = search_key(ht, key);
if (n >= 0) {
*err = true;
return ht->table[n].value;
}
*err = false;
return 0;
}
search_key を呼び出して、返り値 n が 0 以上であれば、その位置に格納されている value を返します。そうでなければ、*err に false をセットして return で 0 を返します。
次はデータを挿入する関数 insert_hash1 を作ります。次のリストを見てください。
リスト : データの挿入
bool insert_hash1(HashTable1 *ht, const char *key, int val)
{
int n = search_key(ht, key);
if (n >= 0) {
ht->table[n].value = val;
return true;
}
int c = 0;
Item *table = ht->table;
n = hash_func1(ht, key);
while (c < ht->size) {
if (table[n].kind != ANY) {
table[n].key = malloc(strlen(key) + 1);
if (table[n].key == NULL) break;
strcpy(table[n].key, key);
table[n].kind = ANY;
table[n].value = val;
ht->count++;
return true;
}
n = (n + 1) % ht->size;
c++;
}
return false;
}
最初に search_key を呼び出して同じキーがないか調べます。同じキーが見つかった場合は、キーに対応する値を引数 val に書き換えます。見つからない場合は、while ループで空き場所または削除した場所を探して、そこにデータを書き込みます。
kind が ANY でなければ、そこにデータを書き込むことができます。キーの領域を malloc で取得して、table[n].key にセットします。strcpy でキーをコピーして、kind に ANY を、value に val をセットします。そして、ht->count を +1 して true を返します。
データがセットされていれば再ハッシュ (n + 1) % ht->size を行って、空き場所または削除した場所を探します。c が ht->size 以上になったら、空き場所がないので while ループを終了して false を返します。
次はデータの削除を行う関数 delete_hash1 を作ります。
リスト : データの削除
bool delete_hash1(HashTable1 *ht, const char *key)
{
int n = search_key(ht, key);
if (n >= 0) {
ht->table[n].kind = DEL;
free(ht->table[n].key);
ht->table[n].key = NULL;
ht->count--;
return true;
}
return false;
}
メソッド search_key でハッシュ表からキー (key) を探します。見つかった場合は、kind を DEL に書き換えて、key の領域を free で解放します。それから、key を NULL に書き換えて、count を -1 してから return で true を返します。キーが見つからない場合は false を返します。
あとはとくに難しいところはないので説明は割愛いたします。詳細はプログラムリスト１をお読みください。
それでは簡単な例題として、前回と同様のテストを行ってみましょう。
リスト : 簡単なテスト
void test1(void)
{
char buff[8][12];
HashTable1 *ht = make_hash_table1(13);
bool err;
printf("-- %d, %d --\n", is_empty_hash1(ht), length_hash1(ht));
printf("----- insert -----\n");
for (int i = 0; i < 8; i++) {
sprintf(buff[i], "%d", rand());
printf("%s, %d\n", buff[i], insert_hash1(ht, buff[i], i));
}
printf("-- %d, %d --\n", is_empty_hash1(ht), length_hash1(ht));
printf("------ search ------\n");
for (int i = 0; i < 8; i++)
printf("%s, %d\n", buff[i], search_hash1(ht, buff[i], &err));
printf("------ delete ------\n");
for (int i = 0; i < 8; i++) {
printf("%s %d\n", buff[i], delete_hash1(ht, buff[i]));
int x = search_hash1(ht, buff[i], &err);
printf("%s, %d, %d\n", buff[i], x, err);
}
printf("-- %d, %d --\n", is_empty_hash1(ht), length_hash1(ht));
printf("----- delete hash -----\n");
delete_hash_table1(ht);
}
$ clang hash1.c $ ./a.out -- 1, 0 -- ----- insert ----- 1804289383, 1 846930886, 1 1681692777, 1 1714636915, 1 1957747793, 1 424238335, 1 719885386, 1 1649760492, 1 -- 0, 8 -- ------ search ------ 1804289383, 0 846930886, 1 1681692777, 2 1714636915, 3 1957747793, 4 424238335, 5 719885386, 6 1649760492, 7 ------ delete ------ 1804289383 1 1804289383, 0, 0 846930886 1 846930886, 0, 0 1681692777 1 1681692777, 0, 0 1714636915 1 1714636915, 0, 0 1957747793 1 1957747793, 0, 0 424238335 1 424238335, 0, 0 719885386 1 719885386, 0, 0 1649760492 1 1649760492, 0, 0 -- 1, 0 -- ----- delete hash -----
次はキーの個数を増やして実行時間を計測してみましょう。
リスト : 簡単なテスト２
void test2(int size)
{
HashTable1 *ht = make_hash_table1(100003);
bool err;
char buff[12];
while (length_hash1(ht) < size) {
sprintf(buff, "%d", rand());
search_hash1(ht, buff, &err);
if (!err) insert_hash1(ht, buff, 1);
}
delete_hash_table1(ht);
}
int main(void)
{
test1();
for (int i = 95000; i <= 100000; i += 250) {
clock_t s = clock();
test2(i);
printf("%d, %.3f\n", i, (double)(clock() - s) / CLOCKS_PER_SEC);
}
return 0;
}
ハッシュ表の大きさは 100003 (素数) とし、作成するデータ数を 95000 から 100000 まで増やして実行時間を計測します。結果は次のようになりました。
表 : 実行結果 (単位 : 秒) 個数 : OPEN CHAIN 個数 : OPEN CHAIN -------+----------------------+--------------- 95000 : 0.072 0.039 97750 : 0.134 0.048 95250 : 0.075 0.038 98000 : 0.164 0.044 95500 : 0.070 0.046 98250 : 0.181 0.048 95750 : 0.073 0.049 98500 : 0.177 0.049 96000 : 0.078 0.047 98750 : 0.197 0.048 96250 : 0.081 0.048 99000 : 0.177 0.050 96500 : 0.105 0.046 99250 : 0.219 0.045 96750 : 0.106 0.046 99500 : 0.282 0.050 97000 : 0.113 0.047 99750 : 0.927 0.044 97250 : 0.128 0.048 100000 : 0.782 0.049 97500 : 0.135 0.049
実行環境 : clang version 14.0.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz 最適化オプション : -O2
ハッシュ表の大きさはチェイン法も同じです。オープンアドレス法の場合、ハッシュ表に占めるデータ数が少ないうちはチェイン法と同等以上の性能を発揮しますが、空き場所が少なくなってくると性能はどんどん劣化していきます。そこで、次は｢二重ハッシュ法」を試してみましょう。
「二重ハッシュ法 (double hashing)」は二種類のハッシュ関数を使う方法です。最初のハッシュ関数を h(x), 二番目のハッシュ関数を g(x), ハッシュ表の大きさを M とすると、二重ハッシュ法は次のような手順になります。
二重ハッシュ法で g(x) = 1 とすると線形走査法になります。g(x) は簡単な関数にしないと時間がかかってしまいます。実際、g(x) は次に示すような簡単な関数で十分なようです。
g(x) = q - (h(x) % q)
q は M よりも小さな非負整数値が選ばれます。たとえば、q = 7 とすると、g(x) の値は 1 から 7 までの範囲になります。つまり、二重ハッシュ法は n (1 <= n <= q) 個おきにハッシュ表を調べていくことになります。そして、ハッシュ値によって n の値を変えることで、クラスターの発生を回避することができます。
ただし、M と n は互いに素になっていないと、ハッシュ表をすべて調べることはできません。このため、M は素数とするのが普通です。また、g(x) の値が 1 にならないように、値を +1 する方法もあります。
プログラムは次のようになります。
リスト : 二重ハッシュ法
int hash_func2(HashTable1 *ht, const char *key, int *m)
{
unsigned int value = 0;
for (; *key != '\0'; key++)
value = (value << 3) + *key;
*m = 8 - value % 7;
return value % ht->size;
}
// キーの探索
int search_sub(HashTable1 *ht, const char *key)
{
int val;
int n = hash_func2(ht, key, &val);
int c = 0;
Item *table = ht->table;
while (c < ht->size) {
if (table[n].kind == EMPTY) break;
if (table[n].kind == ANY && strcmp(key, table[n].key) == 0)
return n;
n = (n + val) % ht->size;
c++;
}
return -1;
}
関数 hash_func2 の返り値は今までと同じハッシュ値ですが、引数 *m に 2 番目のハッシュ関数 1 + (7 - n % 7) の値をセットとします。関数 search_key は、hash_func2 でハッシュ値を求めて、変数 n と val にセットします。val がハッシュ表を探索するときの増分値になります。したがって、再ハッシュの計算は (n + val) % ht->size になります。
再ハッシュの計算が異なるだけで、あとは線形走査法のプログラムと同じです。プログラムの説明は割愛しますので、詳細はプログラムリスト２をお読みください。
それでは実行結果を示します。
表 : 実行結果 (単位 : 秒) 個数 : OPEN CHAIN DOUBLE ----------------------------- 95000 : 0.072 0.039 0.048 95250 : 0.075 0.038 0.048 95500 : 0.070 0.046 0.047 95750 : 0.073 0.049 0.051 96000 : 0.078 0.047 0.054 96250 : 0.081 0.048 0.056 96500 : 0.105 0.046 0.062 96750 : 0.106 0.046 0.050 97000 : 0.113 0.047 0.056 97250 : 0.128 0.048 0.060 97500 : 0.135 0.049 0.062 97750 : 0.134 0.048 0.059 98000 : 0.164 0.044 0.076 98250 : 0.181 0.048 0.074 98500 : 0.177 0.049 0.079 98750 : 0.197 0.048 0.091 99000 : 0.177 0.050 0.081 99250 : 0.219 0.045 0.094 99500 : 0.282 0.050 0.106 99750 : 0.927 0.044 0.283 100000 : 0.782 0.049 0.253
線形走査法よりも二重ハッシュ法の方が速くなりました。二重ハッシュ法は簡単な関数でも大きな効果を発揮するようです。興味のある方はいろいろ試してみてください。
/*
* hash1.c : ハッシュ法 (オープンアドレス法)
*
* Copyright (C) 2015-2023 Makoto Hiroi
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>
#define EMPTY 0
#define DEL 1
#define ANY 2
// ハッシュ表の要素
typedef struct {
int kind;
char *key;
int value;
} Item;
// ハッシュ表
typedef struct {
int size, count;
Item *table;
} HashTable1;
// ハッシュ表の生成
HashTable1 *make_hash_table1(int size)
{
HashTable1 *ht = malloc(sizeof(HashTable1));
if (ht != NULL) {
ht->table = malloc(sizeof(Item) * size);
if (ht->table == NULL) {
free(ht);
return NULL;
}
ht->size = size;
ht->count = 0;
for (int i = 0; i < size; i++) {
ht->table[i].kind = EMPTY;
ht->table[i].key = NULL;
}
}
return ht;
}
// ハッシュ表の廃棄
void delete_hash_table1(HashTable1 *ht)
{
free(ht->table);
free(ht);
}
// ハッシュ関数
int hash_func1(HashTable1 *ht, const char *key)
{
unsigned int value = 0;
for (; *key != '\0'; key++)
value = (value << 3) + *key;
return value % ht->size;
}
// 見つけた位置を返す、未発見は -1
int search_key(HashTable1 *ht, const char *key)
{
int n = hash_func1(ht, key);
int c = 0;
Item *table = ht->table;
while (c < ht->size) {
if (table[n].kind == EMPTY) break;
if (table[n].kind == ANY && strcmp(key, table[n].key) == 0)
return n;
n = (n + 1) % ht->size;
c++;
}
return -1;
}
// 探索
int search_hash1(HashTable1 *ht, const char *key, bool *err)
{
int n = search_key(ht, key);
if (n >= 0) {
*err = true;
return ht->table[n].value;
}
*err = false;
return 0;
}
// 挿入
bool insert_hash1(HashTable1 *ht, const char *key, int val)
{
int n = search_key(ht, key);
if (n >= 0) {
ht->table[n].value = val;
return true;
}
int c = 0;
Item *table = ht->table;
n = hash_func1(ht, key);
while (c < ht->size) {
if (table[n].kind != ANY) {
table[n].key = malloc(strlen(key) + 1);
if (table[n].key == NULL) break;
strcpy(table[n].key, key);
table[n].kind = ANY;
table[n].value = val;
ht->count++;
return true;
}
n = (n + 1) % ht->size;
c++;
}
return false;
}
// 削除
bool delete_hash1(HashTable1 *ht, const char *key)
{
int n = search_key(ht, key);
if (n >= 0) {
ht->table[n].kind = DEL;
free(ht->table[n].key);
ht->table[n].key = NULL;
ht->count--;
return true;
}
return false;
}
// ハッシュ表は空か
bool is_empty_hash1(HashTable1 *ht)
{
return ht->count == 0;
}
// ハッシュ表のデータ数を返す
int length_hash1(HashTable1 *ht)
{
return ht->count;
}
// 巡回
void foreach_hash1(void (*func)(const char *, int), HashTable1 *ht)
{
Item *table = ht->table;
for (int i = 0; i < ht->size; i++) {
if (table[i].kind == ANY)
func(table[i].key, table[i].value);
}
}
// ハッシュ表をクリアする
void clear_hash1(HashTable1 *ht)
{
ht->count = 0;
for (int i = 0; i < ht->size; i++) {
if (ht->table[i].kind == ANY) {
free(ht->table[i].key);
ht->table[i].key = NULL;
}
ht->table[i].kind = EMPTY;
}
}
// 簡単なテスト
void test1(void)
{
char buff[8][12];
HashTable1 *ht = make_hash_table1(13);
bool err;
printf("-- %d, %d --\n", is_empty_hash1(ht), length_hash1(ht));
printf("----- insert -----\n");
for (int i = 0; i < 8; i++) {
sprintf(buff[i], "%d", rand());
printf("%s, %d\n", buff[i], insert_hash1(ht, buff[i], i));
}
printf("-- %d, %d --\n", is_empty_hash1(ht), length_hash1(ht));
printf("------ search ------\n");
for (int i = 0; i < 8; i++)
printf("%s, %d\n", buff[i], search_hash1(ht, buff[i], &err));
printf("------ delete ------\n");
for (int i = 0; i < 8; i++) {
printf("%s %d\n", buff[i], delete_hash1(ht, buff[i]));
int x = search_hash1(ht, buff[i], &err);
printf("%s, %d, %d\n", buff[i], x, err);
}
printf("-- %d, %d --\n", is_empty_hash1(ht), length_hash1(ht));
printf("----- delete hash -----\n");
delete_hash_table1(ht);
}
void test2(int size)
{
HashTable1 *ht = make_hash_table1(100003);
bool err;
char buff[12];
while (length_hash1(ht) < size) {
sprintf(buff, "%d", rand());
search_hash1(ht, buff, &err);
if (!err) insert_hash1(ht, buff, 1);
}
delete_hash_table1(ht);
}
int main(void)
{
test1();
for (int i = 95000; i <= 100000; i += 250) {
clock_t s = clock();
test2(i);
printf("%d, %.3f\n", i, (double)(clock() - s) / CLOCKS_PER_SEC);
}
return 0;
}
/*
* hash2.c : ハッシュ法 (二重ハッシュ法)
*
* Copyright (C) 2015-2023 Makoto Hiroi
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>
#define EMPTY 0
#define DEL 1
#define ANY 2
// ハッシュ表の要素
typedef struct {
int kind;
char *key;
int value;
} Item;
// ハッシュ表
typedef struct {
int size, count;
Item *table;
} HashTable1;
// ハッシュ表の生成
HashTable1 *make_hash_table1(int size)
{
HashTable1 *ht = malloc(sizeof(HashTable1));
if (ht != NULL) {
ht->table = malloc(sizeof(Item) * size);
if (ht->table == NULL) {
free(ht);
return NULL;
}
ht->size = size;
ht->count = 0;
for (int i = 0; i < size; i++) {
ht->table[i].kind = EMPTY;
ht->table[i].key = NULL;
}
}
return ht;
}
// ハッシュ表の廃棄
void delete_hash_table1(HashTable1 *ht)
{
free(ht->table);
free(ht);
}
// ハッシュ関数
int hash_func2(HashTable1 *ht, const char *key, int *m)
{
unsigned int value = 0;
for (; *key != '\0'; key++)
value = (value << 3) + *key;
*m = 8 - value % 7;
return value % ht->size;
}
// キーの探索
int search_sub(HashTable1 *ht, const char *key)
{
int val;
int n = hash_func2(ht, key, &val);
int c = 0;
Item *table = ht->table;
while (c < ht->size) {
if (table[n].kind == EMPTY) break;
if (table[n].kind == ANY && strcmp(key, table[n].key) == 0)
return n;
n = (n + val) % ht->size;
c++;
}
return -1;
}
// 探索
int search_hash1(HashTable1 *ht, const char *key, bool *err)
{
int n = search_sub(ht, key);
if (n >= 0) {
*err = true;
return ht->table[n].value;
}
*err = false;
return 0;
}
// 挿入
bool insert_hash1(HashTable1 *ht, const char *key, int val)
{
int n = search_sub(ht, key);
if (n >= 0) {
ht->table[n].value = val;
return true;
}
int m, c = 0;
Item *table = ht->table;
n = hash_func2(ht, key, &m);
while (c < ht->size) {
if (table[n].kind != ANY) {
table[n].key = malloc(strlen(key) + 1);
if (table[n].key == NULL) break;
strcpy(table[n].key, key);
table[n].kind = ANY;
table[n].value = val;
ht->count++;
return true;
}
n = (n + m) % ht->size;
c++;
}
return false;
}
// 削除
bool delete_hash1(HashTable1 *ht, const char *key)
{
int n = search_sub(ht, key);
if (n >= 0) {
ht->table[n].kind = DEL;
free(ht->table[n].key);
ht->table[n].key = NULL;
ht->count--;
return true;
}
return false;
}
// ハッシュ表は空か
bool is_empty_hash1(HashTable1 *ht)
{
return ht->count == 0;
}
// ハッシュ表の要素の個数
int length_hash1(HashTable1 *ht)
{
return ht->count;
}
// 巡回
void foreach_hash1(void (*func)(const char *, int), HashTable1 *ht)
{
Item *table = ht->table;
for (int i = 0; i < ht->size; i++) {
if (table[i].kind == ANY)
func(table[i].key, table[i].value);
}
}
// ハッシュ表をクリアする
void clear_hash1(HashTable1 *ht)
{
ht->count = 0;
for (int i = 0; i < ht->size; i++) {
if (ht->table[i].kind == ANY) {
free(ht->table[i].key);
ht->table[i].key = NULL;
}
ht->table[i].kind = EMPTY;
}
}
// 簡単なテスト
void test1(void)
{
char buff[8][12];
HashTable1 *ht = make_hash_table1(13);
bool err;
printf("-- %d, %d --\n", is_empty_hash1(ht), length_hash1(ht));
printf("----- insert -----\n");
for (int i = 0; i < 8; i++) {
sprintf(buff[i], "%d", rand());
printf("%s, %d\n", buff[i], insert_hash1(ht, buff[i], i));
}
printf("-- %d, %d --\n", is_empty_hash1(ht), length_hash1(ht));
printf("------ search ------\n");
for (int i = 0; i < 8; i++)
printf("%s, %d\n", buff[i], search_hash1(ht, buff[i], &err));
printf("------ delete ------\n");
for (int i = 0; i < 8; i++) {
printf("%s %d\n", buff[i], delete_hash1(ht, buff[i]));
int x = search_hash1(ht, buff[i], &err);
printf("%s, %d, %d\n", buff[i], x, err);
}
printf("-- %d, %d --\n", is_empty_hash1(ht), length_hash1(ht));
printf("----- delete hash -----\n");
delete_hash_table1(ht);
}
void test2(int size)
{
HashTable1 *ht = make_hash_table1(100003);
bool err;
char buff[12];
while (length_hash1(ht) < size) {
sprintf(buff, "%d", rand());
search_hash1(ht, buff, &err);
if (!err) insert_hash1(ht, buff, 1);
}
delete_hash_table1(ht);
}
int main(void)
{
test1();
for (int i = 95000; i <= 100000; i += 250) {
clock_t s = clock();
test2(i);
printf("%d, %.3f\n", i, (double)(clock() - s)/CLOCKS_PER_SEC);
}
return 0;
}