ソフトウエア基礎
データを検索する場合に、通常は線形探索や二分探索を行なう。 これらはデータ数が増えれば増えるほど検索時間がかかるようになる。 ところがハッシュという仕組みを使えば、 (理想的な場合)データ数に関係なく同じ時間で検索できるようになる。 この利点からハッシュは多くの実用的なプログラムで使用されている。
まず一番簡単な検索時間一定の方法を考えてみよう。 検索時間を一定にするには、 データが存在するかどうかを格納する配列を用意すれば良い。 例えば、a[i]が1ならiというデータが存在、0なら存在しないものとする。 以下のプログラムはこれを実現したものである。
public class SimpleArray {
int a[] = new int[1000];
public static void main(String args[]) {
// SimpleArrayオブジェクトを生成してrun()を実行する
SimpleArray s = new SimpleArray();
s.run();
}
public void run() {
// 配列をクリア(全部0)
for(int i = 0; i < a.length; i++) {
a[i] = 0;
}
a[102] = 1; // 102というデータを登録する
a[253] = 1; // 253というデータを登録する
print_exist(100); // 100というデータは存在するか?
print_exist(102); // 102というデータは存在するか?
print_exist(253); // 253というデータは存在するか?
print_exist(254); // 254というデータは存在するか?
}
void print_exist(int key) {
if (a[key] == 0) {
System.out.println(key + "は存在しません");
} else {
System.out.println(key + "は存在します");
}
}
}
この方法ならaという配列の要素を1つ見れば、 データが存在するかどうか即座に分かる。 存在するデータが増えても検索時間は変わらない。 しかし、データの値は0〜999に限られる。
この方法で、もしJavaの整数型(int)で表現できる値を網羅しようとすれば、 int は32bitなので、2の32乗の大きさの配列が必要となる。仮にデータが 存在するかしないかを1bitで表現したとしても、2^32/8 = 2^32/2^3 = 2^29 = 2^(10*2+9) = 512MBytes 必要となる。これでは全く実用にならない。
そこでこの配列の範囲を小さく圧縮できないか考える。 これがハッシュ法(hashing)である。
配列の範囲を小さくするには、ハッシュ関数というものを使う。 例えば、Javaのintの場合、データの値をxとすれば、x mod 1000 (xを1000で割った余り)というハッシュ関数を使う。この場合、 例えば、xが10456の場合、ハッシュ関数を通すと456となる。 ハッシュ関数を通した値をハッシュ値(hash code)という。 この場合、ハッシュ値は0〜999の範囲に収まる。 さきほどは512MBytesも必要だったのが、たった1000個の要素で済むようになった。 ちなみに、このハッシュを使った配列をハッシュ表(hash table)と呼ぶ。
// [[[注意]]] このプログラムには誤りがあります
public class SimpleHash1 {
final int size = 1000;
int a[] = new int[size];
public static void main(String args[]) {
SimpleHash1 s = new SimpleHash1();
s.run();
}
public void run() {
// 配列をクリア(全部0)
for(int i = 0; i < a.length; i++) {
a[i] = 0;
}
a[hash(530102)] = 1; // 530102というデータを登録する
a[hash(345253)] = 1; // 345253というデータを登録する
print_exist(530100); // 530100というデータは存在するか?
print_exist(530102); // 530102というデータは存在するか?
print_exist(345253); // 345253というデータは存在するか?
print_exist(345254); // 345254というデータは存在するか?
}
int hash(int key) {
return key % size;
}
void print_exist(int key) {
int hashcode = hash(key);
if (a[hashcode] == 0) {
System.out.println(key + "は存在しません");
} else {
System.out.println(key + "は存在します");
}
}
}
ハッシュ法では、元々表現できる範囲が広いデータ値を、 ハッシュ関数を通すことで範囲を狭めている。 範囲が狭くなるため、違うデータ値が同じハッシュ値を持つことがある。 この状態を衝突(collision)、 あるいはシノニム(synonym)が発生しているという。
上記の例では、シノニムを考慮していないので、誤った処理をする可能性がある。 例えば、データがハッシュ表に登録されていないのに、たまたまハッシュ値が同じ データを登録していたため、登録されていると判断されてしまう。 また、ハッシュ表にデータ自体を登録している場合は、 ハッシュ表に前に登録していたデータを同じハッシュ値の違うデータが上書きしてしまい、 前に登録されたデータが消されてしまう。
工夫するとシノニムが発生してもうまく処理することができる。 その方法の一つ、オープンアドレス法(開番地法)を次回紹介する。
上記ではint型のデータでハッシュを使うことを考えたが、 プログラムで扱えるデータであれば何でもハッシュで扱うことができる。
例えば文字列を扱うことを考える。 一番簡単なのは、文字列の1文字ごとの文字コードを加算するハッシュ関数である。 つまり、"ABC"という文字列の場合、'A'=65,'B'=66,'C'=67(ASCIIコード)なので、 65+66+67=198 となる。 これをハッシュ表の大きさで割って余りを求めハッシュ値とする。 例えば、ハッシュ表の大きさが100の場合は、198 mod 100 = 98 となる。
以上の方法によるハッシュ関数のプログラムを示す。
int hash(String key) {
int v = 0;
for (int i = 0; i < key.length(); i++) {
v += key.charAt(i);
}
return v % size;
}
しかし、以上の方法では同じハッシュ値、つまりシノニムが発生しやすい。 例えば、ABC,CBA,BBB,BCA,CAB などは同じハッシュ値になる。
そこで各文字ごとの値が重ならないように、文字コードの範囲でずらして 加算する。例えば、文字をASCIIコードに限定した場合、 文字コードは0〜127の値をとるため、"ABC"という文字列の場合、 (65+66*128+67*128*128) mod 100 = (1106241) mod 100 = 41 となる。こうすれば、シノニムの発生を大幅に減らせる。
上のプログラム(SimpleArray.java)でintの配列を使う代りにbooleanの配列を使 うように書き変えよ。この場合、booleanを使うほうが素直である。
上のプログラム(SimpleHash1.java)でハッシュ表に登録する処理をメソッドとして 定義せよ。メソッドは、void set(int value)という形式にせよ。
課題hash-2を修正し、標準出力にデータ値とハッシュ値を表示するようにせよ。 例えば、530102 -> 102という形で表示すればよい。 ※ hashメソッドに手を加えれば良い。
削除(欠番)
課題hash-3を修正し、データが存在しない(ハッシュ表に登録されていない)のに、 存在するという結果になる例を示せ(そのようなデータの値を考えよ)。
上記の「文字列データのハッシュ関数」にある hashメソッドを利用して、 文字列データを扱うハッシュ法のプログラムを作成せよ。なお、 シノニムを考慮する必要はない。
課題hash-6で作成したプログラムを使って、データ(文字列)が存在しない (ハッシュ表に登録されていない)のに存在するという結果になる例を示せ。
「文字列データを扱うハッシュ法」で説明した 「文字ごとにずらして加算する」ハッシュ関数で、"ABC","CBA","BBB","CAB" のそれぞれのハッシュ値がいくつになるか答えよ。 なお、文字コードはASCIIコード(0〜127)に限定し、ハッシュ表の大きさ(要素数)は100とする。
「文字列データを扱うハッシュ法」で説明した、 「文字ごとにずらして加算する」ハッシュ関数を使ったプログラムを作成せよ。 なお、文字コードはASCIIコード(0〜127)に限定せよ。 hashメソッドを修正することになる。
ソフトウエア基礎
ohmi@rsch.tuis.ac.jp