More than 5 years have passed since last update.

C言語　ハッシュテーブル

Last updated at 2020-03-27Posted at 2020-03-25

ハッシュデーブルというデータ構造

ハッシュテーブルはデータを連想的に格納するデータ構造。
データは配列形式で格納され、各データ値には独自の一意のインデックス値が振られます。
目的のデータのインデックスがわかっているとデータへのアクセスが非常に早くなります。

データサイズに関係なく、挿入及び、検索操作が非常に拘束なデータ構造になります。

ハッシュテーブルは、配列を記憶媒体として使用し、ハッシュテクニックを使用して、要素を挿入する場所または、要素の場所のインデックスを生成します。

ハッシング

ハッシングは、キー値の範囲を配列のインデックスの範囲に変換する手法のことです。

モジュロ演算子(余りを求める演算子、%のこと)を使用して、キー値の範囲を取得すると下記のようになります。

Sr.No.	Key	Hash	Array Index
1	1	1 % 20 = 1	1
2	2	2 % 20 = 2	2
3	42	42 % 20 = 2	2
4	4	4 % 20 = 4	4
5	12	12 % 20 = 12	12
6	14	14 % 20 = 14	14
7	17	17 % 20 = 17	17
8	13	13 % 20 = 13	13
9	37	37 % 20 = 17	17

ハッシュの衝突の回避方法

オープンハッシュ法
- チェイン法
  - 同じ位置に入るべきだったRecordをリスト状にぶら下げていく方法
クローズドハッシュ法(オープンアドレス法)
- 線形探索法
  - 本来入るべきであった場所の隣で妥協してく方法
- 二重ハッシュ法
  - ハッシュ関数を２つ使って衝突を回避していく方法

クローズドハッシュ法はオープンアドレス法とも言われます。
オブジェクトがハッシュテーブルに格納されるアドレスが、そのハッシュコードによって完全に確定されていないことによります。オープンって言葉のニュアンスは、誰でも触れられる、変えられるみたいな意味に捉えるとわかりやすいです。変数はオープン、定数はクローズドみたいなイメージ。

チェイン法(Linked list)

衝突の起こったハッシュを持つ要素に対して、Linked listでつなげることで、同じハッシュに対して複数のキーをもたせることができます。
Linked listに対しては、線形探索を行います。

※画像は参考サイトから引用

線形探索法(Linear Probing)

本来入るべきであった場所の隣で妥協していく方法

重複するハッシュが生成された場合(ハッシュの衝突)、インデックスを次の空いている配列のメモリに対して振ります。
線形探索法を使用した場合の検索アルゴリズムは線形探索になります。

線形探索法の問題は，最大のエントリ数がハッシュテーブルのサイズで制限されるため，ハッシュテーブルが埋まった際にハッシュテーブルを拡張するには、ハッシュテーブル自体を再構成する必要があることです。

Sr.No.	Key	Hash	Array Index	After Linear Probing, Array Index
1	1	1 % 20 = 1	1	1
2	2	2 % 20 = 2	2	2
3	42	42 % 20 = 2	2	3
4	4	4 % 20 = 4	4	4
5	12	12 % 20 = 12	12	12
6	14	14 % 20 = 14	14	14
7	17	17 % 20 = 17	17	17
8	13	13 % 20 = 13	13	13
9	37	37 % 20 = 17	17	18

基本的な操作

挿入
- ハッシュ値の衝突が発生した場合は、再ハッシュを繰り返して、「空状態」バケットを調べていき、空いているバケットを発見したらデータを格納します。
探索
- キーからハッシュ値を求め、バケットのデータがキーに対応する値をチェック、正しければ探索完了、異なれば、次の値を探すか(線形探索法)、再ハッシュを繰り返すか(二重探索法)し、たどり着くまで繰り返す。
消去
- バケットを空にしてしまうと、以降の探索ができなくなってしまう。(これは、線形探索法でも、二重ハッシュ法でも、衝突が置きたデータは同じハッシングによって連続して格納されているため、NULLが入ると、そこで探索が終わってしまうから)。バケットは空にせず、ダミーの「消去済み」というオブジェクトを入れる。探索においては、ダミーをスキップして処理を行わせる必要がある。
再挿入
- 「消去済み」バケットは、「空状態」バケットと同じように扱う。

実装

コードは参考サイトから引用。日本語コメントを加筆。

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

# define SIZE 20



/* DataItemの定義 */
struct DataItem
{
    int data;
    int key;
};

struct DataItem *hashArray[SIZE];
struct DataItem *dummyItem;
struct DataItem *item;

/* ハッシュ関数の定義 */
int hashCode(int key)
{
    return key % SIZE;
}

/* 検索のための関数 */
/* liner Probingを使っているのでそれに合わせた検索を実装です。 */
struct DataItem *search(int key)
{
    //get the hash
    int hashIndex = hashCode(key);

    //move in array until an empty
    while (hashArray[hashIndex] != NULL)
    {

        if (hashArray[hashIndex]->key == key)
            return hashArray[hashIndex];

        //go to next cell
        ++hashIndex;

        //wrap around the table
        hashIndex %= SIZE;
    }

    return NULL;
}

/* 挿入のための関数 */
void insert(int key, int data)
{

    struct DataItem *item = (struct DataItem *)malloc(sizeof(struct DataItem));
    item->data = data;
    item->key = key;

    //get the hash
    int hashIndex = hashCode(key);

    //move in array until an empty or deleted cell
    while (hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1)
    {
        //go to next cell
        ++hashIndex;

        //wrap around the table
        hashIndex %= SIZE;
    }
    // ポインタに対してオブジェクトを代入するということをやっています。
    hashArray[hashIndex] = item;
}

struct DataItem *delete (struct DataItem *item)
{
    int key = item->key;

    //get the hash
    int hashIndex = hashCode(key);

    //move in array until an empty
    while (hashArray[hashIndex] != NULL)
    {

        if (hashArray[hashIndex]->key == key)
        {
            struct DataItem *temp = hashArray[hashIndex];

            //assign a dummy item at deleted position
            hashArray[hashIndex] = dummyItem;
            return temp;
        }

        //go to next cell
        ++hashIndex;

        //wrap around the table
        hashIndex %= SIZE;
    }

    return NULL;
}

void display()
{
    int i = 0;

    for (i = 0; i < SIZE; i++)
    {

        if (hashArray[i] != NULL)
            printf(" (%d,%d)", hashArray[i]->key, hashArray[i]->data);
        else
            printf(" ~~ ");
    }

    printf("\n");
}

int main()
{
    dummyItem = (struct DataItem *)malloc(sizeof(struct DataItem));
    dummyItem->data = -1;
    dummyItem->key = -1;

    insert(1, 20);
    insert(2, 70);
    insert(42, 80);
    insert(4, 25);
    insert(12, 44);
    insert(14, 32);
    insert(17, 11);
    insert(13, 78);
    insert(37, 97);

    display();
    item = search(37);

    if (item != NULL)
    {
        printf("Element found: %d\n", item->data);
    }
    else
    {
        printf("Element not found\n");
    }

    delete (item);
    item = search(37);

    if (item != NULL)
    {
        printf("Element found: %d\n", item->data);
    }
    else
    {
        printf("Element not found\n");
    }
}