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

先頭へ戻る

この章の概要

この章の概要です。


関連する話題が、以下のページにあります。

オープンアドレス法

前章に引き続いて、ハッシュ探索を取り上げます。今回は、データの衝突を解決するもう1つの手段であるオープンアドレス法(開番地法)を説明します。

まず、ハッシュ表やハッシュ関数を使うという点は、前章と同じです。違うのは、衝突が起きてしまったときに(前章で書いたように、衝突自体を避けることはできません)、どうやって破綻しないようにするかという部分です。

オープンアドレス法では、衝突が起きたときには、再度何らかの手段を使って、別の空いているバケットを探し出します。ここで、別のバケットを探す手順を、再ハッシュ(リハッシュ)と呼びます。再ハッシュの方法によって、さらにいくつかの亜種に分けられます。

線形走査法

再ハッシュの方法の1つとして、線形走査法があります。

線形走査法では、衝突が発生した場合、その1つ後続を新たな格納位置とします。それでも駄目なら、さらに1つ後続を試すということを繰り返します。

想像してみれば分かると思いますが、この方法だとチェイン法と違って、いずれはハッシュ表が一杯になって、格納できる場所が無くなるという事態が起こり得ます。そのため、ハッシュ表の要素数を正確に想定できなければ利用できません。目安としては、格納するデータの総数は、ハッシュ表の要素数の 80~90% 程度に抑えるといいとされています。

それでは、実際のプログラムを見ていきましょう。

/* main.c */

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

static void create_hash(void);
static void delete_hash(void);
static void print_explain(void);
static void print_blank_lines(void);
static int get_cmd(void);
static void cmd_add(void);
static void cmd_remove(void);
static void cmd_search(void);
static void cmd_exit(void);
static void add_elem(int value);
static void remove_elem(int value);
static int search_elem(int value);
static void get_line(char* buf, size_t size);

/* コマンド */
enum Cmd_tag {
    CMD_ADD,
    CMD_REMOVE,
    CMD_SEARCH,
    CMD_EXIT,

    CMD_NUM
};

/* コマンド文字列の種類 */
enum CmdStr_tag {
    CMD_STR_SHORT,
    CMD_STR_LONG,

    CMD_STR_NUM
};

/* コマンド文字列 */
static const char* const CMD_STR[CMD_NUM][CMD_STR_NUM] = {
    { "a", "add" },
    { "r", "remove" },
    { "s", "search" },
    { "e", "exit" }
};

/* コマンド実行関数 */
typedef void (*cmd_func)(void);
static const cmd_func CMD_FUNC[CMD_NUM] = {
    cmd_add,
    cmd_remove,
    cmd_search,
    cmd_exit
};


static Hash gHash;


int main(void)
{
    create_hash();

    while( 1 ){
        print_explain();

        if( get_cmd() == 0 ){
            break;
        }

        print_blank_lines();
    }

    delete_hash();

    return 0;
}

/*
    ハッシュ表を作成
*/
void create_hash(void)
{
    gHash = hash_create( 100 );
}

/*
    ハッシュ表を削除
*/
void delete_hash(void)
{
    hash_delete( gHash );
    gHash = NULL;
}

/*
    説明文を出力
*/
void print_explain(void)
{
    puts( "コマンドを入力してください。" );
    printf( " データを登録: %s (%s)\n", CMD_STR[CMD_ADD][CMD_STR_SHORT], CMD_STR[CMD_ADD][CMD_STR_LONG] );
    printf( " データを削除: %s (%s)\n", CMD_STR[CMD_REMOVE][CMD_STR_SHORT], CMD_STR[CMD_REMOVE][CMD_STR_LONG] );
    printf( " データを探索: %s (%s)\n", CMD_STR[CMD_SEARCH][CMD_STR_SHORT], CMD_STR[CMD_SEARCH][CMD_STR_LONG] );
    printf( " 終了する: %s(%s)\n", CMD_STR[CMD_EXIT][CMD_STR_SHORT], CMD_STR[CMD_EXIT][CMD_STR_LONG] );
    puts( "" );
}

/*
    空白行を出力
*/
void print_blank_lines(void)
{
    puts( "" );
    puts( "" );
}

/*
    コマンドを受け付ける

    戻り値:
        終了コマンドを入力されたら 0 を返す。
        それ以外のときは 0以外の値を返す。
*/
int get_cmd(void)
{
    char buf[20];
    enum Cmd_tag cmd;
    int i;

    get_line( buf, sizeof(buf) );

    cmd = CMD_NUM;
    for( i = 0; i < CMD_NUM; ++i ){
        if( strcmp( buf, CMD_STR[i][CMD_STR_SHORT] ) == 0
         || strcmp( buf, CMD_STR[i][CMD_STR_LONG] ) == 0
        ){
            cmd = i;
            break;
        }
    }

    if( cmd == CMD_EXIT ){
        return 0;
    }
    else if( 0 <= cmd && cmd < CMD_NUM ){
        CMD_FUNC[i]();
    }
    else{
        puts( "そのコマンドは存在しません。" );
    }

    return 1;
}

/*
    addコマンドの実行
*/
void cmd_add(void)
{
    char buf[40];
    int value;

    puts( "追加する数値データを入力してください。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );

    add_elem( value );
}

/*
    removeコマンドの実行
*/
void cmd_remove(void)
{
    char buf[40];
    int value;

    puts( "削除する数値データを入力してください。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );

    remove_elem( value );
}

/*
    searchコマンドの実行
*/
void cmd_search(void)
{
    char buf[40];
    int value;

    puts( "探索する数値データを入力してください。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );

    if( search_elem( value ) ){
        puts( "見つかりました。" );
    }
    else{
        puts( "見つかりませんでした。" );
    }
}

/*
    exitコマンドの実行
*/
void cmd_exit(void)
{
    puts( "終了します。" );
}

/*
    要素を追加する

    引数:
        value:	追加する要素の数値データ。
*/
void add_elem(int value)
{
    hash_add( gHash, value );
}

/*
    要素を削除する

    引数:
        value:	削除する要素の数値データ。
*/
void remove_elem(int value)
{
    hash_remove( gHash, value );
}

/*
    要素を探索する

    引数:
        value:	探索する要素の数値データ。
    戻り値:
        発見できたら 0以外、発見できなければ 0 を返す。
*/
int search_elem(int value)
{
    return hash_search( gHash, value ) != NULL;
}

/*
    標準入力から1行分受け取る

    受け取った文字列の末尾には '\0' が付加される。
    そのため、実際に受け取れる最大文字数は size - 1 文字。

    引数:
        buf:    受け取りバッファ
        size:   buf の要素数
    戻り値:
        buf が返される
*/
void get_line(char* buf, size_t size)
{
    fgets(buf, size, stdin);

    /* 末尾に改行文字があれば削除する */
    char* p = strchr(buf, '\n');
    if (p != NULL) {
        *p = '\0';
    }
}
/* hash.c */

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


enum{
    EMPTY    = -1,      /* 空であることを表す値 */
    DELETED  = -2,      /* データが削除されたことを表す値 */
};


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

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


/* ハッシュ表を作る */
Hash hash_create(int size)
{
    struct Hash_tag* hash;
    int i;

    assert( size > 0 );

    hash = xmalloc( sizeof(struct Hash_tag) );
    hash->table = xmalloc( sizeof(int) * size );
    for(i = 0; i < size; ++i){
        hash->table[i] = 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;
    int index;
    int i;


    /* 特別な値と同じ値を持つデータは許可しない */
    assert(data != EMPTY && data != DELETED);

    index = hash_func( hash, data );

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

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

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


    index = hash_func( hash, data );

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

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

        index = rehash_func( hash, index );
    }
}

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


    index = hash_func( hash, data );

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

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

        index = rehash_func( hash, index );
    }

    return NULL;
}




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

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

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

#ifndef HASH_H_INCLUDED
#define HASH_H_INCLUDED


typedef struct Hash_tag* Hash;


/*
    ハッシュ表を作る

    引数:
        size:	ハッシュ表の大きさ
    戻り値:
        作成されたハッシュ表。
        使い終わったら、hash_delete関数に渡して削除する。
*/
Hash hash_create(int size);

/*
    ハッシュ表を削除する

    引数:
        hash:	hash_create関数で作成したハッシュ表
*/
void hash_delete(Hash hash);

/*
    ハッシュ表にデータを追加する

    引数:
        hash:	hash_create関数で作成したハッシュ表
        data:	追加するデータ
*/
void hash_add(Hash hash, int data);

/*
    ハッシュ表からデータを削除する

    引数:
        hash:	hash_create関数で作成したハッシュ表
        data:	削除するデータ
*/
void hash_remove(Hash hash, int data);

/*
    ハッシュ表からデータを探索する

    引数:
        hash:	hash_create関数で作成したハッシュ表
        data:	探索するデータ
    戻り値:
        ハッシュ表の要素へのポインタ。
        見つからなければ NULL。
*/
int* hash_search(Hash hash, int data);

#endif

main.c と hash.h に関しては、前章のサンプルプログラムをまったく同じです。変更したのは hash.c だけです。

ハッシュ表の作成

ハッシュ表を探索する関数は、hash_create関数です。引数にハッシュ表の要素数を指定します。

ハッシュ表を動的に作成した後には、すべてのバケットを EMPTY で初期化しています。EMPTY は、その場所には何も有効なデータがないことを表す列挙定数(C言語編第50章参照)です。

EMPTY の他にも、DELETED という列挙定数も定義されていますが、これらは、ハッシュ表に登録するいかなるデータの値とも異なる値でなければなりません。ここでは、-1 と -2 を割り当てていますが、もしこれらの値を登録しようとしたら、何らかの手段で失敗させなければ、以降で説明する理論が破綻してしまいます。

ハッシュ表への要素の追加

要素の追加は、hash_add関数で行っています。

まず、hash_func関数を呼び出して、格納位置を決定しています。そうして決定された位置が空であれば、その位置へ格納できます。

空かどうかは、その位置に EMPTY か DELETED が格納されていることで判定できます。ハッシュ表を作成した段階で、すべてのバケットは EMPTY で初期化されているので、初期状態では必ず空になっているとみなせます。DELETED については、要素を削除するところで説明します。

もし空でなかったら、再ハッシュを行います。ここがチェイン法との根本的な違いです。

再ハッシュは、rehash_func関数で実装しています。線形走査法なので、再ハッシュは、単に1つ次の位置へ進ませるだけです。もし、ハッシュ表の末尾まで来てしまっていたら、先頭に戻すようにします。

再ハッシュを繰り返していくと、いずれ元の位置まで戻ってきてしまいます。ここでは、ハッシュ関数を呼び出した回数をカウントしていき、ハッシュ表の要素数以上になってしまったら、一周したとみなして終了させるようにしています。

ハッシュ表からの要素の削除

要素の削除は、hash_remove関数で行っています。

格納位置を決定する手順は、先ほどと同じで、まずは hash_func関数で最初の位置を決定し、その位置に目的のデータがなければ、rehash_func関数で再ハッシュを行います。

目的のデータが見つかったら、その位置に、削除済みであることを表す列挙定数 DELETED を格納します。実装上、ここの理解が難しいところでしょう。なぜ、EMPTY を格納するのでは駄目なのでしょうか。

例えば、要素数が 5 のハッシュ表があるとして、ここに a,b,c というデータを格納します。ハッシュ関数によって、それぞれ 0, 1, 0 の位置に格納されることになったとしましょう。a と b を格納すると、次のような状態になります。

a
b
EMPTY
EMPTY
EMPTY

次に c を格納しようとします。最初は 0 の位置に格納しようと試みますが、そこには既に a がありますから、再ハッシュを行います。再ハッシュによって格納位置は 1 となりますが、そこには b があります。再び再ハッシュを行い、格納位置は 2 となります。ここには何もないので格納できます。

a
b
c
EMPTY
EMPTY

さて、ここで b を削除します。ハッシュ関数によって、b の格納位置は 1 だと分かり、確かにそこに目的の値 b がありますから、これを削除します。ここでもし、EMPTY を格納することで実現しようとすると、次の状態が出来上がります。

a
EMPTY
c
EMPTY
EMPTY

次に、c を削除します。ハッシュ関数によって、c の格納位置は 0 だと分かりますが、そこには a があるので c とは一致しません。そこで、再ハッシュを行い、新たな格納位置 1 を得ます。そこには EMPTY があるので、ここで探索は打ち切られてしまいます。

こういうとき、データがなくても探索を打ち切らずに探索を繰り返させるためには、区別する手段が必要であり、それが DELETED なのです。EMPTY が見つかったら探索を打ち切るが、DELETED の場合はその位置を無視するだけで次へは進ませるということです

ハッシュ表からの要素の探索

要素の探索は、hash_search関数で行っています。

探索は、削除とほとんど同じ実装で済むので、詳細は割愛します。


二重ハッシュ法

線形走査法では、1度衝突が起こると、再ハッシュが起こる機会が増加しやすいという悪い特性があります。例えば、格納位置が 0 となるデータa, b, c が登録されると、

a
b
c
EMPTY
EMPTY

このような状態が出来上がります。この後、d を登録するとき、d のハッシュ値が 0 でも 1 でも 2 でも衝突が起き、いずれも再ハッシュが必要となります。こうやって再ハッシュの機会が増加すると、性能を低下させてしまいますから、できるだけ避けたいところです。

このような状態が起こりやすい原因は、再ハッシュの際に「次のバケットを調べる」という方法を採っているため、1箇所に集中的にデータの塊ができるからです。従って、1箇所に集中しないように、もう少し離れた位置に再ハッシュされるように工夫すれば良いことが分かります。その方法として、二重ハッシュ法があります。

二重ハッシュ法では、再ハッシュの際に「次のバケット」ではなく、「2次ハッシュで算出された値だけ離れたバケット」を調べるようにします。

2次ハッシュというのは、初回に使ったハッシュ関数とは別のハッシュ関数という程度の意味です。線形走査法のサンプルプログラムで、rehash_func という関数を作っていましたが、これのことだと思って問題ありません。つまり、rehash_func関数の中身を変えれば、二重ハッシュ法による実装になります。

2次ハッシュの実装で必ず守らなければならないことは、ハッシュ値が 0 にならないようにすることです。ハッシュ値が 0 だと、同じバケットへの参照を繰り返すだけですから、一向に空きバケットを見つけられません。

なお、ハッシュ値が 1 だと、線形走査法とまったく同じ挙動になります

ハッシュ表の要素数と、2次ハッシュのハッシュ値とは、互いに素になっていることが望ましいと言われています。そうでないと、再ハッシュが繰り返されたとき、同じ格納位置ばかりを調べてしまう可能性があり、空きバケットがあるのにも関わらず、それを見つけ出せずに失敗してしまいます。

例えば、ハッシュ表の要素数が 20 で、初回のハッシュで格納位置が 3 になり、2次ハッシュのハッシュ値が 4 だとします。この場合、3, 7, 11, 15, 19, 3, 7, ... のように調べることになります。このように同じ値でループしてしまいます。

前章でも触れたように、ハッシュ表の要素数を素数にしておくことが簡単な解決策でしょう。先の例で、ハッシュ表の要素数が 23 であれば、3, 7, 11, 15, 19, 0, 4, 8, 12, 16, 20, 1, 5, 9, 13, 17, 21, 2, 6, 10, 14, 18, 22, 3, 7, ... というように、すべてのバケットを調べ尽くせます。

まとめ

ハッシュ探索は、要素の追加も削除も探索も、すべて O(1) で行える非常に優れたアルゴリズムです。

オープンアドレス法は、チェイン法と違って、連結リストを使わないので、nextポインタのような余計なデータがありません。そのため、メモリの使用効率の面で優れています。

一方で、メモリの許す限りはどこまでも拡張できるチェイン法と違い、オープンアドレス法はハッシュ表の要素数分のデータしか登録できません。そのため、事前にデータの総数が分かっていないとうまく使えません。

線形走査法と二重ハッシュ法の比較ですが、一般的に後者の方がパフォーマンスは良くなります。これは、線形走査法では、衝突によって使用済みバケットの塊ができやすい問題が、二重ハッシュ法では、ある程度解消されるからです。


練習問題

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

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


解答ページはこちら


参考リンク



更新履歴

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

'2018/2/12 サンプルプログラムの改善(fgets が受け取った改行文字の削除の方法を修正。const、static の付加)

'2017/11/13 サンプルプログラムで、存在しないコマンドが入力されたときに、未初期化の変数を参照していたのを修正。

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

'2014/1/22 O(1) が 0(1) になっていた誤植を修正。

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

'2012/4/22 新規作成。



前の章へ (第6章 ハッシュ探索①(チェイン法))

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

Programming Place Plus のトップページへ


はてなブックマーク Pocket に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS
管理者情報 プライバシーポリシー