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

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

この章の概要

この章の概要です。

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


オープンアドレス法

前章に引き続いて、ハッシュ探索を取り上げます。

ハッシュ探索そのものの考え方については、前章のとおりです。本章では、衝突をチェイン法とは異なるやり方で対処するオープンアドレス法(開番地法)を説明します。

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

再ハッシュのやり方にもいくつか方法があり、さらにいくつかの亜種に分けられます。ここでは、線形走査法と、二重ハッシュ法を取り上げることにします。

線形走査法

オープンアドレス法の再ハッシュの方法の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 enum CmdRetValue_tag get_cmd(void);
static enum CmdRetValue_tag cmd_add(void);
static enum CmdRetValue_tag cmd_remove(void);
static enum CmdRetValue_tag cmd_search(void);
static enum CmdRetValue_tag 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
};

// コマンドの戻り値
enum CmdRetValue_tag {
    CMD_RET_VALUE_CONTINUE,
    CMD_RET_VALUE_EXIT,
};
// コマンド文字列
static const char* const CMD_STR[CMD_NUM][CMD_STR_NUM] = {
    { "a", "add" },
    { "r", "remove" },
    { "s", "search" },
    { "e", "exit" }
};

// コマンド実行関数
typedef enum CmdRetValue_tag (*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() == CMD_RET_VALUE_EXIT ){
            break;
        }

        print_blank_lines();
    }

    delete_hash();

    return 0;
}

/*
    ハッシュ表を作成
*/
void create_hash(void)
{
    gHash = hash_create( 101 ); // 素数が好ましい
}

/*
    ハッシュ表を削除
*/
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以外の値を返す。
*/
enum CmdRetValue_tag get_cmd(void)
{
    char buf[20];
    get_line( buf, sizeof(buf) );

    enum Cmd_tag cmd = CMD_NUM;
    for( int 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( 0 <= cmd && cmd < CMD_NUM ){
        return CMD_FUNC[cmd]();
    }
    else{
        puts( "そのコマンドは存在しません。" );
    }

    return CMD_RET_VALUE_CONTINUE;
}

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

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

    add_elem( value );

    return CMD_RET_VALUE_CONTINUE;
}

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

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

    remove_elem( value );

    return CMD_RET_VALUE_CONTINUE;
}

/*
    searchコマンドの実行
*/
enum CmdRetValue_tag 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( "見つかりませんでした。" );
    }

    return CMD_RET_VALUE_CONTINUE;
}

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

    return CMD_RET_VALUE_EXIT;
}

/*
    要素を追加する

    引数:
        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; // ハッシュ表
    size_t           size;  // data の要素数
};

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(int) * size );
    for( size_t 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)
{
    // 特別な値と同じ値を持つデータは許可しない
    assert(data != EMPTY && data != DELETED);

    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] == 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;
    size_t index = hash_func( hash, data );

    for( size_t 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;
    size_t index = hash_func( hash, data );

    for( size_t 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;
}




/*
    ハッシュ関数
*/
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;
}
// hash.h

#ifndef HASH_H_INCLUDED
#define HASH_H_INCLUDED


typedef struct Hash_tag* Hash;


/*
    ハッシュ表を作る

    引数:
        size:   ハッシュ表の大きさ
    戻り値:
        作成されたハッシュ表。
        使い終わったら、hash_delete関数に渡して削除する。
*/
Hash hash_create(size_t 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 の値は、ハッシュ表に登録されるどのデータの値とも異なる値でなければなりません。ここでは -1 を使っていますが、もし、実際のデータとして -1 をハッシュ表に登録すると、線形走査法のアルゴリズムは破綻してしまいます。

EMPTY の他にも、DELETED という列挙定数も定義されていますが、こちらも同様で、ハッシュ表に登録されるどのデータの値とも異なる値でなければなりません。

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

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

まず、関数の先頭の assert によって、登録しようとしているデータが EMPTY や DELETED に割り当てている値と同じでないか確認しています。この確認の必要性は、「ハッシュ表の作成」で説明したとおりです。

次に、hash_func関数を呼び出して、格納位置を決定します。決定された位置のバケットが空であれば、その位置へ格納できます。

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

もしバケットが空でなかったら、つまり衝突していたら、再ハッシュを行います。ここがチェイン法との違いです。

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

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

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

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

格納位置を決定する手順は、先ほどと同じで、まずは hash_func関数によって位置を取得します。その位置に EMPTY があれば、該当のデータはハッシュ表に存在しないので、その時点で終了です。

データがあったら、その値が目的の値と一致しているかを確認します。チェイン法と違って、ハッシュ関数で割り出された位置にデータがあるとは限りませんから、本当に値が一致しているかどうかは確認しなければなりません。

データが一致しない場合は、rehash_func関数で再ハッシュを行い、次の位置へ進みます。

データが一致するバケットを発見したら、その位置に、削除済みであることを表す列挙定数 DELETED を格納します。ここの理解がやや難しいところです。削除したのなら、なぜ EMPTY を格納しないのでしょうか。

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

a
b
EMPTY
EMPTY
EMPTY

次に c を格納します。c の格納位置を生成したところ、a と同じで 0 になったとします(つまり衝突する)。0 の位置に格納しようと試みますが、そこにはすでに a がありますから、再ハッシュを行います。再ハッシュによって格納位置は1つ後ろの 1 となりますが、そこには b があります。2回目の再ハッシュを行い、格納位置は 2 となります。ここには何もないので格納でき、次のようになります。

a
b
c
EMPTY
EMPTY

ここで b を削除します。ハッシュ関数によって、b の格納位置は 1 だと分かり、確かにそこに目的の値 b がありますから、これを削除します。正しいやり方では、DELETED を格納しなければなりませんが、EMPTY を格納したとします。すると、次のようになります。

a
EMPTY
c
EMPTY
EMPTY

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

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

EMPTY のときも無視して、次へ進ませればいいと思うかもしれません。そうしたとすると、ハッシュ表の中に目的のデータがない場合に、ハッシュ表のすべてのバケットを調べつくすまで「ない」と確定できなくなってしまいます。これでは線形探索をしているのと変わらないので、大幅な効率低下です。

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

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

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



線形走査法による方法は単純で分かりやすいものの、1度衝突が発生してしまうと、それ以降も衝突が起こりやすくなる問題を抱えています。

たとえば、3種類のデータ a,b,c のハッシュ値がいずれも 0 になってしまうとします。線形走査法のアルゴリズムの下で、a,b,c をハッシュ表に登録すると、次のような状態になります。

a
b
c
EMPTY
EMPTY

ここで d を追加登録するとします。d のハッシュ値が 0 であっても 1 であっても 2 であっても衝突が起き、いずれも再ハッシュが必要となります。

線形走査法による解決方法では、本来の格納位置(初回のハッシュ関数で生成された位置)に格納できなかった要素たちが、すぐ後ろのところに集まってかたまりをつくってしまうところに原因があります。そのかたまりの場所は本来、ほかの要素が真っ先に入り込みたかった場所なのです。

線形走査法の問題を解決するために、次の項でほかの手法を紹介します。


二重ハッシュ法

オープンアドレス法の再ハッシュの方法の1つとして、二重ハッシュ法があります。

二重ハッシュ法は、基本的な発想は線形走査法のままですが、再ハッシュのときには、2次ハッシュを使って算出された値の分だけ離れたバケットを調べるようにします。

線形走査法のサンプルプログラムで、rehash_func という関数を作っていました。

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

ここで + 1 のところが線形走査法のポイントです。こういう実装なので、つねに1つずつしか後ろに移動しませんから、衝突した要素のかたまりを生み出しやすいのです。そこで、+ 1 ではなく、もう少し大きく離れた位置を作り出せば、かたまりが分散できるのではないか、というのが二重ハッシュ法の考え方です。

そこで、2次ハッシュ関数を導入します。

/*
    2次ハッシュ関数
*/
inline size_t second_hash_func(Hash hash, size_t key)
{
    return 2;
}

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

こうすると、2つずつ進みます。この程度なら関数化するまでもないですが、ここでは inline を付加したうえで関数にしておきました。もちろん、データの値を使ってなんらかの計算式でハッシュ値を生成することも可能です(key % 97 + 1 といった計算式がよく使われています)。

2次ハッシュの実装として必ず避けなければならないのは、0 を返すことです。2次ハッシュが返す値は、バケットの位置ではなくて、何個離れたバケットを使うかという “距離” ですから、0 を返すと、現在のバケットばかりを調べ続けて無限ループになってしまいます。

ところで、2次ハッシュとして 2 のような、固定された単純な値を返すことには危険な面もあります。たとえば、ハッシュ表の大きさが 16 で、初回のハッシュ値が 3 だったとします。3 の位置をみて衝突したとすると、その後の再ハッシュで生成される格納位置は、3, 5, 7, 9, 11, 13, 15, 1 です。みてのとおり、偶数位置をまったく確認していません。もしかしたら、奇数位置には空きバケットはなく、偶数位置にはあったかもしれないのに、です。

この問題を避けるには、ハッシュ表の要素数と、2次ハッシュのハッシュ値とを、互いに素の関係にすることです

ハッシュ表の要素数を素数にするという、これまでどおりの指針がここでも生きます。ハッシュ表の大きさを 16 でなく、素数である 17 に変えてやれば、2次ハッシュがつねに 2 を返すという実装であっても、3, 5, 7, 9, 11, 13, 15, 0, 2, 4, 6, 8, 10, 12, 14, 16, 1 というように、すべての位置を調べ尽くせます。

ハッシュ表の要素数を素数にできないなら、2次ハッシュの側で工夫する必要があります。

まとめ

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

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

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

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


練習問題

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

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


解答ページはこちら


参考リンク


更新履歴

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

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



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

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

Programming Place Plus のトップページへ



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