ハッシュテーブル

探索アルゴリズム

•表の中に入っているデータ（表の中のデータの個数をn個と

する）の中から，目的のデータを探索するアルゴリズム

–線形探索

•表中のデータを１つ１つ順に端から調べるだけの単純な探索法

•計算量は O(n)

–二分探索，木

•キー値の比較に基づき，途中で探索候補を絞っていくことによっ

て,表全部を調べることなく高速化を図る

•計算量は O(log n)

–ハッシュ法

•平均してO(1)の計算量で探索，挿入，削除の全てを行うことがで

きる

配列による探索

•「キー値の範囲をおおうような配列」を使う方法

（例）レコード｛学籍番号，名前，生年月日｝

–キー値：学籍番号（1から100までの値をとりうる)

–1～100までの整数を添字とする配列を用意

（例）配列student[1]～student[100] に，それぞれレコード

データを入れる

–配列を使って，キー値からレコードを取り出す方法：

与えられたキー値（この場合，学籍番号）を添字として，そ

の配列を調べる

•単純に考えて，「データが何個存在するかに関係なく，

配列を１つ調べればいい」と考えれば，探索1回当り

の計算量はO(1)

ハッシュ法

•配列による探索

–配列の添字として使用できるのは正の整数のみ

–キーの値が限られた範囲の整数である場合にしか使えない（一般的

ではない）

•ハッシュ法

–キーの値を直接配列の添字とするのではなく，キー値をある関数

（ハッシュ関数）によって整数に変換して，この関数値を添字として配

列を参照する

–キー値として，文字列など可能（名前による検索など）

（例）名前によって探索する場合

１．関数Hash に引数として，検索したい名前(文字列)を与える．

２．関数Hash は，与えられた文字列からなんらかの計算を行い，整数

値を返す．

３．その整数値を配列の添字とする配列を参照する．

ハッシュ法

•ハッシュ関数：

–キー値を整数に変換する関数

–常に，同じハッシュ関数を使うので，同じキーの値を与えた時,結

果はいつも同じになる．

→データを挿入する時も探索する時も配列の同じ場所を参照する

•ハッシュ値

–ハッシュ関数の計算によって得られる整数値

•ハッシュテーブル

–データが格納された配列

•ハッシュ関数の計算，配列の参照にかかる時間は，デー

タ数nに無関係で，O(1)の計算量

衝突

•キーのとり得る値の種類に比べて，配列の添字

として使える値の範囲は小さい

–配列の添字：

正の整数で，4バイトの整数（0から2147483648）

–キーのとり得る値の種類の例：

４バイトの浮動小数なら： -3.4e38から3.4e38

•全てのキー値を，1対１で整数に変換することは

不可能

•違うキーの値でも，ハッシュ値（ハッシュ関数を適

用した結果）が同じになるということが起る．

→このような事態を衝突と呼ぶ

衝突への対処法

• 連鎖法(チェイン法)

– ハッシュ関数の値(ハッシュ値）が同じで

あるレコード同士をリストでつないでおく

–ハッシュテーブルには，リストを指すポイン

ターを入れる

• 開放番地法

–ハッシュテーブルそのものにレコードを入れる

連鎖法(チェイン法)

•ハッシュ関数の値(ハッシュ値）が同じであるレコード同士をリ

ストでつないでおく

•下の図のようにハッシュテーブルの各要素には，レコードを直

接入れるのではなく，レコードをつないだリストの先頭を指す

ポインターを入れる

•探索の際は，まずハッシュ関数を計算して，ハッシュテーブル

から特定のリストを選んで，その後リスト上を探索するという

手順になる

・

Hash Table

開放番地法のデータ挿入手順

•まず，ハッシュテーブルからハッシュ値が指す要素を調べる．

•もしそこにデータが入っていなかったら，そこにレコードを入れる．別

のレコードがすでにそこに入っていれば，ハッシュテーブルの別の場

所を調べ，そこが未使用であればそこへデータを入れ，使用済であ

ればまた別の場所を探すという方法をとる．

•この方法では,ハッシュ表の各要素が使用中であるか否かを表す印

が必要となる

0 used record

1 free

2 free

4 free

3 used record

m used record

m-1 free

mark Hash Table

開放番地法

•開放番地法では，要素を調べたときに使用済であった場合

に，次にどこの場所を調べるかということを前もって方針を

決めておく

–線形走査法

•使用済であった場合に，次の要素，その次の要素．．．

と添字を１つずつ増やしながら調べていく方法

–均一ハッシュ法

•違うハッシュ値を持つデータ同士がひとかたまりにな

らないようにする方法

線形走査法

•使用済であった場合に，次の要素，その次の要素．．．と添字

を１つずつ増やしながら調べていく方法

•クラスターによる性能低下が起こる

–下図では，「１から５」に固まり（クラスター）ができている

–ハッシュ値が１のレコードを挿入しようとするとき，１から５までは塞がっ

ているので，６の場所に入れる．

–その付近のハッシュ値を持つデータは次々に固まりに加わっていく．

–このように．同じ値のハッシュ値だけでなく，違う値のハッシュ値の影響

を受けて固まりができていく現象をクラスターという

1 record

2 record

3 record

4 record

5 record

1 record

均一ハッシュ法

•関数をm個（関数h1,h2,....hmとし，これらはある同じ値を

入力しても全て違う値を返すとする）用意して，最初に関

数h1により，ハッシュテーブルを調べ,塞がっていれば次

に関数h2を適用して，その場所を調べる．さらに塞がって

いる場合，h3,h4,...と空いているまで関数によってその場

所をみつけていく．

•これにより，データがバラバラに配置されてクラスターを

避ける

•この方法では,ハッシュ関数の計算の手間が増えて効率

が悪くなる

チェイン法と開放番地法の比較

•開放番地法

–衝突が起ったときに，ハッシュテーブル内の別の場所に格納して

いく

→扱えるデータの総数はハッシュテーブルの大きさに制限され

る（欠点）

–データの削除では，単純にその場所の印を未使用にしてしまうと，

探索の時にその場所で止まってしまう．

→そこで，新たな印として，削除済ということを表す印を加え,

（使用中，未使用，削除済）の3種類の印を用いると，削除済とい

うのは探索に関しては，使用中と同じことになる．削除が多くなる

と，ハッシュテーブルに無駄な部分が増えて，効率が悪くなる（欠

点）

•チェイン法

–大きな欠点は無い

–線形リストを使うため若干メモリ使用量が増える

チェイン法のハッシュ関数

•ハッシュ関数は，キー値を，一様に分散させるようなものが望

ましい

ハッシュテーブルの大きさがmである場合：

–チェイン法の効率をあげるには，データをm本のリストにできるだけ均

等に振り分けて，個々のリストをできるだけ短くすることが必要

•キーの値に対して，できるだけランダムな値を返すハッシュ関

数が望ましい

•ハッシュ関数の作り方は，キーの種類，とりうる値の範囲に影

響される

•任意のデータに対して常に一様なばらつきを持ったハッシュ

関数を作ることは不可能

チェイン法のハッシュ関数

•キー値が正の整数の場合：

–キーの値をmで割った余りをハッシュ関数とする

–キー値は0～m-1の範囲の整数に分けられる

–同じハッシュ値となるのは，mの倍数だけ離れた値を持つキー

•ハッシュ関数をできるだけランダムなものにするためには，

キーの全てのビットの値が結果に影響することが望まし

い

–mの大きさは，素数をとるのが良いとされる

–m = 2のK乗とすると，最下位kビットのみでハッシュ値が決まる．

データ自体の傾向やハッシュ関数の癖が強調されてばらつきが

悪くなってしまうようと言われる

•キーが文字列の時：

–何らかの方法で文字列を整数値に変換して，それをmで割った

余りをとるようにすることができる

ハッシュ法の欠点

•ハッシュ関数をうまく作って，ハッシュテーブルのサイズmを

十分大きくとれば，探索,その他の操作は高速になる

•対象とするデータの数があらかじめ分かってないと，表の大

きさmを決めるのは難しい

–あまりmを大きくとると記憶域の無駄が大きくなってしまう

•表の中のデータの順序がでたらめになるので，表の中の値

を大きさの順に取り出す場合は，新たに整列を行う必要が

ある．

–このような場合，整列を必要としない2分探索木などと比べて劣って

いる

サンプルプログラム

#include<stdio.h>

#include<stdlib.h>

struct RECOAD{ /*レコードを構造体で定義*/

char *value; /*レコードの中身*/

struct RECOAD *next; /*次のレコードを指すポインタ*/

}

main(){

struct RECOAD *table[10];

int i;

char in[20];

for (i=0;i<10;i++)table[i]=NULL; /*テーブルを初期化*/

for (i=0;i<100;i++){

printf("Input Word (end: %%%%%%) :"); /*語を入力*/

scanf("%s",in);

if (strcmp(in,"%%%")==0)break;

else Chain(in,table); /*チェイン法で挿入*/

}

while (1){

printf("Search Word (end: %%%%%%) :"); /*探す語を入力*/

scanf("%s",in);

if (strcmp(in,"%%%")==0)break;

else Search(in,table); /*探索*/

}

Chain(char *in,int *table){

int k,h;

char *in2;

struct RECOAD *rec;

rec=malloc(sizeof(rec)); /*レコードを作製*/

in2=malloc(20);

strcpy(in2,in); /*文字列を格納する領域を作成*/

rec->value=in2;

h=0;

for (k=0;k<20;k++){ /*ハッシュ値を計算(h=0,1,2,...,9)*/

if (in[k]==NULL)break;

h=h+in[k];

}

h=h % 10;

rec->next=table[h]; /*レコード挿入*/

table[h]=rec;

}

Search(char *in,int *table){

struct RECOAD *rec;

int k,h;

h=0;

for (k=0;k<20;k++){ /*ハッシュ値を計算(h=0,1,2,...,9)*/

if (in[k]==NULL)break;

h=h+in[k];

}

h=h % 10;

rec=table[h];

while (1){

if (rec==NULL){

printf ("Not Found %s\n",in);

break;

}

if (strcmp(rec->value,in)==0){

printf ("Found %s\n",in);

break;

}

rec=rec->next; /*次のレコード参照*/

}