【C言語】ハッシュ法（データ探索アルゴリズム）について分かりやすく解説

このページにはプロモーションが含まれています

このページでは、データ探索アルゴリズムの１つである “ハッシュ法” について解説していきます。

Contents

事前学習：最も単純な探索
ハッシュ法
衝突（ハッシュ法の問題点）
衝突を解決する手法
まとめ

事前学習：最も単純な探索

ここから説明するハッシュ法の特徴の１つは、衝突が発生しなければ、探索に必要な計算量のオーダーが O(1) であることです（”衝突” については後述で解説します）。

計算量のオーダーが O(1) であるということは、データの個数がいくつ増えようがデータの探索速度は変わらないということになります（衝突が発生しなければ）。素晴らしい探索アルゴリズムですね！

ただ、ハッシュ法をわざわざ使わなくても、計算量のオーダーが O(1) で済むデータの探索方法は簡単に考え出すことができます（いろいろ条件がつきますが）。

で、この方法の考え方は、ハッシュ法の基にもなるものですので、まずはこの方法について説明していきたいと思います。

ダイレクトアクセス法

例えば 0 〜 9 の整数のうちの５つが、”重複無し” でランダムに配列に格納されているとします（この節では、配列内のデータが “重複なし” であることを前提として解説していきます）。

この中から 0 〜 9 のうちの特定の値 x を探索する（配列内に格納されているかどうかを判断する）にはどうすれば良いでしょう？

例えば線形探索であれば、配列の先頭から１つずつ、x と一致するかどうかを確認すれば、配列の中から x を探索することができます。ただこの場合、最悪５回の比較が必要になってしまいます（平均で５/２回）。

では、もし配列に格納される整数が “必ず配列の添字と一致する位置に格納されている” という前提があればどうでしょう？

例えば配列に格納される整数が 0, 2, 5, 7, 9 だとすれば、配列には下の図のように格納されることになります（配列の添字は 0 から始まるものとしています）。

この時、この配列の中から特定の値 x を探索するにはどうすれば良いでしょうか？

簡単ですね！

“必ず配列の添字と一致する位置に格納されている” のですから、添字 x の位置の配列の中身と x とが一致するかどうかを確認すれば良いだけです。

一致していた場合、その位置に、探索したいデータ x が存在することになります。

もし一致しなかった場合は、配列の中に x は存在しないことになります。

いずれにせよ、この方法でデータの格納とデータの探索を行えば、探索に必要な比較回数は１回のみになります。

実装の仕方によっては、サイズチェックや探索先が空であるかどうかのチェックも行う場合があり、この場合は比較回数は１回にはなりませんが、それでも計算量のオーダーとしては O(1) となります（データの個数に関係なく探索可能）。

要は、探索したいデータが配列のどの位置に格納されるかが決まっているので、データを探索する際はその位置を調べれば良いだけになります。ここがこの探索方法の最大のポイントです。

ここからは、説明を簡単にするため、ここまで紹介してきた探索方法を “ダイレクトアクセス法” と呼ばせていただきます（一般用語ではないので注意してください。ちなみにダイレクトアクセス自体は一般用語です）。

ダイレクトアクセス法のサンプル実装

このダイレクトアクセス法を C言語 でプログラミングすれば、下記のようになります。

ダイレクトアクセス法

#include <stdio.h>

/* 配列のサイズ */
#define NUM_ELEM 1000

/* 各要素の状態を表す定数 */
#define FULL 0
#define EMPTY 1

/* 各要素の中身を表現する構造体 */
typedef struct _ELEM {
    unsigned int data; /* 格納するデータ */
    int state; /* 要素の状態 */
} ELEM;

/* データの格納先の配列 */
static ELEM data_table[NUM_ELEM];

/******************************
 * 配列を初期化する関数
 ******************************/ 
void initialize(void) {
    int i;

    for (i = 0; i < NUM_ELEM; i++) {
        data_table[i].data = 0;
        data_table[i].state = EMPTY;
    }
}

/******************************
 * 配列に対して終了処理を行う関数
 ******************************/ 
void finalize(void) {
    int i;

    for (i = 0; i < NUM_ELEM; i++) {
        data_table[i].data = 0;
        data_table[i].state = EMPTY;
    }
}

/******************************
 * 配列にデータを追加する関数
 * data：追加したいデータ
 * 返却値：追加した位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
ELEM* add(unsigned int data) {    

    if (data >= NUM_ELEM) {
        return NULL;
    }

    /* dataを添字とする位置の要素にデータ格納 */
    if (data_table[data].state == EMPTY) {
        data_table[data].data = data;
        data_table[data].state = FULL;

        return &data_table[data];
    }

    return NULL;
}

/******************************
 * 配列からデータを探索する関数
 * data：探索したいデータ
 * 返却値：見つかった位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
ELEM* search(unsigned int data) {

    if (data >= NUM_ELEM) {
        return NULL;
    }

    /* dataを添字とする位置の要素と比較 */
    if (data_table[data].state != EMPTY) {
        if (data_table[data].data == data) {

            /* dataが見つかった */
            return &data_table[data];
        }
    }

    return NULL;
}

/******************************
 * 配列からデータを削除する関数
 * data：削除したいデータ
 * 返却値：削除した位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
ELEM* delete(unsigned int data) {

    if (data >= NUM_ELEM) {
        return NULL;
    }

    /* dataを添字とする位置の要素を空にする */
    if (data_table[data].state != EMPTY) {
        if (data_table[data].data == data) {

            /* 配列の要素の状態を空に設定 */
            data_table[data].state = EMPTY;

            return &data_table[data];
        }
    }

    return NULL;
}

int main(void) {
    unsigned int datas[10] = {
        100, 500, 245, 325, 999,
        0, 199, 1, 98, 777
    };
    int i;

    initialize();

    /* データの格納 */
    for (i = 0; i < 10; i++) {
        if (add(datas[i])) {
            printf("%d is ADDED\n", datas[i]);
        }
    }

    /* データの探索 */
    for (i = 0; i < 10; i++) {
        if (search(datas[i])) {
            printf("%d is FOUND\n", datas[i]);
        }
    }

    /* データの探索が失敗することを確認 */
    if (search(987)) {
        printf("%d is FOUND\n", 987);
    }
    
    if (search(654)) {
        printf("%d is FOUND\n", 654);
    }

    /* データの削除が失敗することを確認 */
    if (delete(654)) {
        printf("%d is DELETED\n", 654);
    }

    /* データの削除 */
    for (i = 0; i < 10; i++) {
        if (delete(datas[i])) {
            printf("%d is DELETED\n", datas[i]);
        }
    }

    finalize();

    return 0;
}

ソースコードの解説

簡単に上記のソースコードについて解説しておきます。基本は、ここまで解説してきたダイレクトアクセス法をそのまま実装したものになります。

ただし、データの格納先・データの探索先の配列は下記の ELEM 構造体の配列としているところにちょっと注意が必要です。

ELEM構造体

/* 各要素の中身を表現する構造体 */
typedef struct _ELEM {
    unsigned int data; /* 格納するデータ */
    int state; /* 要素の状態 */
} ELEM;

/* データの格納先の配列 */
static ELEM data_table[NUM_ELEM];

わざわざ構造体を用意しているのは、配列の要素が “空であるか” どうかを判断できるようにするためです。具体的には、その要素が “空であるか” どうかの情報を state メンバで管理するようにしています。

また、格納するデータそのものは data メンバに格納するようにしています。

データを格納する際には、この ELEM 構造体の配列である data_table の各要素の data メンバにそのデータを格納します。

さらに、データの格納を行なった際には、state メンバを FULL にすることで、その要素が空きでないことを示すようにしています（FULL はソースコードの先頭付近で #define で定義した定義値になります）。

今回はデータの重複がないことを前提としているため、この state メンバは不要と言えば不要なのですが、今後説明するハッシュ法（特に衝突への対応時）においては、この state メンバが活躍します。

また、実際にデータの格納・データの探索を行なっているのは下記の関数になります。

データの格納：add
データの探索：search

add においては、引数 data を添字とした data_table[data] の data メンバに data をセットする処理を行なっています（同時に state メンバに FULLも格納）。

addでのデータの格納

data_table[data].data = data;
data_table[data].state = FULL;

これにより、data が配列内に存在するのであれば、必ず data_table[data] の位置に存在することになります。

ですので、search においては data_table[data] の中身が引数 data と一致するかどうかの確認を行うようにしています。

一致した場合は、そのデータが存在する要素の位置のアドレス、すなわち &data_table[data] を返却するようにしています。

searchでのデータの探索

if (data_table[data].data == data) {

    /* dataが見つかった */
    return &data_table[data];
}

一致しなかった場合は NULL を返却するようにしていますので、これらの返却値からデータの探索に成功したかどうかを判断することができます。

また、ここまでの解説では触れませんでしたが、配列からデータを削除する関数 delete も用意しています（ハッシュ法を実現する上で最低限必要になのは “データの格納” と” データの探索” のみですが、以降で紹介するオープンアドレス法ではこの “データの削除” も重要になりますので、それに合わせて削除する関数 delete も用意しています）。

この削除においては、search 同様に引数 data を持つ要素を探索し、見つかった場合には、その位置の要素の state メンバを EMPTY にセットするようにしています。

deleteでのデータの削除

if (data_table[data].data == data) {

    /* バケットの状態を空に設定 */
    data_table[data].state = EMPTY;

    return &data_table[data];
}

main 関数では上記の関数を使用して、データの格納時・データの探索時・データの削除時の動作、さらには、これらに失敗する時の動作を確認するような処理を行なっています。

今後ハッシュ法を解説していきますが、このダイレクトアクセス法のソースコードをベースにしてサンプル実装などを紹介していきたいと思います。

ダイレクトアクセス法による構造体の探索

ここまで整数を探索することを前提にして解説してきましたが、ダイレクトアクセス法で構造体の特定のメンバに対して探索を行うことも可能です。

この場合、データを格納する際には、その “メンバの値を配列の添字” とする位置に構造体のデータを格納するようにします。

さらに、データを探索する際には、その “メンバの値を配列の添字” とする位置に構造体のデータが存在するかを調べるようにします。

要は、データそのもの（構造体そのもの）ではなく、構造体の特定のメンバに対してここまで解説してきた内容を実施すれば、構造体に対してハッシュ法を適用することが可能です。

例えば下記は、Person 構造体に対するダイレクトアクセス法での探索プログラムのソースコードになります（Person 構造体の height メンバに対してデータを探索する例）。

ダイレクトアクセス法（構造体）

#include <stdio.h>

/* 配列のサイズ */
#define NUM_ELEM 1000

/* 各要素の状態を表す定数 */
#define FULL 0
#define EMPTY 1

/* 人を表現する構造体 */
typedef struct _PERSON {
    unsigned int height;
    unsigned int weight;
} PERSON;

/* 各要素の中身を表現する構造体 */
typedef struct _ELEM {
    PERSON data; /* 格納するデータ */
    int state; /* 要素の状態 */
} ELEM;

/* データの格納先の配列 */
static ELEM data_table[NUM_ELEM];

/******************************
 * 配列を初期化する関数
 ******************************/ 
void initialize(void) {
    int i;

    for (i = 0; i < NUM_ELEM; i++) {
        data_table[i].data.height = 0;
        data_table[i].data.weight = 0;
        data_table[i].state = EMPTY;
    }
}

/******************************
 * 配列に対して終了処理を行う関数
 ******************************/ 
void finalize(void) {
    int i;

    for (i = 0; i < NUM_ELEM; i++) {
        data_table[i].data.height = 0;
        data_table[i].data.weight = 0;
        data_table[i].state = EMPTY;
    }
}

/******************************
 * 配列にデータを追加する関数
 * data：追加したいデータ
 * 返却値：追加した位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
ELEM* add(PERSON *data) {    

    if (data->height >= NUM_ELEM) {
        return NULL;
    }

    /* dataを添字とする位置の要素にデータ格納 */
    if (data_table[data->height].state == EMPTY) {
        data_table[data->height].data = *data;
        data_table[data->height].state = FULL;

        return &data_table[data->height];
    }

    return NULL;
}

/******************************
 * 配列からデータを探索する関数
 * data：探索したいデータ
 * 返却値：見つかった位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
ELEM* search(PERSON *data) {

    if (data->height >= NUM_ELEM) {
        return NULL;
    }

    /* dataを添字とする位置の要素と比較 */
    if (data_table[data->height].state != EMPTY) {
        if (data_table[data->height].data.height == data->height) {

            /* dataが見つかった */
            return &data_table[data->height];
        }
    }

    return NULL;
}

/******************************
 * 配列からデータを削除する関数
 * data：削除したいデータ
 * 返却値：削除した位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
ELEM* delete(PERSON *data) {

    if (data->height >= NUM_ELEM) {
        return NULL;
    }

    /* dataを添字とする位置の要素を空にする */
    if (data_table[data->height].state != EMPTY) {
        if (data_table[data->height].data.height == data->height) {

            /* 配列の要素の状態を空に設定 */
            data_table[data->height].state = EMPTY;

            return &data_table[data->height];
        }
    }

    return NULL;
}

int main(void) {
    PERSON datas[10] = {
        175, 65,
        180, 84,
        200, 105,
        100, 30,
        165, 48,
        158, 51,
        220, 85,
        190, 100,
        85, 20,
        180, 130
    };
    int i;
    PERSON data;

    initialize();

    for (i = 0; i < 10; i++) {
        if (add(&datas[i])) {
            printf("(%d, %d) is ADDED\n", datas[i].height, datas[i].weight);
        }
    }

    for (i = 0; i < 10; i++) {
        if (search(&datas[i])) {
            printf("(%d, %d) is FOUND\n", datas[i].height, datas[i].weight);
        }
    }

    data.height = 200;
    data.weight = 30;
    if (add(&data)) {
        printf("(%d, %d) is ADDED\n", data.height, data.weight);
    }

    data.height = 170;
    data.weight = 30;
    if (search(&data)) {
        printf("(%d, %d) is FOUND\n", data.height, data.weight);
    }
    
    data.height = 200;
    data.weight = 30;
    if (search(&data)) {
        printf("(%d, %d) is FOUND\n", data.height, data.weight);
    }

    if (delete(&data)) {
        printf("(%d, %d) is DELETED\n", data.height, data.weight);
    }

    for (i = 0; i < 10; i++) {
        if (delete(&datas[i])) {
            printf("(%d, %d) is DELETED\n", datas[i].height, datas[i].weight);
        }
    }

    finalize();

    return 0;
}

こんな感じで、探索対象のデータが構造体である場合においても、ここまで解説してきたダイレクトアクセス法は適用することが可能です。

次に解説するハッシュ法に関しても同様に探索対象のデータが構造体であっても適用することが可能です。が、解説を簡単にするため、基本的には解説の中で構造体については取り扱いません。といっても、構造体のデータの探索には適用できないというわけではないのでご注意ください。

ダイレクトアクセス法の問題点

次はここまで解説してきたダイレクトアクセス法の問題点について説明していきたいと思います。

ダイレクトアクセス法は非常に高速に探索可能ですが、下記の２つの問題点があります。

配列のサイズが大きくなりやすい
探索可能なデータが限定されている

配列のサイズが大きくなりやすい

問題点の１つは “配列のサイズが大きくなりやすい” です。

ダイレクトアクセス法では、配列に格納する整数は、添字がその整数と一致する配列の位置に格納する必要があります（例えば配列 array に x を格納するのであれば、array[x] の位置に x を格納する）。

ですので、用意する配列のサイズは、格納するデータの個数に関わらず格納するデータが取りうる値の パターン数 となります。

例えば前述で紹介した例においては、格納する整数 0 〜 9 に限定していたので配列のサイズは 10 で十分です。ですが、格納する整数の種類数が大きければ大きいほど、必要になる配列のサイズが大きくなってしまいます。

例えば unsigned int 型のどの整数でも配列に格納されうるとすれば、unsigned int 型の最大値は 4294967295 なので、必要な配列のサイズは 4294967296 になります。

さらに、配列の型が unsigned int 型であることを考慮すれば、unsigned int 型のサイズは 4 バイトなので、この配列を用意するだけで１６ GB のメモリが必要になることになります（少なくとも私の PC ではメモリ足りない…）。

で、本当に必要な配列のサイズは 格納するデータの個数 のみですので、格納するデータが取りうる値のパターン数が多い＆格納するデータの個数が少ないような場合は無駄にメモリを使用することになるのでもったいないです。

そもそも巨大なメモリを使用できない環境も多いはずです。

MEMO

ここでは unsigned int 型のサイズを 4 バイトとして説明していますが、環境によってはサイズが異なる場合があるのでご注意ください

探索可能なデータが限定されている

もう１つの問題点は、”探索対象に出来るデータが限定されている” という点です。

要は、格納するデータ（もしくは格納する構造体のメンバ）を配列の添字とするので、配列の添字に指定できる形式のデータしか探索することができません（配列に格納することができないので）。

C言語 の場合、配列の添字は 0 を含む正の整数のみですので、探索できるデータもこれらのみとなってしまいます。

ですので、負の整数や浮動小数点数、文字列等を探索することができません。

これらの問題があるので、ここで紹介したダイレクトアクセス法は使い所が少ないです（もちろん使えるケースもあると思います）。

で、このダイレクトアクセス法の考え方を踏襲し、さらにこれらの問題点を解決して実用的なものにしたのが、今回紹介するハッシュ法になります（踏襲しているというよりも、ダイレクトアクセス法は、実はハッシュ法の１つの実装形態とも言えます）。

ハッシュ法

では、本題のハッシュ法について解説していきます。

前述の通り、このハッシュ法は、最も単純な探索で紹介したダイレクトアクセス法を踏襲したものになります。踏襲するのは、”配列のどの位置に格納されるかが決まっているので、探索する際はその位置を調べれば良いだけ” という考え方です。

ダイレクトアクセス法においては、データそのものを配列の格納する位置（配列の添字）としてきましたが、ハッシュ法においては、その位置はハッシュ関数によって求めることになります。

ハッシュ関数

ハッシュ関数とは、入力された任意のデータに対して “何らかの処理” を行って値を算出する関数のことを言います。このハッシュ関数で算出される値をハッシュ値と呼びます。

“何らかの処理” と言われると曖昧で困ってしまうかもしれませんが、ハッシュ関数で行う処理は下記さえ満たしていれば原理的にはどのような処理であっても良いです。

同じ入力データに対して、毎回同じハッシュ値が算出できる

原理的には上記のみを満たしていれば良いのですが、現実的には、ハッシュ関数で算出するハッシュ値は固定長データであることが望まれます。

“固定長データ” の分かりやすい例は、特定の範囲内に必ず収まるような整数です。

例えば 0 〜 255 の整数のみのハッシュ値（この場合、8 ビットの固定長データとなる）を算出したり、0 〜 65535 の整数のみのハッシュ値（この場合、16 ビットの固定長データとなる）を算出する感じですね。

MEMO

例えば 0 〜 255 の整数のみのハッシュ値であれば、これらの値は 00000000 〜 11111111 の８桁の２進数で表現できるので、8 ビットの固定長データであるといえます

また、0 〜 65535 の整数のみのハッシュ値であれば、これらの値は 0000000000000000 〜 1111111111111111 の１６桁の２進数で表現できるので 16 ビットの固定長データであるといえます

特にハッシュ法におけるハッシュ値は配列の添字として利用されますので、配列の添字として扱える値、具体的には 0 〜 配列のサイズ未満 の整数を入力データから算出するハッシュ関数を用意する必要があります。

ハッシュ関数の例

ここで、より具体的にハッシュ関数のイメージを掴みやすくするために、ハッシュ関数の具体例を紹介していきます。ハッシュ関数が算出するハッシュ値の取りうる値の範囲は 0 〜 N - 1 であるものとして解説していきます（N は 配列のサイズ以下 の値）。

整数に対するハッシュ関数

例えば下記は、引数により入力された int 型の整数を unsigned int 型に変換し、その変換結果に対して N で剰余算を行なった結果をハッシュ値とするハッシュ関数の例となります。

ハッシュ関数の例１

unsigned int hash(int data) {
    unsigned int u_data = data;

    return u_data % N;
}

上記のハッシュ関数であれば、入力された int 型の値が負の値であっても、配列の添字として使用できる整数をハッシュ値として求めることができます。

文字列に対するハッシュ関数

また、文字列を入力データとしてハッシュ値を求めるようなハッシュ関数も作成することができます。その一例が下記になります。

ハッシュ関数の例２

unsigned int hash(char *data) {
    unsigned int i;
    unsigned int sum;

    sum = 0;
    for (i = 0; i < strlen(data); i++) {
        sum += data[i];
    }

    return sum % N;
}

要は、文字列の各文字のアスキーコードを足し合わせ、最後に N で剰余算する関数です。

浮動小数点数に対するハッシュ関数

浮動小数点数に対するハッシュ値を求めるハッシュ関数も同様に作成できます。下記がその一例になります。

ハッシュ関数の例３

unsigned int hash(double data) {
    unsigned int u_data;

    u_data = data * 10000;

    return u_data % N;
}

適当な値を入力されたデータに掛け算を行なった後に、N で剰余算を行なっています。

こんな感じで、入力されたデータに対して “何らかの処理” を行なって値を算出するのがハッシュ関数になります。

また、入力されるデータがどのようなデータであっても、ハッシュ関数さえきちんと作成してやればハッシュ値は算出可能です。

どんなデータでも入力可能なハッシュ関数

上記の例の場合、入力されるデータに応じてハッシュ関数を呼び分ける必要がありますが、C言語 であれば下記のように void * ポインタを利用することで、どんなデータであっても１つのハッシュ関数からハッシュ値を求めるようなことも可能です。

ハッシュ関数の例４

unsigned int hash(void *data, unsigned int size) {
    unsigned int i;
    unsigned char *p = data;
    unsigned int sum;

    sum = 0;
    for (i = 0; i < size; i++) {
        sum += p[i];
    }

    return sum % N;
}

上記においては、引数 data を先頭アドレスとしたサイズ size 分のデータを１バイトずつに分解し、その１バイトずつの値を加算して最後に N で剰余算を行なっています。このようなハッシュ関数であれば、入力データが画像データなどの場合でもハッシュ値を算出することが可能です。

ここまでに４つのハッシュ関数を紹介しましたが、これらの関数は全て、同じ入力データに対して毎回同じハッシュ値が算出できるという点を満たしていることもポイントになります。

ダメなハッシュ関数の例

逆に、同じ入力データに対して毎回同じハッシュ値を算出することができない、ダメなハッシュ関数の例も紹介しておきたいと思います。

例えば下記のような関数だと、同じ入力データを引数で指定しても、実行するたびに算出する値が異なるため、ハッシュ関数としては相応しくありません。

ダメなハッシュ関数の例１

unsigned int hash(int data) {
    unsigned int u_data = data;
    static unsigned int i = 0;

    /* 実行するたびにiの値が変わるのでダメ */
    u_data += i;
    i++;

    return u_data % N;
}

下記もダメなハッシュ関数の例になります。

ダメなハッシュ関数の例２

unsigned int hash(int data) {
    unsigned int u_data = data;

    /* 実行するたびにrand()の値が変わるのでダメ */
    u_data += rand();

    return u_data % N;
}

ハッシュ法での探索

上記のハッシュ関数を利用してデータを探索するアルゴリズムが、ハッシュ法になります。

ハッシュ法は “データを探索する” アルゴリズムですが、このアルゴリズムを適用するためにはデータの配列への格納に対しても工夫が必要になります。

ハッシュ法におけるデータの格納

まずハッシュ法においては、データを配列に格納する際に、そのデータに対してハッシュ関数を実行してハッシュ値を算出します（データが構造体の場合は、探索する際のキーとなるメンバの値をハッシュ値に変換する）。

そしてそのデータを、ハッシュ値を添字とする配列の位置に格納します。

例えば配列が array で格納するデータが x、さらにハッシュ関数が hash なのであれば、x は array[hash(x)] の位置に格納します。

ハッシュ法におけるデータの探索

さらに、データを探索する際には、データを格納した時と同じハッシュ関数を利用して探索したいデータからハッシュ値を算出し、そのハッシュ値を添字とする配列の位置を探索します（その探索したいデータが格納されているかどうかを判断する）。

例えば、探索したいデータが x で、さらに配列が array でハッシュ関数が hash なのであれば、array[hash(x)] に格納されているデータと x が一致するかどうかを判断します。

もし一致した場合、データ x は配列内に存在することになり、これで探索が完了となります。

以上が、ハッシュ法での探索の流れとなります。

ハッシュテーブルとバケット

ちょっとここで、ハッシュ法における用語について紹介しておきます。

ハッシュ法でデータの格納先となる配列を “ハッシュテーブル”、さらに、その配列の各要素を “バケット” と呼びます。例えばデータの格納先の配列が array なのであれば、array 自体がハッシュテーブルで、array[x] や array[y] 等がバケットになります。

今後はこれらの用語を用いて解説していきます。

ハッシュ法が O(1) で探索できる理由

では、なぜハッシュ法では、ハッシュ値の位置を調べるのみで探索が完了するのでしょうか？

その理由は、根本的には最初に紹介したダイレクトアクセス法と同じです。

要は、ハッシュ法においても “配列のどの位置に格納されるかが決まっているので、探索する際はその位置を調べれば良いだけ” が成立するからです。

さらに、これが成立する理由は、データを格納する際にもデータを探索する際にも、位置を決める際に（配列の添字を決める際に）同じハッシュ関数を使用しているからです。

前述の通り、ハッシュ関数は同じ入力データに対して、毎回同じハッシュ値が算出できるを満たしています。

ですので、格納時と探索時で同じハッシュ関数を利用した場合、同じデータからは必ず同じハッシュ値が算出できます。さらに、このハッシュ値の位置にデータを格納するようにしているので、探索したいデータが配列に存在する場合、その探索したいデータに対するハッシュ値の位置に必ず存在するはずです。

つまり、ハッシュ関数によりどの位置を探索すれば良いかが分かるので、ダイレクトアクセス法同様に比較回数１回のみで探索を行うことが可能です。

ただ、計算量が１回のみというわけではないので注意してください。ハッシュ関数の作り方によっては、ハッシュ関数の中でたくさんの演算が行われる可能性もあります。

例えば下記の場合、文字列の文字数が多いと、その分計算量も増えます。

計算量の多いハッシュ関数の例

unsigned int hash(char *data) {
    unsigned int i;
    unsigned int sum;

    sum = 0;
    for (i = 0; i < strlen(data); i++) {
        sum += data[i];
    }

    return sum % N;
}

ただし、計算量のオーダーで考えた場合、この計算量のオーダーは “データの個数の増加” に応じてどれくらい計算量が増加するかの割合を示すものであり、ハッシュ法の場合はデータの個数に計算量は依存しないため、計算量のオーダーは O(1) となります。

ダイレクトアクセス法に対するハッシュ法のメリット

このハッシュ法では、ダイレクトアクセス法における問題点の下記の２つを解決することができます。

配列のサイズが大きくなりやすい
探索可能なデータが限定されている

配列のサイズは自身で決められる

ダイレクトアクセス法では、配列に格納するデータそのものを配列の添字とするため、扱うデータのパターン数が多いと配列サイズも大きくしないといけないという問題がありました。

その一方でハッシュ法の場合、ハッシュテーブル（配列）の添字とするのはハッシュ値であり、ハッシュ関数の作りによって必ずハッシュ値が特定の値未満になるようにすることも可能です。

ですので、必要になるハッシュテーブルのサイズを予め決めておき、それに合わせてハッシュ関数を作成すれば良いため、ハッシュテーブルのサイズは制御しやすくなりますし、意図的に小さくすることもできます（逆にハッシュ関数の作りに合わせて配列のサイズを決めても良いです）。

例えば、後述で紹介するオープンアドレス法の場合、ハッシュテーブルのサイズは 格納するデータの個数 で十分です（ただしパフォーマンスを考慮するともっと大きい方が良い）。

どんなデータも探索可能

また、ダイレクトアクセス法では、配列に格納するデータそのものを配列の添字とするため、扱えるデータは 0 を含む正の整数のみでした。

その一方でハッシュ法の場合、配列の添字とするのはハッシュ値であり、ハッシュ値さえ 0 を含む正の整数であれば良いだけです。

ですので、さまざまな形式のデータに対応するようにハッシュ関数を用意してやれば、どんなデータであっても配列に格納可能ですし、探索可能となります。

ハッシュ法のサンプル実装

ここまで解説してきたハッシュ法を C言語 で実装したサンプルを紹介していきます。

整数をハッシュ法で探索するサンプル実装

下記は整数のデータをハッシュ法により探索する例となります。

衝突考慮なしハッシュ法（整数）

#include <stdio.h>

/* ハッシュテーブルのサイズ */
#define NUM_BUCKET 10

/* バケットの状態を表す定数 */
#define FULL 0
#define EMPTY 1

/* バケットの中身を表現する構造体 */
typedef struct _BUCKET {
    int data; /* バケットに格納されたデータ */
    int state; /* バケットの状態 */
} BUCKET;

/* ハッシュテーブル */
static BUCKET hash_table[NUM_BUCKET];

/******************************
 * ハッシュ値を算出する関数
 * data：ハッシュ値の元になるデータ
 * 返却値：算出したハッシュ値
 ******************************/ 
unsigned int hash(int data) {
    unsigned int u_data = data;

    return u_data % NUM_BUCKET;
}

/******************************
 * ハッシュテーブルを初期化する関数
 ******************************/ 
void initialize(void) {
    int i;

    for (i = 0; i < NUM_BUCKET; i++) {
        hash_table[i].data = 0;
        hash_table[i].state = EMPTY;
    }
}

/******************************
 * ハッシュテーブルの終了処理を行う関数
 ******************************/ 
void finalize(void) {
    int i;

    for (i = 0; i < NUM_BUCKET; i++) {
        hash_table[i].data = 0;
        hash_table[i].state = EMPTY;
    }
}

/******************************
 * ハッシュテーブルにデータを追加する関数
 * data：追加したいデータ
 * 返却値：追加した位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
BUCKET* add(int data) {
    unsigned int i;

    /* ハッシュ値の算出 */
    i = hash(data);

    if (i >= NUM_BUCKET) {
        return NULL;
    }

    /* ハッシュ値の位置のバケットにデータ格納 */
    if (hash_table[i].state != FULL) {
        hash_table[i].data = data;
        hash_table[i].state = FULL;

        return &hash_table[i];
    }

    return NULL;
}

/******************************
 * ハッシュテーブルからデータを探索する関数
 * data：探索したいデータ
 * 返却値：見つかった位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
BUCKET* search(int data) {
    
    unsigned int i;
    
    /* ハッシュ値の算出 */
    i = hash(data);

    if (i >= NUM_BUCKET) {
        return NULL;
    }

    /* ハッシュ値の位置のバケットと比較 */
    if (hash_table[i].state != EMPTY) {
        if (hash_table[i].data == data) {

            /* dataが見つかった */
            return &hash_table[i];
        }
    }

    return NULL;
}

/******************************
 * ハッシュテーブルからデータを削除する関数
 * data：削除したいデータ
 * 返却値：削除した位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
BUCKET* delete(int data) {
    
    unsigned int i;
    
    /* ハッシュ値の算出 */
    i = hash(data);

    if (i >= NUM_BUCKET) {
        return NULL;
    }

    /* ハッシュ値の位置のバケットの中身を削除 */
    if (hash_table[i].state != EMPTY) {
        if (hash_table[i].data == data) {

            /* バケットの状態を空に設定 */
            hash_table[i].state = EMPTY;

            return &hash_table[i];
        }
    }

    return NULL;
}

int main(void) {
    unsigned int datas[10] = {
        101, 520, 245, 323, 999,
        678, 924, 2, 96, 777
    };
    int i;

    initialize();

    /* データの格納 */
    for (i = 0; i < 10; i++) {
        if (add(datas[i])) {
            printf("%d is ADDED\n", datas[i]);
        }
    }

    /* データの探索 */
    for (i = 0; i < 10; i++) {
        if (search(datas[i])) {
            printf("%d is FOUND\n", datas[i]);
        }
    }

    /* データの探索が失敗することを確認 */
    if (search(987)) {
        printf("%d is FOUND\n", 987);
    }
    
    if (search(654)) {
        printf("%d is FOUND\n", 654);
    }

    /* データの削除が失敗することを確認 */
    if (delete(654)) {
        printf("%d is DELETED\n", 654);
    }

    /* データの削除 */
    for (i = 0; i < 10; i++) {
        if (delete(datas[i])) {
            printf("%d is DELETED\n", datas[i]);
        }
    }

    finalize();

    return 0;
}

実際に比較してみると分かりやすいと思うのですが、処理としてはダイレクトアクセス法のサンプル実装で紹介したものとほとんど変わりません。

ハッシュ法っぽく、配列名を hash_table、配列の各要素の構造体の定義名を BUCKET に変更したりもしていますが、処理内容として違うのは、データの格納時・データの探索時・データの削除時に参照する配列の添字がハッシュ関数（hash）から算出されるハッシュ値としている部分のみです。

例えば、データを格納する add 関数においては、ダイレクトアクセス法の場合、下記のように引数で渡されるデータそのものを配列の添字にしていました。

ダイレクトアクセス法のadd

ELEM* add(unsigned int data) {

    if (data >= NUM_ELEM) {
        return NULL;
    }

    /* dataを添字とする位置の要素にデータ格納 */
    if (data_table[data].state == EMPTY) {
        data_table[data].data = data;
        data_table[data].state = FULL;

        return &data_table[data];
    }

    return NULL;
}

それに対してハッシュ法の場合は、下記のように引数で渡されるデータからハッシュ値 i を hash 関数から算出し、そのハッシュ値 i を配列の添字にしています。

ハッシュ法のadd

BUCKET* add(int data) {
    unsigned int i;

    /* ハッシュ値の算出 */
    i = hash(data);

    if (i >= NUM_BUCKET) {
        return NULL;
    }

    /* ハッシュ値の位置のバケットにデータ格納 */
    if (hash_table[i].state != FULL) {
        hash_table[i].data = data;
        hash_table[i].state = FULL;

        return &hash_table[i];
    }

    return NULL;
}

その他の search 関数や delete 関数に関しても同様の変更のみになります。ですので、処理内容としては、ダイレクトアクセス法との違いは配列の添字の扱いの違いだけという点が理解していただけると思います。

ただ、ハッシュ法では、ハッシュ関数で返却する値を 0 〜 BUCKET_SIZE - 1 としていますので、配列のサイズは BUCKET_SIZE のみで動作することが可能です。

より具体的には、ダイレクトアクセス法ではデータの格納先となる配列のサイズは 1000 必要でしたが、ハッシュ法ではデータの格納先となる配列のサイズは 10 のみで済んでいます。

文字列をハッシュ法で探索するサンプル実装

また、ダイレクトアクセス法では扱うデータは正の整数のみでしたが、ハッシュ法では文字列等も扱うことが可能です。

例えば文字列を探索する例は下記となります。

衝突考慮なしハッシュ法（文字列）

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

/* ハッシュテーブルのサイズ */
#define NUM_BUCKET 10

/* 扱う文字列の最大文字数 */
#define MAX_STR_LEN 255

/* バケットの状態を表す定数 */
#define FULL 0
#define EMPTY 1

/* バケットの中身を表現する構造体 */
typedef struct _BUCKET {
    char data[MAX_STR_LEN + 1]; /* バケットに格納されたデータ */
    int state; /* バケットの状態 */
} BUCKET;

/* ハッシュテーブル */
static BUCKET hash_table[NUM_BUCKET];

/******************************
 * ハッシュ値を算出する関数
 * data：ハッシュ値の元になるデータ
 * 返却値：算出したハッシュ値
 ******************************/ 
unsigned int hash(char *data) {
    unsigned int i;
    unsigned int sum;

    sum = 0;
    for (i = 0; i < strlen(data); i++) {
        sum += data[i];
    }

    return sum % NUM_BUCKET;    
}

/******************************
 * ハッシュテーブルを初期化する関数
 ******************************/ 
void initialize(void) {
    int i;

    for (i = 0; i < NUM_BUCKET; i++) {
        hash_table[i].data[0] = '\0';
        hash_table[i].state = EMPTY;
    }
}

/******************************
 * ハッシュテーブルの終了処理を行う関数
 ******************************/ 
void finalize(void) {
    int i;

    for (i = 0; i < NUM_BUCKET; i++) {
        hash_table[i].data[0] = '\0';
        hash_table[i].state = EMPTY;
    }
}

/******************************
 * ハッシュテーブルにデータを追加する関数
 * data：追加したいデータ
 * 返却値：追加した位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
BUCKET* add(char *data) {
    unsigned int i;

    /* ハッシュ値の算出 */
    i = hash(data);

    if (i >= NUM_BUCKET) {
        return NULL;
    }

    /* ハッシュ値の位置のバケットにデータ格納 */
    if (hash_table[i].state != FULL) {
        strcpy(hash_table[i].data, data);
        hash_table[i].state = FULL;
    }

    return &hash_table[i];
}

/******************************
 * ハッシュテーブルからデータを探索する関数
 * data：探索したいデータ
 * 返却値：見つかった位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
BUCKET* search(char *data) {
    
    unsigned int i;
    
    /* ハッシュ値の算出 */
    i = hash(data);

    if (i >= NUM_BUCKET) {
        return NULL;
    }

    /* ハッシュ値の位置のバケットと比較 */
    if (hash_table[i].state != EMPTY) {
        if (strcmp(hash_table[i].data, data) == 0) {

            /* dataが見つかった */
            return &hash_table[i];
        }
    }

    return NULL;
}

/******************************
 * ハッシュテーブルからデータを削除する関数
 * data：削除したいデータ
 * 返却値：削除した位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
BUCKET* delete(char *data) {
    
    unsigned int i;
    
    /* ハッシュ値の算出 */
    i = hash(data);

    if (i >= NUM_BUCKET) {
        return NULL;
    }

    /* ハッシュ値の位置のバケットの中身を削除 */
    if (hash_table[i].state != EMPTY) {
        if (strcmp(hash_table[i].data, data) == 0) {

            /* バケットの状態を空に設定 */
            hash_table[i].state = EMPTY;

            return &hash_table[i];
        }
    }

    return NULL;
}

int main(void) {
    char datas[10][MAX_STR_LEN ] = {
        "abc", "def", "ghi", "jkl", "mno",
        "pqr", "stu", "vwx", "yz ", "B"
    };
    int i;

    initialize();

    /* データの格納 */
    for (i = 0; i < 10; i++) {
        if (add(datas[i])) {
            printf("%s is ADDED\n", datas[i]);
        }
    }

    /* データの探索 */
    for (i = 0; i < 10; i++) {
        if (search(datas[i])) {
            printf("%s is FOUND\n", datas[i]);
        }
    }

    /* データの探索が失敗することを確認 */
    if (search("bcf")) {
        printf("%s is FOUND\n", "bcf");
    }
    
    if (search("xz")) {
        printf("%s is FOUND\n", "xz");
    }

    /* データの削除が失敗することを確認 */
    if (delete("aiu")) {
        printf("%s is DELETED\n", "aiu");
    }

    /* データの削除 */
    for (i = 0; i < 10; i++) {
        if (delete(datas[i])) {
            printf("%s is DELETED\n", datas[i]);
        }
    }

    finalize();

    return 0;
}

整数を探索するときの違いは主に下記の３つのみです。

ハッシュテーブルへの格納の仕方
データの比較の仕方
ハッシュ関数

上記２つに関しては、要は扱うデータが文字列なので、文字列を他の場所にコピーするために strcpy を使うように変更し、文字列同士を比較するために strcmp を使うように変更しているだけです。

ハッシュ関数に関しては、関数への入力データが文字列なので、その文字列を正の整数に変換するための処理を行う必要がありますので、そのための変更を行なっています。

要は、ハッシュ法の探索プログラムでは、扱うデータに応じて上記の３つの処理に関しては変更が必要ということになります（上記２つに関してはどの探索アルゴリズムでも同様だと思います）。

逆に上記以外の処理に関しては、他の形式のデータを扱う場合でも整数を扱う場合と同じ処理でハッシュ法を実現することが可能です。

衝突（ハッシュ法の問題点）

大体ハッシュ法については理解していただけたでしょうか？

もうお気づきの方も多いかと思いますが、ここまであえて説明を避けてきましたが、このハッシュ法には問題点があります。

その問題点が “衝突” です

衝突とは、異なるデータのハッシュ値が重複してしまうことを言います。

ここまで紹介してきたソースコードの例では、ハッシュ値が異なるようにハッシュテーブルに格納するデータを選んでいました。

なので、ここまで紹介してきたソースコードではデータの探索はうまく動作するのですが、例えば先ほど整数をハッシュ法で探索するサンプル実装で紹介したソースコードの main 関数に下記を加えた場合、search(394) でのデータの探索に失敗するようになってしまいます。

探索に失敗する例

/* データの格納 */
for (i = 0; i < 10; i++) {
    if (add(datas[i])) {
        printf("%d is ADDED\n", datas[i]);
    }
}

/* ここから下を追加 */
add(394);
if (search(394)) {
    /* searchに失敗するので下記は表示されない */
    printf("%d is FOUND\n", 394);
}
/* ここから上を追加 */

失敗する理由の根本的原因は、データ 394 のハッシュ値が、事前にハッシュテーブルに格納されていた 924 のハッシュ値と重複することです。つまり衝突が発生しています。

この際、データ 924 とデータ 394 は同じ位置に格納することになるので、先に格納したデータが後から格納されたデータで上書きされる or 後から格納しようとするデータが格納できないことになります（いずれにせよ一方のデータはハッシュテーブルに格納できない）。

ここで、格納できなかった方のデータを探索したとしても、当然そのデータを見つけることはできません。

整数をハッシュ法で探索するサンプル実装で紹介したソースコードは、データ格納時に先に格納されたデータをハッシュテーブル内に残すようにしているので、後から格納しようとした 394 は、ハッシュテーブルに格納されず、データ 394 の探索には当然失敗してしまいます。

このように、衝突が発生した場合、ここまで解説してきた単純なハッシュ法ではデータの探索がうまく動作しません。

配列に格納するデータに規則性がある場合などは、ハッシュ関数の作り方を工夫すれば衝突は防げるかもしれませんが、ランダムなデータである場合は、おそらく完全に衝突を防ぐハッシュ関数を作成するのは難しいと思います（もしかしたらできるのかもしれませんが、少なくとも私は知りません）。

なので、衝突を完全に防ぐのは難しいものとして、衝突した場合でもデータの探索が正常に動作するように対応することが必要になります。

MEMO

衝突時の対応を導入したとしても、衝突はできるだけ発生しないようにハッシュ関数を作成したほうが良いです

これは、衝突が発生すればするほど、データの探索時間が長くなってしまうからです（理由は後述で解説します）

衝突を解決する手法

ここまで解説してきた衝突を解決する手法、つまり、衝突が発生しても正常に探索を行うための手法として有名なのが下記の２つになります。

オープンアドレス法
チェイン法

このページにおいては、１つ目のオープンアドレス法について解説していきたいと思います。

チェイン法については別ページの下記において解説していますので、チェイン法について知りたい方は下記ページを参照していただければと思います。

【C言語】チェイン法について解説（ハッシュ探索時の衝突を解決する方法）

オープンアドレス法とは

オープンアドレス法は、衝突が発生した場合に新たなハッシュ値を算出し、その新たなハッシュ値の位置のバケットにデータを格納することで、衝突発生時にもデータの探索を正常に行えるようにする方法になります。

リハッシュ関数

新たなハッシュ値は、衝突時のハッシュ値とは異なるものである必要があります（同じハッシュ値だとまた衝突してしまいますよね…）。

この新たなハッシュ値を求める関数をリハッシュ関数と呼ばせていただきます。

一番分かりやすいリハッシュ関数は下記になると思います。第１引数 old_hash で受け取る値が、前回求めたハッシュ値となります。

リハッシュ関数の例

unsigned int rehash(unsigned int old_hash) {

    return (old_hash + 1) % N;    
}

前回求めたハッシュ値 +1 の値が新たなハッシュ値となるので、要は次のバケットをデータの新たな格納位置とするリハッシュ関数になります（+1 した結果がハッシュテーブルのサイズとなる場合は、ハッシュテーブルの先頭が格納先のバケットとなる）。

ただ、別にリハッシュ関数は上記のものに限られるわけではありません。大事なのは、新たなハッシュ値を求め、そのハッシュ値の位置のバケットにデータを格納することです。

ちなみに上記の関数で新たなハッシュ値を求める方法は “線形走査法” と呼ぶそうです。他にも “ダブルハッシュ法” など、新たなハッシュ値を求める方法においてもたくさんのものが存在します。

データの格納

で、当然ですが、新たなハッシュ値の位置のバケットが空いているとは限りません。他のデータが既に格納されている可能性があります。

この場合は、再度リハッシュ関数を実行して新たなハッシュ値を生成し、再度そのハッシュ値の位置のバケットにデータを格納することを試みます。

当然この位置のバケットも空でない可能性がありますので、空のバケットが見つかるまで、リハッシュ関数を繰り返し実行することになります。

ですので、当然ハッシュテーブルのサイズを超える数のデータは一度に格納することができません。ハッシュテーブルが満杯の状態で上記の処理を行なってしまうと、無限にリハッシュ関数が実行されることになるので注意してください。

ここまでが、オープンアドレス法を用いたときのデータの格納の流れとなります。

データの探索

では、データの探索はどのようにして実現すれば良いでしょうか？

これもデータ格納時とほぼ同様です。

まず探索したいデータからハッシュ関数によりハッシュ値を求め、その位置のバケットが探索したいデータであるかどうかを判断します。もしそのバケットに探索したいデータが格納されているのであれば、その時点でデータが見つかったことになるので探索完了です。

この場合、単なるハッシュ法と同様に、探索に必要になる計算量のオーダーは O(1) のみとなります。

ここからが単なるハッシュ法とは異なるところで、もし、ハッシュ値の位置のバケットに探索したいデータ以外のデータが格納されていたのであれば、リハッシュ関数により新たなハッシュ値を求める必要があります。

そして、先ほど同様に、そのハッシュ値の位置のバケットが探索したいデータであるかどうかを判断します。

もしそのバケットに探索したいデータが格納されているのであれば、その時点でデータが見つかったことになるので探索完了ですし、異なったデータが格納されていた場合は、再度リハッシュ関数を求めて新たなハッシュ値を求め、またそのハッシュ値の位置のバケットのデータの確認を行います。

要はこれを、空のバケットに到達するまで、もしくはハッシュテーブル全体の探索が完了するまで繰り返します。

探索したいデータが見つかるまでに、空のバケットに到達した場合 or ハッシュテーブル全体のバケットのデータと比較が完了した場合は、探索したいデータがハッシュテーブル内に存在しなかったことになります。

要は、オープンアドレス法においては、ハッシュ値の位置にバケットが存在しなかった場合、次にそのデータが格納されている可能性のあるバケットの位置は、リハッシュ関数により取得することができます。

これは、格納する際にも同様に、ハッシュ値の位置にバケットが空いていなかった場合、次にそのデータを格納する位置をリハッシュ関数から取得するようにしているからです。

ですので、リハッシュ関数でハッシュ値を求め、そのハッシュ値の位置のバケットを調べることを繰り返せば、いずれは探索したいデータに到達することができます（ハッシュテーブルの中に探索したいデータが存在する場合）。

空のバケットの取り扱いに注意

で、ここで重要なのが、ハッシュテーブルからデータの削除を行うような場合、“空のバケット” には下記の２つの意味のものが存在するという点です。

最初からずっと空のバケット
データが削除されて空になったバケット

前述で、データの探索は “空のバケット” に到達するまで繰り返すと言いましたが、この “空のバケット” は、上記の “最初からずっと空のバケット” の方を指します。

つまり、データの探索は、求めたハッシュ値の位置のバケットが “データが削除されて空になったバケット” である場合でも、探索を続行する必要があります。

なぜなら、それ以降で求めたハッシュ値の位置のバケットに、探索したいデータが存在する可能性があるからです。

例えば下の図のように、92 と 252 と 12 の３つのデータで衝突が発生し、衝突時はオープンアドレス法（リハッシュ関数は線形走査法）に基づいてデータを格納した場合について考えてみましょう。

この状態であれば、データ 12 は、ハッシュ値を３回求めることで探索することが可能です（ハッシュ関数を１回とリハッシュ関数を２回実行）。

今度は、データ 252 を削除した後に、データ 12 を探索することを考えてみましょう。

この場合、２回目に求めたハッシュ値の位置のバケットは空です。

ただ、ここでバケットが空といってデータの探索をやめてしまうと、データ 12 はハッシュテーブル内に存在するにも関わらず、探索に失敗することになってしまいます。つまり、探索の動作がおかしいです。

こんな感じで、途中でデータを削除した場合、それ以降に求めたハッシュ値の位置にデータが存在する可能性はあります。ですので、それ以降もデータの探索を継続する必要があります。

逆に、バケットに元々データが格納されていなかったのであれば、それ以降に探しているデータは存在しないため、その時点でデータの探索を終了する必要があります。

上記のように、探索の継続と終了を切り替えるような制御を行うためには、空のバケットが、”最初からずっと空のバケット” or “データが削除されて空になったバケット” のどちらであるかが分かるようにバケットを管理する必要があります。

で、探索を行う際には、空のバケットがどちらの意味のバケットであるかを確認し、後者の場合は探索を継続、前者の場合は探索を終了するように制御を行う必要があります。

オープンアドレス法のサンプル実装

ここまで解説してきたオープンアドレス法を適用したデータ探索プログラムのサンプルが下記となります。

オープンアドレス法（整数）

#include <stdio.h>

/* ハッシュテーブルのサイズ */
#define NUM_BUCKET 10

/* バケットの状態を表す定数 */
#define FULL 0
#define EMPTY 1
#define DELETED 2

/* バケットの中身を表現する構造体 */
typedef struct _BUCKET {
    int data; /* バケットに格納されたデータ */
    int state; /* バケットの状態 */
} BUCKET;

/* ハッシュテーブル */
static BUCKET hash_table[NUM_BUCKET];

/* テーブルの空き数 */
static unsigned int empty_num = 0;

/******************************
 * ハッシュ値を算出する関数
 * data：ハッシュ値の元になるデータ
 * 返却値：算出したハッシュ値
 ******************************/ 
unsigned int hash(int data) {
    unsigned int u_data = data;

    return u_data % NUM_BUCKET;    
}

/******************************
 * 再ハッシュ値を算出する関数
 * old_hash：前回のハッシュ値
 * 返却値：算出したハッシュ値
 ******************************/ 
unsigned int rehash(unsigned int old_hash) {

    return (old_hash + 1) % NUM_BUCKET;    
}

/******************************
 * ハッシュテーブルを初期化する関数
 ******************************/ 
void initialize(void) {
    int i;

    empty_num = 0;

    for (i = 0; i < NUM_BUCKET; i++) {
        hash_table[i].data = 0;
        hash_table[i].state = EMPTY;
        empty_num++;
    }
}

/******************************
 * ハッシュテーブルの終了処理を行う関数
 ******************************/ 
void finalize(void) {
    int i;

    empty_num = 0;

    for (i = 0; i < NUM_BUCKET; i++) {
        hash_table[i].data = 0;
        hash_table[i].state = EMPTY;
        empty_num++;
    }
}

/******************************
 * ハッシュテーブルにデータを追加する関数
 * data：追加したいデータ
 * 返却値：追加した位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
BUCKET* add(int data) {
    unsigned int i;
    
    if (empty_num == 0) {
        return NULL;
    }

    /* ハッシュ値の算出 */
    i = hash(data);

    if (i >= NUM_BUCKET) {
        return NULL;
    }


    /* 空いているバケットを探す */
    while (hash_table[i].state == FULL) {
        /* 新たなハッシュ値を算出 */
        i = rehash(i);
    }

    /* ハッシュ値の位置のバケットにデータ格納 */
    hash_table[i].data = data;
    hash_table[i].state = FULL;
    empty_num--;

    return &hash_table[i];
}

/******************************
 * ハッシュテーブルからデータを探索する関数
 * data：探索したいデータ
 * 返却値：見つかった位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
BUCKET* search(int data) {
    
    unsigned int i;
    unsigned int count;

    /* ハッシュ値の算出 */
    i = hash(data);

    if (i >= NUM_BUCKET) {
        return NULL;
    }

    /* ハッシュ値の位置のバケットと比較 */
    count = 0;
    while (hash_table[i].state != EMPTY && count < NUM_BUCKET) {
        if (hash_table[i].data == data) {

            /* dataが見つかった */
            return &hash_table[i];
        }

        /* 新たなハッシュ値を算出 */
        i = rehash(i);

        /* 探索回数をカウントアップ */
        count++;
    }

    return NULL;
}

/******************************
 * ハッシュテーブルからデータを削除する関数
 * data：削除したいデータ
 * 返却値：削除した位置のアドレス（成功時）
 *      ：NULL（失敗時）
 ******************************/ 
BUCKET* delete(int data) {
    
    unsigned int i;
    unsigned int count;

    /* ハッシュ値の算出 */
    i = hash(data);

    if (i >= NUM_BUCKET) {
        return NULL;
    }

    /* ハッシュ値の位置のバケットの中身を削除 */
    count = 0;
    while (hash_table[i].state != EMPTY && count < NUM_BUCKET) {
        if (hash_table[i].data == data) {

            /* バケットの状態を削除済みに設定 */
            hash_table[i].state = DELETED;

            empty_num++;
            return &hash_table[i];
        }

        /* 新たなハッシュ値を算出 */
        i = rehash(i);

        /* 探索回数をカウントアップ */
        count++;
    }

    return NULL;
}

int main(void) {
    unsigned int datas[10] = {
        100, 500, 245, 325, 999,
        0, 199, 1, 98, 777
    };
    int i;

    initialize();

    /* データの格納 */
    for (i = 0; i < 10; i++) {
        if (add(datas[i])) {
            printf("%d is ADDED\n", datas[i]);
        }
    }

    /* データの探索 */
    for (i = 0; i < 10; i++) {
        if (search(datas[i])) {
            printf("%d is FOUND\n", datas[i]);
        }
    }

    /* データの探索が失敗することを確認 */
    if (search(987)) {
        printf("%d is FOUND\n", 987);
    }
    
    if (search(654)) {
        printf("%d is FOUND\n", 654);
    }

    /* データの削除が失敗することを確認 */
    if (delete(654)) {
        printf("%d is DELETED\n", 654);
    }

    /* データ削除後の探索に成功することを確認 */
    delete(500);
    if (search(0)) {
        printf("%d is FOUND\n", 0);
    }
    add(500);

    /* データの削除 */
    for (i = 0; i < 10; i++) {
        if (delete(datas[i])) {
            printf("%d is DELETED\n", datas[i]);
        }
    }

    finalize();

    return 0;
}

上記ソースコードにおけるポイントを解説しておきます。

最大のポイントは、衝突したデータの格納や探索、削除を行う処理です。

例えばデータを探索する search 関数では、下記のように、ハッシュ値の位置のバケットに異なるデータが格納されている際に rehash 関数で新たなハッシュ値を求め、そのハッシュ値の位置のバケットを調べる処理を繰り返すようにしています。

探索の繰り返し

while (hash_table[i].state != EMPTY && count < NUM_BUCKET) {
    if (hash_table[i].data == data) {

        /* dataが見つかった */
        return &hash_table[i];
    }

    /* 新たなハッシュ値を算出 */
    i = rehash(i);

    /* 探索回数をカウントアップ */
    count++;
}

同様の処理を、データを格納する add 関数とデータを削除する delete 関数でも行なっています。

また、オープンアドレス法では、”空のバケット” を下記の２種類で区別して管理する必要があります。

最初からずっと空のバケット
データが削除されて空になったバケット

そのため、ソースコード先頭付近で、下記の EMPTY と DELETED を定義し、空のバケットに対応する BUCKET 構造体の state メンバにこれらのどちらかを格納することで、空きのバケットを区別するようにしています。

EMPTY：最初からずっと空のバケットであることを示す定義値
DELETED：データが削除されて空になったバケットであることを示す定義値

より具体的には、ハッシュテーブルの初期化を行う initialize 関数の中で、全ての BUCKET 構造体の state メンバに EMPTY を格納しています。

また、データの削除を行う delete 関数の中で、データを削除するバケット（BUCKET 構造体）の state メンバに DELETED を格納するようにしています（ちなみにデータを追加する際には FULL を格納するようにしています）。

さらに、データの探索を行う searach 関数の中では、探索先のバケット（BUCKET 構造体）の state メンバが EMTPY の場合に探索を終了し、それ以外のバケットの場合は探索を継続するようにしています。

MEMO

search 関数では、ハッシュテーブルのサイズ（NUM_BUCKET）回の探索を行なった際にも探索を終了するようにしています

あとは、オープンアドレス法においては、ハッシュテーブルが満杯になるとデータを格納することができないようになるため、ハッシュテーブルの空き数を、empty_num 変数で管理しているところもポイントの１つになります。

オープンアドレス法の探索効率

最後に、オープンアドレス法の探索効率について解説しておきます。

もし、探索したいデータに対して衝突が発生していない場合、この時は単なるハッシュ法と同じ手順での探索となりますので計算量のオーダーは O(1) です。

ただし、衝突が発生していた場合、そのデータを探索する際には、要は算出されるハッシュ値に沿ってデータを１つ１つ調べていくだけになるので、線形探索と同様の動作になります（ハッシュ値を求めるコストがある分、ハッシュ法の方が遅くなるはずです）。

この時にオープンアドレス法で厄介なのが、削除されたデータも含めて探索を行う必要があるところです。

実質的にはハッシュテーブル内の１つのバケットにしかデータがないような場合でも、他のバケットが全て “データが削除されて空になったバケット” であるような場合、最悪ハッシュテーブルのサイズ分の線形探索を行う必要があります。

これに対して、下記ページで紹介しているチェイン法では、削除されたデータはもう探索する必要がありません。ですので、特にデータの削除を行うようなユースケースが存在する場合、オープンアドレス法よりもチェイン法の方がパフォーマンス的には優れていると言えます。

【C言語】チェイン法について解説（ハッシュ探索時の衝突を解決する方法）

また、オープンアドレス法では、ハッシュテーブル内に存在しないデータを探索する際に、いかにして早く “最初からずっと空のバケット” に到達するかが探索効率に直結します。

ですので、データを格納する分には、ハッシュテーブルのサイズは “格納するデータの個数” で十分なのですが、それよりも大きなサイズにして “最初からずっと空のバケット” を増やした方が、探索効率は向上します（さらに、”最初からずっと空のバケット” がハッシュテーブル内に散らばるようにハッシュ関数やリハッシュ関数を作成できるとより良い）。

ただし、一度データが格納されたバケットは、もう “最初からずっと空のバケット” には戻ることがありません。

なので、”データを削除して空になったバケット” が増えてきた際には、ハッシュテーブルを作り直すような対応をした方が、探索効率は低下しにくくなるかなぁと思います。

いずれにしても、ハッシュ法では衝突が発生すればするほど、データ探索時の効率は低下します。ですので、いかにしてハッシュ値が被らないようにハッシュ関数を作成するかが重要になります。

その方法の１つとしては、ハッシュ値が取りうる値の範囲を大きくすることが挙げられます。これにより、ハッシュ値が被る確率を下げられるので、データ探索時の効率は向上すると考えられます。

ただ、その分配列のサイズも大きくする必要があるので、使用メモリ量が増えるというデメリットもあるので注意してください。

逆にいうと、使用するメモリ量を増やせば（ハッシュテーブルのサイズを大きくすれば）、ハッシュ法での探索効率は向上しますので、メモリが潤沢にあるような環境上での探索にはハッシュ法は向いていると思います（線形探索や二分探索では、使用するメモリを増やしたからといって探索効率は向上しない）。