プログラミング演習
II
第
14
回
2018 年 7 月 26 日 今回の目的: • ハッシュ法 課題提出先: proen@mm.ics.saitama-u.ac.jp • メールのタイトルは、第 14 回演習, 学籍番号, 名前とすること。 • 授業時間内に解けなかった問題は、8 月 2 日 12:00 までにメールで提出すること。 • 各課題について、質問がある場合やコメントが欲しい場合には、その旨明記する こと。1
ハッシュ法とは
今回は、整数を格納するためのハッシュ法を扱う。ハッシュ法は、（ある制約下におい て）O(1) の比較回数で検索が可能なデータ構造である。要素数を n としたとき、連結リ ストは O(n)、平衡した二分探索木は O(log n) の比較回数が必要なため、ハッシュ法は非 常に高速な検索が可能である。ハッシュ法はよく文字列に対して用いられるが、ここでは 扱わない。 ハッシュ法は、配列はどの要素でも O(1) で値が分かることに基づいている。ただし、 配列の要素数にはメモリ上の制約があるので、広い範囲の要素を格納するためにはテク ニックが必要になる。 例（32 ビットマシン）: 1G バイトのメモリには int 型整数（4 バイト）が 250 M 個 （2.5 億個）格納できる。int 型整数の最大値は約 21 億だから不足している。2
ハッシュ法の原理
まず、ハッシュ法の原理をみる。 0 以上 100 未満の整数に限定した場合、以下のように配列に入っているか否かの二択 のみで判定できる。 0 以上 100 未満の整数の場合 #include <stdio.h> #define HASHSIZE 100 /* 追加できるデータの上限 */ #define NOTFOUND 0 /* 入っていない場合の戻り値 */ #define FOUND (!NOTFOUND) /* 入っている場合の戻り値 */ #define EMPTY -1 /* 空であることを意味する */void hash1_init(int *array) {
int i;
for (i = 0; i < HASHSIZE; i++)
array[i] = EMPTY; /* i が入っていなければ EMPTY */ }
void hash1_insert(int *array, int n) { if (n < 0 || n >= HASHSIZE) { printf("範囲外の入力です\n"); return; } array[n] = n; }
int hash1_find(int *array, int n) { if (n < 0 || n >= HASHSIZE) return NOTFOUND; if (array[n] == n) return FOUND; return NOTFOUND; } • hash1_insert() はデータを追加する関数、hash1_find() はデータを検索する関 数、hash1_init() は初期化関数である。 • hash1_find() での比較回数は HASHSIZE によらないことに注意。
2.1
課題
1
上の関数をテストしてください。このとき、データがある場合の検索と、ない場合の検 索を行うこと。以下のメイン関数を利用してもよい。〔提出: hash1_insert() で追加し たデータ、hash1_find() で検索したデータとその結果〕メイン関数の例 #include <stdio.h> int main(void) { int hashtable[HASHSIZE]; int data[] = { 9, 77, 35, 43, 96 } ; int n, i; hash1_init(hashtable); n = sizeof(data) / sizeof(data[0]); for (i = 0; i < n; i++) hash1_insert(hashtable, data[i]); printf("Input> "); scanf("%d", &n); if (hash1_find(hashtable, n) != NOTFOUND) { printf(" found\n"); } else {
printf(" not found\n"); } return 0; } • このメイン部は以降の課題でも（修正の上）利用できる。
3
ハッシュ法の原理
(2)
0以上 100 未満の整数に限定すると、利用可能な範囲が非常に狭い。そのため、追加で きるデータの範囲を広げることを考える。その方法として、100 で割った余りが同じデー タを同じ箇所に格納することとする。例えば、15 と 215 は同じ位置に格納する。 0 以上の int 型整数の場合void hash2_init(int *array) {
int i;
for (i = 0; i < HASHSIZE; i++) array[i] = EMPTY;
}
{ if (n < 0) { printf("範囲外の入力です\n"); return; } array[n % HASHSIZE] = n; /* 「HASHSIZE で割った余り」の箇所に n を入れる */ }
int hash2_find(int *array, int n) { if (n < 0) return NOTFOUND; if (array[n % HASHSIZE] == n) return FOUND; return NOTFOUND; } • ここで、f(n) ≡ n % HASHSIZE は「ハッシュ関数」と呼ばれる。
3.1
課題
2
この手法の問題点を指摘してください。また、その問題点を実験結果によって示してく ださい。〔提出: 問題点。問題点が明らかになる入力と結果〕4
衝突の回避
—
クローズドハッシュ
上記の問題点を解決する方法には、2 種類存在する。その内の一つがクローズドハッ シュである。 クローズドハッシュ法void hash3_init(int *array) {
int i;
for (i = 0; i < HASHSIZE; i++) array[i] = EMPTY;
}
void hash3_insert(int *array, int n) {
if (n < 0) {
printf("範囲外の入力です\n"); return;
}
hashval = n % HASHSIZE;
for (i = hashval; i < HASHSIZE; i++) { if (array[i] == EMPTY) {
array[i] = n; return;
} }
for (i = 0; i < hashval; i++) { if (array[i] == EMPTY) { array[i] = n; return; } } printf("配列がすべて埋まっています\n"); }
int hash3_find(int *array, int n) {
int i, hashval;
if (n < 0)
return NOTFOUND;
hashval = n % HASHSIZE;
for (i = hashval; i < HASHSIZE; i++) { if (array[i] == n)
return FOUND; if (array[i] == EMPTY)
return NOTFOUND; }
for (i = 0; i < hashval; i++) { if (array[i] == n) return FOUND; if (array[i] == EMPTY) return NOTFOUND; } return NOTFOUND; }
4.1
課題
3
このコードは、課題 2 で指摘した問題点をどのように解決しているかを述べてくださ い。また、課題 2 で失敗した入力に対して問題が解決していることを実験で示してくだ さい。〔提出: クローズドハッシュが行っている解決策。実験結果〕
• hash3_insert() と hash3_find() にある 2 つの for ループはどのような意図で書
かれたものか（hash2_insert() と hash2_find() のままだとなぜ問題なのか）に 注意して述べてください。
5
衝突の回避
—
オープンハッシュ
課題 2 での問題点の解決として、もうひとつにはオープンハッシュがある。 オープンハッシュ法（の類似手法） #define VECTORSIZE 5 struct vector { int size; int value[VECTORSIZE]; } ;void hash4_init(struct vector *array) {
int i;
for (i = 0; i < HASHSIZE; i++) array[i].size = 0;
}
void hash4_insert(struct vector *array, int n) {
int hashval, size;
if (n < 0) { printf("範囲外の入力です\n"); return; } hashval = n % HASHSIZE; size = array[hashval].size; if (size < VECTORSIZE) { array[hashval].value[size] = n; array[hashval].size++;
return; }
printf("配列がすべて埋まっています\n"); }
int hash4_find(struct vector *array, int n) {
int i, hashval, size;
if (n < 0)
return NOTFOUND;
hashval = n % HASHSIZE; size = array[hashval].size; for (i = 0; i < size; i++) {
if (array[hashval].value[i] == n) return FOUND; } return NOTFOUND; }
6
文字列を格納するハッシュ
6.1
文字コード
C言語では、文字列は char 型の配列として表される。char 型は 1 バイト整数なので、 文字列も整数のペアと同様の方法で整数化できる。表 1 は、ASCII (American Standard Code for Information Interchange) の表である （0x00 から 0x1F と 0x7F は制御文字のため省いた）。文字と 7 ビットの整数が対応付け
文字コードの明示的な使用 #include <stdio.h> int main(void) { char str[8]; str[0] = 5*16+3; str[1] = 6*16+1; str[2] = 6*16+9; str[3] = 7*16+4; str[4] = 6*16+1; str[5] = 6*16+13; str[6] = 6*16+1; str[7] = ’\0’; printf("%s\n", str); return 0; } 上のコードを実行すると、Saitama と表示されるはずである。
6.2
文字列操作関数
C言語では文字列は配列であるため、代入や比較は（整数のように）= や == といった構 文があるわけではない。代わりに、標準関数として string.h に関数が用意されている。 代入関数 (string copy)char *strcpy(char *s, char *t)
比較関数 (string compare)
int strcmp(char *s, char *t)
• strcpy(s, t) と呼ぶと、t の内容を s にコピーする。 • strcmp(s, t) と呼ぶと、s の内容と t の内容が一致するときに 0 を、一致しない ときには 0 以外を返す。
6.3
文字列に対するハッシュ値
先頭の文字だけでもハッシュ値にはなるが、それでは衝突が多発することが予想される （例: 入力データの多くが The から始まる場合）。整数のペア x, y を ax + by に変換する 手法を応用しようとした場合、文字列は長さが一定であるとは限らないため、係数（a や b）を無数に用意しておくなどする必要がある。たとえば、1 文字目の係数は 1 とし、2 文字目の係数は t、3 文字目の係数は t2、4 文字目の係数は t3、…、とすることが考えら れる。 以下では、t = 5 とした。変数 coeff は係数 ti を保持する。ただし、HASHSIZE で割っ た余りにすることでオーバーフローを防止する。ハッシュ値計算
int hashfunc(char *s) {
int hashval = 0, coeff = 1, i;
for (i = 0; s[i] != ’\0’; i++) { hashval += s[i] * coeff;
coeff = (coeff * 5) % HASHSIZE; /* オーバーフロー防止 */ }
return hashval % HASHSIZE; }
6.4
課題
4
hash_find()を適切に作成し、（空文字列以外の）文字列を格納するハッシュを構成す るプログラムを作成してください。〔提出: 作成したコード全て〕 ハッシュ関数は上の関数を利用すること（変更してもよい）。 コード例（一部省略） #define MAXLENGTH 128 struct string { char str[MAXLENGTH]; } ; int main(void) {struct string hashtable[HASHSIZE];
char *data[] = { "Japan", "United Kingdom", "Sweden", "United States", "Brazil", "Egypt" } ; char buffer[MAXLENGTH], *p; int n, i; hash_init(hashtable); n = sizeof(data) / sizeof(data[0]); for (i = 0; i < n; i++) hash_insert(hashtable, data[i]); /* 標準入力（キーボード）から文字列を buffer に読み込む */ printf("Input> ");
fgets(buffer, sizeof(buffer), stdin); if ((p = strrchr(buffer, ’\n’)) != NULL) {
*p = ’\0’; /* 末尾の改行コードを削除 */ }
/* 読み込んだ文字列を検索 */
if (hash_find(hashtable, buffer) != NOTFOUND) { printf(" found\n");
} else {
printf(" not found\n"); }
return 0; }
/* 空文字列で「空」を表すこととする */ #define EMPTY_STRING ""
void hash_init(struct string *array) {
int i;
for (i = 0; i < HASHSIZE; i++)
strcpy(array[i].str, EMPTY_STRING); }
void hash_insert(struct string *array, char *str) { int i, hashval; if (strcmp(str, EMPTY_STRING) == 0) { printf("範囲外の入力です\n"); return; } hashval = hashfunc(str);
for (i = hashval; i < HASHSIZE; i++) {
if (strcmp(array[i].str, EMPTY_STRING) == 0) { strcpy(array[i].str, str);
return; }
}
for (i = 0; i < hashval; i++) {
if (strcmp(array[i].str, EMPTY_STRING) == 0) { strcpy(array[i].str, str);
return; }
}
printf("配列がすべて埋まっています\n"); }
int hash_find(struct string *array, char *str) {
/* hash_insert() を参考に適切に埋めてください */ }
表 1: 文字コード表 (16 進数で表記) 0 1 2 3 4 5 6 7 8 9 A B C D E F 20 ! " # $ % & ’ ( ) * + , - . / 30 0 1 2 3 4 5 6 7 8 9 : ; < = > ? 40 @ A B C D E F G H I J K L M N O 50 P Q R S T U V W X Y Z [ \ ] ^ _ 60 ‘ a b c d e f g h i j k l m n o 70 p q r s t u v w x y z { | } ~
