プログラミング応用演習

第7回 ハッシュ表

2020.05.28

今日のお題

ハッシュ表

2020.05.28

Hash Table

ハッシュ表の概要

⚫ 鍵と値の組をたくさん記憶したいときに使う

◆たとえば問4,5,6における単語が鍵、行番号が値

⚫ 鍵から計算されるハッシュ値を添え字とする配列に鍵と値の組を格納する

◆鍵も格納しなければいけないのは、後に述べる衝突の対策に必要だから

◆この配列の要素にはデータ（鍵と値の組）が入っていないこともある

⚫ 衝突がなければ線形探索や二分探索のように探す必要がない

◆ハッシュ値を計算して配列を参照するだけ

◆データ数Nに対してO(1)

1 < log N < N なので速いはず 2020.05.28

ハッシュ値を計算する手間はデータ数には依存しない

この配列を「ハッシュ表」と呼ぶ

key value

2020.05.28

問4は問2の逆の動作？

問2：行番号から単語を調べる

…単語を配列に入れて、行番号から添字を計算する

問4：単語から行番号を調べる

…行番号を配列に入れて、単語から添字を計算する(?)

配列の添字は非負整数なので、単純にはうまくいかない

➡ 単語から添字を計算するのは、実はハッシュの考え方

線形探索や二分探索は、入力単語と同じ単語を配列の中から探すプログラム

⚫ ハッシュでは衝突の対策としてのみ探す

ハッシュ表のプログラム上の表現

ハッシュ表を配列で表す

⚫ ハッシュ値を添え字とするので…

◆ハッシュ値は添え字の範囲に収まる値でなければならない

⚫ 配列の要素として、データが無いことを示す値を用意しておく必要がある

◆検索したデータが登録されていないことを判別するため

2020.05.28

ハッシュ値の計算

鍵 k に対して、そのハッシュ値 hash(k) を計算する関数 hash をハッシュ関数と呼ぶ。

ハッシュ関数ではどのような計算をするのか：⚫ 同じ鍵に対しては、同じハッシュ値を返さなければならない

⚫ 違う鍵に対しては、できるだけ違うハッシュ値を返すことが望ましい

◆違う鍵から同じハッシュ値が得られても問題が起きないようにしておく必要がある

⚫ 上記を満たせば、どんな計算でもよい

◆ 計算の手間が少ないことが望ましい

2020.05.28

情報セキュリティで使う「ハッシュ」だと、「できるだけ」の部分がもっと厳密。

ハッシュ関数実装上の注意点

ハッシュ値を配列の添字にするので…→配列の添字として有効な値を返さねばならない

◆負数 や 配列の大きさ以上の値 になってはいけない

→配列の大きさで割った余りを使うことが多い

◆余りなら、0以上 割った数未満 になる（？）

→int で計算する場合、32bit 整数の範囲を超える計算をしてしまう可能性を考慮する：

正の数だけを加えても、231以上になると負の数になる…負数の剰余は負になる

…簡単な解決法の一つは、unsigned int を使うこと

2020.05.280以上232未満の(非負の)整数を表す型

単純なハッシュ関数の例

例）文字列のハッシュ値を計算したい

⚫ 各文字の（文字コードの）合計

"abc" … 97,98,99 の和で294

… "abc" と "cba" は同じハッシュ値になる

⚫ 各文字の文字コードにそれぞれ適当な数を掛けて合計

"abc" … 97×1+98×2+99×3 で590

… 単なる和よりはマシ。

⚫ 文字列のポインタ値

同じ文字列が異なるハッシュ値になりうる

2020.05.28

単純なハッシュ関数の実装例

#define HASHTABLESIZE 1000003

unsinged int hash(unsigned char *s) {

unsigned int h=0,i;

for(i=1 ; *s ; i++) {

h += *s * i;

s++;

}

return h % HASHTABLESIZE;

}

2020.05.28

文字列 s の各文字の文字コードに1,2,3,... を順に掛けて合計する。

より複雑なハッシュ関数を考えることもできるが、ハッシュ関数は何度も呼び出されることが前提となるので、できるだけ軽い（手間が少ない）計算が望ましい。

手間の少ない計算で、ハッシュ関数の要件を満たす方法を考えるのが工夫のしどころ。

このハッシュ関数は、あまり性能が良くない（よく衝突する）。課題では、工夫してください。

ハッシュの衝突

異なる鍵 x と y について、ハッシュ値が同じである場合、これを「ハッシュの衝突」と呼ぶ。

⚫ ハッシュ表は配列なので、同じ添え字に対して、格納できる値は一つだけ

2020.05.28

衝突の対策 1：オープンハッシュ

データ（k,v）を登録するとき：⚫ ハッシュ表の hash(k) の位置以降の空いている

ところに（k,v）を登録する

鍵kに対応する値vを検索するとき：⚫ ハッシュ表の hash(k) の位置から、順にkを探す

※どちらのときも、最後のエントリの次は最初のエントリ

2020.05.28

衝突の対策 2：チェイン法

同じハッシュ値を持つデータをリストにする。⚫ ハッシュ表は各リストの先頭を指すポインタの配列

2020.05.28

ハッシュ値に対応するデータが無いこともある

衝突がなければ、リストの長さは１

衝突している場合は連結リストにつなぐ。

ハッシュ表は、セルへのポインタの配列。添え字 は ハッシュ値 に等しい

2020.05.28

二つのハッシュ表の構成(衝突対策)の比較

ハッシュ表に対象のデータが存在しないとき⚫ オープンハッシュでは、データの入っていないエントリが

あれば、検出できる

◆ハッシュ表がすべて埋まっている場合には、表全体を検査しないと、データの非在を検出できない

⚫ チェイン法では、リストの終端を見つけることで、データの非在を検出できる

ハッシュ表の大きさ⚫ オープンハッシュでは、データ数以上の大きさの配列が必要

⚫ チェイン法では、リストの先頭を格納する配列があれば良いので、データ数未満の大きさでも（遅いだけで）動く

ハッシュ表の大きさ

大きいほど衝突が減る（はず）

⚫ ただし、ハッシュ関数の値域がハッシュ表(配列)の添え字全体となっていないと、大きくする意味がない

大きいことのデメリット：

⚫ メモリ使用量が増える（空のエントリが増える）

◆空のエントリのメモリ使用量を減らすためにもポインタを利用する方がよい

2020.05.28

ハッシュ関数の性能を実験的に調べる

先ほど例に挙げたハッシュ関数→の性能を調べてみる：

2020.05.28

int main(int argc, char **argv) {

FILE *fp;

char str[25];

char *p;

if ((fp=fopen(argv[1],"r")) == NULL) {

fprintf(stderr,"cannot open\n");

return 1;

}

while(fgets(str,25,fp) != NULL) {

for(p=str ; *p ; p++) {

if (*p == '\n') { *p=0; break; }

}

printf("%d\n",hash(str));

}

fclose(fp);

return 0;

}

こんなmain関数を書いて、辞書ファイルの各単語に対して

どんなハッシュ値が計算されるかを観察してみよう

改行文字とヌル文字を含めて25byte格納

できるように用意する

#define HASHTABLESIZE 1000003

unsinged int hash(unsigned char *s) {

unsigned int h=0,i;

for(i=1 ; *s ; i++) {

h += *s * i;

s++;

}

return h % HASHTABLESIZE;

}

実行例：ハッシュ関数の性能

2020.05.28

動画

参考：昨年の情報処理演習Ⅰの資料第12回あたりhttp://sun.ac.jp/prof/yamagu/2019IPP1/

出席確認演習

文字列に対するハッシュ関数の定義をいろいろ変えて、前ページでやったように衝突の様子を調べなさい。

自分で書き換えた中で、衝突が少ないと思われるハッシュ関数の定義（ソースコード）を一つ提出しなさい。

提出方法：Google Classroom から提出

提出期限：06/01 10:302020.05.28

2020.05.28

ハッシュ表の応用例

メモ化同じ入力や引数に対する計算を繰り返さずに、前回の計算結果を返すことで高速化する。

… 関数の引数から返戻値を索くハッシュ表を用意する。

関数の入り口で、ハッシュ表を参照し、値があれば、それを返す。なければ、関数の計算を通常通り行い、計算結果をハッシュ表に登録する。

連想配列プログラミング言語の中には、文字列などを配列の添え字にできるものもある。こうした配列はプログラミング言語処理系の内部ではハッシュ表として作られている。

問8 単語の検索５

問5または6のプログラムをもとに、ハッシュ表を使って単語が格納されている行の番号を出力するプログラムを書いてみよう。

標準入力が閉じるまで、単語の入力（と行番号の出力）を繰り返すこと。

※）衝突の対策は、オープンハッシュでもチェイン法でも、どちらでもよい

2020.05.28

問7や問8の実行時間計測データ

$ time ./a.out words < toi5-all.prb >/dev/null

では、約10万単語の辞書から約17万回の検索を行う時間を計測する。

…最近の計算機は高速なので、まっとうにプログラムが書けていれば、すぐに実行が終わるので時間計測が困難。

そこで、たとえば、入力を増やす工夫をする：

$ cat toi5-all.prb toi5-all.prb > toi5-all2.prb

toi5-all.prbを2回繰り返した入力ファイルを用意できる

同様に、toi5-all.ansを2回繰り返したファイルを用意すればdiffでの検証もできる。

2020.05.28

2020.05.28

課題（ひとつめ）標準入力から与えられた文字列が、辞書ファイルの何行目にあるかを出力するプログラムを、線形探索・二分探索・ハッシュ表の3つの方法で実装し、比較しなさい。

⚫ 辞書ファイルはコマンドラインから指定できるようにすること。

⚫ 文字列の入力（と行番号の出力）は標準入力が閉じるまで繰り返すこと。

⚫ 実行結果の検証を行うこと（toi5.tgz が使える）。

⚫ 性能(実行時間)やコード量など、さまざな視点で比較すること。

各プログラムの実行結果の検証報告・比較した内容・結論をまとめたレポートを書き、全てのソースコードを付録につけて提出しなさい。

⚫ 方法の説明・プログラムの説明は書かなくて良い

⚫ 授業名・学籍番号・氏名・提出月日を書いた表紙をつける

提出方法：Google Classroomからpdfファイルを提出

提出締切：2020年6月11日10:30

問5 問7

問8

課題に向けた演習の時間

問4～問8は、課題に直結

⚫ 問6は、ハッシュの衝突対策（チェイン法）に

（部分的に）利用できる

⚫ 問7は二分探索, 問8はハッシュ表

2020.05.28