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

トップページアルゴリズムとデータ構造編【探索アルゴリズム】第7章

問題①

問題① サンプルプログラムの実装における 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関数を呼び出したとき、ハッシュ表の要素数の8割以上が使用済みであれば、ハッシュ表を拡張するようにしてみます。なお、問題①のコードを元に改造しています。

// 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;

    // ハッシュ表の要素数の8割以上が使用済みならば、ハッシュ表を拡張する
    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倍にしないのは、ハッシュ表の要素数をできるだけ奇数に保っておくためです。本編で解説したように、本当は素数が望ましいところですが、つねに素数を保つ実装はやや難しい上に、計算負荷が非常に大きくなります。

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

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

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

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


参考リンク


更新履歴

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

≪さらに古い更新履歴を展開する≫



第7章のメインページへ

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

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る