ソフトウエア基礎
ここでは、ハッシュにおけるシノニムを扱うためにオープンアドレス法を 使ったアルゴリズムを学ぶ。その準備として、ハッシュ法(1)のプログラム を以下のように修正する。
// [[[注意]]] このプログラムにはシノニムを考慮していません
public class Hash3 {
final int size = 10;
String hashtable[] = new String[size];
public static void main(String args[]) {
Hash3 s = new Hash3();
s.run();
}
public void run() {
// ハッシュ表をクリア(全部null)
for(int i = 0; i < hashtable.length; i++) {
hashtable[i] = null;
}
set("abc"); // "abc"というデータを登録する
set("xyz"); // "xyz"というデータを登録する
set("yyy"); // "yyy"というデータを登録する
dump_hashtable(); // ハッシュ表の内容を表示する
print_exist("abc"); // "abc"というデータは存在するか?
print_exist("bbb"); // "bbb"というデータは存在するか?
print_exist("xyz"); // "xyz"というデータは存在するか?
print_exist("yyy"); // "yyy"というデータは存在するか?
print_exist("vxyz"); // "vxyz"というデータは存在するか?
}
int hash(String key) {
int s = 0;
for (int i = 0; i < key.length(); i++) {
s += key.charAt(i);
}
return s % size;
}
void set(String key) {
hashtable[hash(key)] = key;
}
void print_exist(String key) {
int hashcode = hash(key);
if (hashtable[hashcode] == key) {
System.out.println(key + "は存在します");
} else {
System.out.println(key + "は存在しません");
}
}
void dump_hashtable() {
for (int i = 0; i < hashtable.length; i++) {
System.out.print(i + ":");
if (hashtable[i] == null) {
System.out.println();
} else {
System.out.println(hashtable[i]);
}
}
}
}
修正点は以下の通りである。
以上の例では、ハッシュ表に格納されたデータと探索したいキーを比較して 一致すれば見つかった、一致しなければ見つからなかったとしている。 ハッシュ表には、"xyz"と"yyy"というデータを格納しようとしているが、 これらのハッシュ値は同じ(3)でありシノニムが発生する。まず最初に、 ハッシュ表の3番の要素に"xyz"が登録される。しかし、その直後、同じ 場所に"yyy"が登録され、"xyz"は消えてしまう。このため、"xyz"という データは存在しない、"yyy"というデータは存在するという誤った結果と なる。これを図解すると以下のようになる。
(1)ハッシュ表に"xyz"を登録 ... 2: 3: "xyz" ← 3番目に登録 4: ... (2)ハッシュ表に"yyy"を登録 ... 2: 3: "yyy" ← 3番目に登録。"xyz"は消えてしまう 4: ... (3)"xyz"が存在するかどうか調べる ... 2: 3: "yyy" ← 3番目は"xyz"ではないので存在しない(誤り) 4: ... (4)"yyy"が存在するかどうか調べる ... 2: 3: "yyy" ← 3番目は"yyy"ではないので存在する 4: ...
オープンアドレス法は、 ハッシュ表(配列)のみを使ってデータを格納する方法である。 ここでは、オープンアドレス法の中で、一番簡単な線形走査法を学ぶ。
データをハッシュ表に登録する場合は、 まずハッシュ関数を使いハッシュ値を求め、ハッシュ表の中の対応する場所を見る。 そこが空ならデータを格納する。既にデータが格納されていたら、 その1つ下に移動する。そして、空いている場所を見つけるまで移動し、 空いている場所に格納する。
上記の例では、空いている場所はnullで、 既にデータが格納されている場合はそれ以外の値となる。
これを実現したsetメソッドを以下に示す。
void set(String key) {
int hashcode = hash(key); // ハッシュ表中の位置(ハッシュ値)を求める
while(hashtable[hashcode] != null) { // その場所が空でなければ
hashcode++; // 1つ下に移動する
}
hashtable[hashcode] = key; // ハッシュ表にデータを格納する
}
[解説] まずハッシュ値を求めhashcodeに代入する。 そしてハッシュ表中の要素(hashtable[hashcode])が空(null)でない、 つまり既にデータが入っている場合は、hashcodeに1を加え、1つ下に移動する。 これを空の場所が見つかるまで繰り返す。空の場所が見つかったら、 そこにデータを格納する。
以上のプログラムでは、ハッシュ表の一番下に達した場合の考慮をしていない。 これは1つ加算する場合に、加算した結果をハッシュ表の大きさで割った余りを 求めれば良い。そのような場合、ハッシュ表の大きさで丸めるという。
データを探索する場合は、 ハッシュ値から求めた場所に探したいデータがあるとは限らない。 1つずつ下に移動してデータを探す必要が出てくる。 途中で空(null)に出会った場合は、データは格納されていないことが分かる。 これを実現したprint_existメソッドを以下に示す。
void print_exist(String key) {
int hashcode = hash(key); // ハッシュ表中の位置(ハッシュ値)を求める
while(hashtable[hashcode] != null) { // その位置が空でなければ
if (hashtable[hashcode] == key) { // キーと一致するかどうか
System.out.println(key + "は存在します");
return;
}
hashcode++; // 一致しなければ1つ下に移動する
}
// 空に出会った場合は存在しない
System.out.println(key + "は存在しません");
}
[解説] 基本的には、データの格納と似た動作をする。 まずハッシュ値を求めhashcodeに代入する。 そしてハッシュ表中の要素(hashtable[hashcode])が空(null)でない、 つまり既にデータが入っている場合は、そのデータをキーを比較する。 一致すれば見つかったと表示し、returnでメソッドを終える。 一致しなければ、hashcodeに1を加え、1つ下に移動する。 これを空の場所が見つかるまで繰り返す。空の場所が見つかったら、 探しているデータは見つからなかったと表示し終了する。
オープンアドレス法はハッシュ表に直接データを格納するため、 最大でもハッシュ表の要素数しかデータを格納できない。 また、一般にハッシュ値は似通った値に集中することが多く、その辺りが かたまり状になってしまう。このかたまりをクラスターと言う。 クラスターが発生すると、格納する場所を下にずらすことが多くなり、 効率がかなり悪くなる。このため、クラスターが起こりにくい、つまりハッシュ 値が分散しやすいハッシュ関数が望ましい
また、限界に近い数のデータを格納すると極端に効率が悪くなる。 このため、格納するデータ数を見積もっておき、 ハッシュ表の大きさに余裕を持つべきである。 しかし、あまり大きずぎてもメモリの無駄遣いとなる。 ハッシュ表の大きさを決めることには、一筋縄ではいかない難しい面がある。
上のプログラム(Hash3.java)でprint_existメソッドを呼んだ場合に、 ハッシュ表の要素が、nullの場合「データが存在しない」、 null以外の場合「データが存在する」 という処理を行なうように修正せよ。このように修正した場合、誤った結果 となっているところを指摘せよ。
上の「データの登録」で示しているsetメソッドを使ってみよ。 ハッシュ表にどのようにデータが格納されたか説明せよ。 また、データの探索については、まだそのままであるが、 どのような結果になったか説明せよ。
課題hash-11で、set("mag"); set("mbf"); を実行した場合にどのような動作をおこすか説明せよ。
課題hash-11を修正し、hashcodeがハッシュ表の一番下に到達した場合に、一番上 に移動するように、hashcodeをハッシュ表の大きさで丸めるようにせよ。
課題hash-11を修正し、 上の「データの探索」で示したprint_existメソッドを使ってみよ。 正しく動作しているかどうか報告せよ。
課題hash-13に課題hash-14を反映させ、「データの探索」においても hashcodeがハッシュ表の一番下に到達した場合に、一番上に移動するように、 hashcodeをハッシュ表の大きさで丸めるようにせよ。
上記のプログラムでは、ハッシュ表が満杯になった時に無限ループに
陥いってしまう。これは終了条件が空(null)の要素が見つかるまでと
しているためである。プログラムを修正し、ハッシュ表を一周したら、
「登録できません」とエラー表示するようにせよ。
ヒント:最初のハッシュ値に戻ったらエラーとすれば良い
ソフトウエア基礎
ohmi@rsch.tuis.ac.jp