ハッシュ探索②（オープンアドレス法）　解答ページ | Programming Place Plus　アルゴリズムとデータ構造編【探索アルゴリズム】　第７章

問題① 🔗

問題①　サンプルプログラムの実装における EMPTY と DELETED のような特殊な値が、実際のデータにもありえるため用意できないとしたら、どうやって実装したら良いでしょうか。

サンプルプログラムでは、EMPTY と DELETED にそれぞれ -1、-2 を割り当てていましたが、これらの値がデータに含まれている場合には問題になります。

こういう場合には、メモリの使用量が増加してしまいますが、別の変数を追加することになります。 hash.c を次のように変更します。

// hash.c

#include "hash.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


enum State {
    EMPTY,        // 空であることを表す値
    USED,         // 使用中
    DELETED,      // データが削除されたことを表す値
};

struct Backet_tag {
    int                value;   // 値
    enum State         state;   // 状態
};

struct Hash_tag {
    struct Backet_tag* table;   // ハッシュ表
    size_t             size;    // table の要素数
};

static size_t hash_func(Hash hash, int key);
static size_t rehash_func(Hash hash, size_t index);
static void* xmalloc(size_t size);


/*
    ハッシュ表を作る
*/
Hash hash_create(size_t size)
{
    struct Hash_tag* hash = xmalloc( sizeof(struct Hash_tag) );
    hash->table = xmalloc( sizeof(struct Backet_tag) * size );
    for( size_t i = 0; i < size; ++i ){
        hash->table[i].state = EMPTY;
    }
    hash->size = size;

    return hash;
}

/*
    ハッシュ表を削除する
*/
void hash_delete(Hash hash)
{
    free( hash->table );
    free( hash );
}

/*
    ハッシュ表にデータを追加する
*/
void hash_add(Hash hash, int data)
{
    struct Hash_tag* p = hash;
    size_t index = hash_func( hash, data );

    for( size_t i = 0; i < p->size; ++i ){
        // 空のバケットが見つかったら、そこへ格納
        if( p->table[index].state == EMPTY || p->table[index].state == DELETED ){
            p->table[index].value = data;
            p->table[index].state = USED;
            return;
        }

        index = rehash_func( hash, index );
    }
    assert(!"hash_add failed.");
}

/*
    ハッシュ表からデータを削除する
*/
void hash_remove(Hash hash, int data)
{
    struct Hash_tag* p = hash;
    size_t index = hash_func( hash, data );

    for( size_t i = 0; i < p->size; ++i ){
        // 空のバケットが見つかったら終わり
        if( p->table[index].state == EMPTY ){
            break;
        }

        // 削除済みでなく、値が一致しているバケットなら削除
        if( p->table[index].state != DELETED ){
            if( p->table[index].value == data ){
                p->table[index].state = DELETED;
                return;
            }
        }

        index = rehash_func( hash, index );
    }
}

/*
    ハッシュ表からデータを探索する
*/
int* hash_search(Hash hash, int data)
{
    struct Hash_tag* p = hash;
    size_t index = hash_func( hash, data );

    for( size_t i = 0; i < p->size; ++i ){
        // 空のバケットが見つかったら終わり
        if( p->table[index].state == EMPTY ){
            break;
        }

        // 削除済みでなく、値が一致しているバケットなら終了
        if( p->table[index].state != DELETED ){
            if( p->table[index].value == data ){
                return &p->table[index].value;
            }
        }

        index = rehash_func( hash, index );
    }

    return NULL;
}




/*
    ハッシュ関数
*/
size_t hash_func(Hash hash, int key)
{
    return key % hash->size;
}

/*
    再ハッシュ関数
*/
size_t rehash_func(Hash hash, size_t index)
{
    return (index + 1) % hash->size;
}

/*
    エラーチェック付きの malloc関数
*/
void* xmalloc(size_t size)
{
    void* p = malloc( size );
    if( p == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( EXIT_FAILURE );
    }
    return p;
}

ハッシュ表の型を struct Backet_tag に変更して、この構造体のメンバに、データの値(value) と状態(state) を置くようにしました。

state は EMPTY で初期化されており、実際にデータが格納されたら USED を代入します。また、データが削除されたら DELETED を代入します。データの有無を調べるときも、state を調べるようにします。

問題② 🔗

問題②　この章の実装では、ハッシュ表の要素数を超える量のデータを登録できません。ハッシュ表全体を、より大きな要素数で作り直すようにすれば、この制約を免れることが可能ですが、この方法で実装してみてください。また、この方法に実用上の問題はあるでしょうか？

hash_add関数を呼び出したとき、ハッシュ表の要素数の８割以上が使用済みであれば、ハッシュ表を拡張するようにしてみます。なお、問題①のコードを元に改造しています。

// hash.c

#include "hash.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>


enum State {
    EMPTY,        // 空であることを表す値
    USED,         // 使用中
    DELETED,      // データが削除されたことを表す値
};

struct Backet_tag {
    int                value;   // 値
    enum State         state;   // 状態
};

struct Hash_tag {
    struct Backet_tag* table;   // ハッシュ表
    size_t             size;    // table の要素数
    size_t             count;   // 登録されたデータの総数
};

static void init(Hash hash, size_t size);
static void add(Hash hash, int data);
static size_t hash_func(Hash hash, int key);
static size_t rehash_func(Hash hash, size_t index);
static void recreate(Hash hash, size_t new_size);
static void* xmalloc(size_t size);


/*
    ハッシュ表を作る
*/
Hash hash_create(int size)
{
    assert( size > 0 );

    struct Hash_tag* hash = xmalloc( sizeof(struct Hash_tag) );
    init( hash, size );

    return hash;
}

/*
    ハッシュ表を削除する
*/
void hash_delete(Hash hash)
{
    free( hash->table );
    free( hash );
}

/*
    ハッシュ表にデータを追加する
*/
void hash_add(Hash hash, int data)
{
    struct Hash_tag* p = hash;

    // ハッシュ表の要素数の８割以上が使用済みならば、ハッシュ表を拡張する
    if( p->count >= p->size * 0.8 ){
        recreate( hash, p->size * 2 + 1 );
    }

    add( hash, data );
}

/*
    ハッシュ表からデータを削除する
*/
void hash_remove(Hash hash, int data)
{
    struct Hash_tag* p = hash;
    size_t index = hash_func( hash, data );

    for( size_t i = 0; i < p->size; ++i ){
        // 空のバケットが見つかったら終わり
        if( p->table[index].state == EMPTY ){
            break;
        }

        // 削除済みでなく、値が一致しているバケットなら削除
        if( p->table[index].state != DELETED ){
            if( p->table[index].value == data ){
                p->table[index].state = DELETED;
                p->count--;
                return;
            }
        }

        index = rehash_func( hash, index );
    }
}

/*
    ハッシュ表からデータを探索する
*/
int* hash_search(Hash hash, int data)
{
    struct Hash_tag* p = hash;
    size_t index = hash_func( hash, data );

    for( size_t i = 0; i < p->size; ++i ){
        // 空のバケットが見つかったら終わり
        if( p->table[index].state == EMPTY ){
            break;
        }

        // 削除済みでなく、値が一致しているバケットなら終了
        if( p->table[index].state != DELETED ){
            if( p->table[index].value == data ){
                printf("%d にありました。\n", index);
                return &p->table[index].value;
            }
        }

        index = rehash_func( hash, index );
    }

    return NULL;
}



/*
    初期化
*/
void init(Hash hash, size_t size)
{
    hash->table = xmalloc( sizeof(struct Backet_tag) * size );
    for( size_t i = 0; i < size; ++i ){
        hash->table[i].state = EMPTY;
    }
    hash->size = size;
    hash->count = 0;
}

/*
    データの登録
*/
void add(Hash hash, int data)
{
    struct Hash_tag* p = hash;
    size_t index = hash_func( hash, data );

    for( size_t i = 0; i < p->size; ++i ){
        // 空のバケットが見つかったら、そこへ格納
        if( p->table[index].state == EMPTY || p->table[index].state == DELETED ){
            p->table[index].value = data;
            p->table[index].state = USED;
            p->count++;
            return;
        }

        index = rehash_func( hash, index );
    }
    assert(!"hash_add failed.");
}

/*
    ハッシュ関数
*/
size_t hash_func(Hash hash, int key)
{
    return key % hash->size;
}

/*
    再ハッシュ関数
*/
size_t rehash_func(Hash hash, size_t index)
{
    return (index + 1) % hash->size;
}

/*
    ハッシュ表を作り変える
*/
void recreate(Hash hash, size_t new_size)
{
    // 現在の登録情報をコピー
    size_t old_size = hash->size;
    struct Backet_tag* work_table = malloc( sizeof(struct Backet_tag) * old_size );
    memcpy( work_table, hash->table, sizeof(struct Backet_tag) * old_size );

    // ハッシュ表を作り直す
    free( hash->table );
    init( hash, new_size );

    // 登録されていたデータをハッシュし直す
    for( size_t i = 0; i < old_size; ++i ){
        if( work_table[i].state == USED ){
            add( hash, work_table[i].value );
        }
    }

    // コピーの方は解放
    free( work_table );
}

/*
    エラーチェック付きの malloc関数
*/
void* xmalloc(size_t size)
{
    void* p = malloc( size );
    if( p == NULL ){
        fputs( "メモリ割り当てに失敗しました。", stderr );
        exit( EXIT_FAILURE );
    }
    return p;
}

hash_add関数の中で、ハッシュ表の拡張を行うかどうかを判定しています。実際に拡張する処理を行っているのは、recreate関数です。

ハッシュ表の要素数は、現在の要素数の 2倍 + 1 としています。単純に 2倍にしないのは、ハッシュ表の要素数をできるだけ奇数に保っておくためです。本編で解説したように、本当は素数が望ましいところですが、つねに素数を保つ実装はやや難しい上に、計算負荷が非常に大きくなります。

ハッシュ表を拡張する手順としては、以下のようになります。

現在のハッシュ表の中身を、別のところにコピーしておく
現在のハッシュ表を解放して、あらためて Hash_tag構造体のメンバを再初期化する
コピーしておいたハッシュ表を参照して、データがあれば、作り直した方のハッシュ表にハッシュし直す
コピーの方を解放して完了

重要なポイントは、現在のハッシュ表の内容を、新しいハッシュ表へ memcpy関数などを使ってコピーするだけでは駄目だという点です。なぜなら、ハッシュ関数がハッシュ表の要素数に依存した実装になっているからです。要素数が変わってしまったので、同一のデータに対するハッシュ値は変化しています。

実用面を考えると、ハッシュ表の作り変えが起こるタイミングでの Hash_add関数が劇的に遅くなる問題があります。これは普段は高速だった関数が、このタイミングでだけ遅くなるので、こういう挙動が許されない場合（高速であることをアテにしている場合）には問題になります。

参考リンク 🔗

Programming Place Plus　アルゴリズムとデータ構造編　参考書籍
　– 当サイトの参考書籍一覧ページ。アルゴリズムとデータ構造に関する書籍を多数紹介。
Programming Place Plus　アルゴリズムとデータ構造編　リンク集
　– 当サイトの参考Webサイト集。アルゴリズムとデータ構造の全般的な学習に有益なサイトを紹介。

更新履歴 🔗

2019/12/17
- 全体的に見直して、大幅に修正
2019/9/4
- 対応規格を C95 から C99 へ上げる
  - コメントに // を使う
2019/9/3
- 対応規格を C95 から C99 へ上げる
  - 変数宣言をブロックの先頭以外でも行う
2019/9/2
- 対応規格を C95 から C99 へ上げる
  - ループ制御変数を for文の初期設定式で宣言するように修正

’2018/2/22　要素数を意味している「サイズ」について、「要素数」に表記を改めた。

≪さらに古い更新履歴≫

’2015/2/21　サンプルプログラムで、ファイルスコープでよい関数に static を付加。

’2012/5/13　ハッシュ表からの削除と探索のサンプルで、再ハッシュ処理を行う位置が不適切だったのを修正。

’2012/4/22　新規作成。

第７章のメインページへ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ

はてなブックマークに保存	Pocket に保存	Facebook でシェア
X でポスト／フォロー	LINE で送る	noteで書く
RSS	管理者情報	プライバシーポリシー