アルゴリズムとデータ構造編【探索】 第6章 ハッシュ探索①(チェイン法)

先頭へ戻る

この章の概要

この章の概要です。

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

ハッシュ

この章では、ハッシュ探索という手法を説明します。

ハッシュ探索は、O(1) という圧倒的に小さい計算量で探索を行える非常に優れたアルゴリズムです。 これは、目的の値がどこにあるのかを1回の計算だけで導き出せることを意味しています。 どうしたらこんなことが可能になるのでしょう?

原理としては、データを登録する際に、その値を使って何らかの計算を施して、 格納位置(通常、データ構造としては配列を使うので、その添字のことになります)を決定します。
例えば、登録するデータが整数だと仮定します。 登録するデータの値を n としたとき、n を 100 で割った余りを格納位置とすれば、 537 というデータは、「537 % 100 == 37」ですから、37 が格納位置となります。
探索するときも同様で、537 を探索したいとすれば、「537 % 100」という計算を行います。 こうして、ただちに 37番目の位置にあることが分かります。

このように、データの値と格納位置を何らかの約束事によって対応付けてしまうというのが基本的な考え方になります。 従って、最初の段階で、好き勝手に登録されているデータ列からの探索には利用できません

なお、ハッシュ探索の用語としては、データが格納される配列のことをハッシュ表と呼び、 ハッシュ表の各要素をバケットと呼びます。
また、格納位置を決めるための計算は、ある値 x を、添字index へと写像する関数 f(x) と考えられることから、 ハッシュ関数と呼びます。 ハッシュ関数が返す値は、ハッシュ値と呼ばれます。

衝突

ハッシュ探索を実際に実装するには、解決しなければならない問題があります。

一番の問題は、ハッシュ関数によって決定された格納位置が、別のデータによって使用される可能性がある点です。 例えば、先ほどの「n % 100」というハッシュ関数を使うと、537 でも 837 でも 10037 でも、すべて 37番目の位置を使ってしまいます。 この現象を、衝突(まれにシノニムと呼ぶこともあります)といいます。

結論からいうと、衝突を避けることはできません。 そこで、衝突が起きたとしても矛盾が起きない方法を考えることになります。 幸い、その方法論は幾つか確立されています。 この章ではこの後、その1つであるチェイン法を説明します。 もう1つの方法であるオープンアドレス法は、次章で説明します。

チェイン法

チェイン法(分離連鎖法)は、同じハッシュ値を持ったデータを、 連結リスト(データ構造編第3章)によってつなげていくことによって、衝突を解決する方法です。 イメージとしては、次の図のようになります。

チェイン法のイメージ図

こうすれば、データを格納する際、決定された格納位置に既にほかのデータがあれば、 連結リストに要素を追加することで対応できます。


それでは、実際にプログラムを作成してみましょう。

/* 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 "ppps_int_slist.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


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

static int hash_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(PPPSIntSlist) * size );
	for(i = 0; i < size; ++i){
		hash->table[i] = ppps_int_slist_create();
	}
	hash->size = size;

	return hash;
}

/* ハッシュ表を削除する */
void hash_delete(Hash hash)
{
	int i;

	for(i = 0; i < hash->size; ++i){
		ppps_int_slist_delete( hash->table[i] );
	}
	free( hash->table );
	free( hash );
}

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

	ppps_int_slist_add_front( hash->table[index], data );
}

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

	ppps_int_slist_delete_elem( hash->table[index], data );
}

/* ハッシュ表からデータを探索する */
int* hash_search(Hash hash, int data)
{
	PPPSIntSlist elem;

	int index = hash_func( hash, data );

	elem = ppps_int_slist_search( hash->table[index], data );
	if( elem == NULL ){
		return NULL;
	}
	return &elem->value;
}




/* ハッシュ関数 */
int hash_func(Hash hash, int key)
{
	return key % 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
#define HASH_H


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

このプログラムを実行すると、コマンドの入力を求められます。例えば、"a" または "add" と入力すれば、ハッシュ表へ要素を追加しようとします。 このコマンドの場合は、続けて、追加する要素の入力を求められます。
ハッシュ表への要素の追加、要素の削除、探索のコマンドを実装しています。 とりあえず、適当に追加や削除を行い、動作を確かめてみて下さい。


それでは、実装内容を確認していきましょう。
今回、ハッシュ探索に関わる部分は hash.c と hash.h に分離してあります。 また、チェイン法の実装のために連結リストを必要としますが、 これはコードライブラリにあるサンプル実装 ppps_int_slist を使っています。

ハッシュ表の作成

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

ハッシュ表の各要素(バケット)は、連結リストになります。 初期状態では、連結リストの先頭部分だけが並んだような状態になっています。

ハッシュ表の適切な要素数は用途次第で決められます。 チェイン法の場合、仮に登録するデータの総数が最大で 100件のとき、ハッシュ表の要素数が 100以上必要だという訳ではありません。 なぜなら、チェイン法では、連結リストによって自動的に拡張されていく部分があるため、 ハッシュ表の要素数以上の要素が格納できるからです。
しかし、格納されるデータの総数よりも、ハッシュ表の要素数の方が小さい場合、確実に衝突が発生することになります。 その結果、連結リストが長く伸びていく可能性が高まることになります。 連結リストが伸びる場合、リスト要素の動的確保が行われることによる速度低下や、メモリ使用量の増加が起こる他、 探索の際にも、リストを辿る回数が増えるため、全体的に性能が悪化します

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

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

まず、hash_func関数を呼び出して、格納位置を決定しています。 この hash_func関数は名前の通り、ハッシュ関数を実装したものです。
このサンプルプログラムでは、ハッシュ関数は、渡された整数値をハッシュ表の要素数で割った余りを返しています。

格納位置が決定したら、その位置にある連結リストの先頭に挿入しています。 連結リスト上の要素の並び順には特に意味がないのであれば、先頭に挿入した方が高速です。

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

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

ここでもやはり、hash_func関数を呼び出して格納位置を調べます。 その位置にある連結リストを辿ることで、目的の要素を見つけ出せるので、あとは連結リストからの削除処理を行えば実現できます。

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

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

探索は、削除とほとんど同じです。 ハッシュ関数によって格納位置を調べ、そこにある連結リストを辿っていけば良いです。

ハッシュ関数

サンプルプログラムでは、データの値 n と、ハッシュ表の要素数 s を使って、「n % s」という計算によって格納位置を決定しています。 しかし、例えば、登録するデータが int型でなく、文字列だとすれば、このような計算が行えません。

どんな種類のデータであっても、何とか整数値にできればいいので、 例えば文字列なら、1文字1文字を文字コードにして考えればいいでしょう。 それぞれの文字の文字コードを合計すれば、整数値を得られます。
実数のデータなら、小数点以下の部分がなくなるように、10倍なり 100倍なりすれば、整数値を得られます。
こういった工夫を加えれば、基本的にどんな種類のデータであっても扱えるはずです。

なお、添字として整数を使うのが普通の配列(データ構造編第1章)ですが、 整数以外(主に文字列)を使う特殊な配列を、連想配列と呼びます。よく、「連想配列=ハッシュ」というように使われますが、本来、連想配列を実装する1つの手段としてハッシュがあるに過ぎません。


次にハッシュ関数の作り方ですが、まず次のポイントを抑えておくことが重要になります。

散らばりが悪い、偏った結果を返しやすいハッシュ関数を使うと、衝突が頻繁に起こってしまいますから、性能悪化を招きやすくなります。 また、いくら良い結果を返すとしても、ハッシュ関数そのものが低速だと、全体的な性能低下を招くことは明らかでしょう。

「n % s」というハッシュ関数の場合、ハッシュ表の要素数 s を素数にすることで、 偏った結果になりにくいことが知られています。
また、s の値として特に悪いのは、2 のべき乗です。 例えば、32, 256, 65536 といった数ですが、こういった数を使うと、n の下位の方のビットだけによって結果が決定してしまいます。 もちろんデータの内容次第ではあるのですが、下位に近いビットが同じになるケースは多く、偏りが起こりやすいと言えます。

まとめ

ハッシュ探索は、要素の追加も削除も探索も、すべて O(1) で行える非常に優れたアルゴリズムです。
しかし、チェイン法においては、衝突が起きている場合、連結リストを辿ることになるので、実際の性能はこれより低くなる可能性があります。 基本的に避けられる事態ではありますが、最も悪いケースでは、すべてのデータが同じ位置に集まることになり、 この場合、O(n) の性能にまで悪化します。

ハッシュ探索では、要素がどのような順番で並んでいるかに関しては、考えに入っていません。 そのため、登録済みのデータを昇順に書き出す、といった処理は効率的に行うことができないという欠点もあります。

チェイン法においては、連結リストの部分がどうしても長くなってしまう場合、リスト構造にこだわらず、 二分探索木(【データ構造】第8章)などのツリー構造を使うという手もあります。 連結リストを辿る部分は線形探索法(第1章)の性能しか出ませんが、 ツリー構造ならば、二分探索法(第4章)程度の性能を期待できるので、 全体の性能向上に貢献するかも知れません。


練習問題

問題① サンプルプログラムを改造して、ハッシュ表の状況を出力するコマンドを実装して下さい。

問題② ハッシュ表に登録されている要素数を返す関数を作成して下さい。

問題③ 次の文字列専用のハッシュ関数は、あまり良い実装ではありません。 なぜでしょうか。また、どうすればより良くなるでしょうか。

int hash_func(Hash hash, const char* key)
{
	int h = 0;
	
	while( *key != '\0' ){
		h += *key;
		++Key;
	}
	
	return h % hash->size;
}


解答ページはこちら


参考リンク

更新履歴

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

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

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

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

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

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





前の章へ(第5章 二分探索の改良(内挿探索))

次の章へ(第7章 ハッシュ探索②(オープンアドレス法))

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

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS