ソフトウエア基礎

ハッシュ法(2) 解答例

課題hash-10

print_existメソッドの中の、 if (hashtable[hashcode] == key) { を、 if (hashtable[hashcode] != null) { に書き変える。

以上のように修正したプログラムを実行すると、 ハッシュ表に登録していないはずの "bbb" が存在すると表示された。 これは、登録されている"abc"とハッシュ値が同じであり、そこが nullではないため存在するという誤った表示がされた。

課題hash-11

ハッシュ表の内容は以下のようになった。

0:
1:
2:
3:xyz
4:abc
5:yyy
6:
7:
8:
9:

"abc"と、"xyz"は本来のハッシュ値の場所に格納された。 "yyy"は、既に登録されたデータがあるため下に移動し、5番に格納された。

データの探索は、本来のハッシュ値の場所しか見ないため、 "abc"と"xyz"は「存在する」と正しく表示されるか、 "yyy"については、「存在しない」と誤った結果となる。

課題hash-12

実行すると、 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException と表示され、プログラムが途中で異常終了した。 配列 hashtable の範囲を超えて、添字10にアクセスしようとして、 ArrayIndexOutOfBoundsExceptionという例外が発生して、プログラムが終了した。

課題hash-13

setメソッドを以下のように記述する

    void set(String key) {
	int hashcode = hash(key); // ハッシュ表中の位置(ハッシュ値)を求める
	while(hashtable[hashcode] != null) { // その場所が空でなければ
	    hashcode = (hashcode+1)%size;
	}
	hashtable[hashcode] = key; // ハッシュ表にデータを格納する
    }

少々長くなるが、以下でも良い。

    void set(String key) {
	int hashcode = hash(key); // ハッシュ表中の位置(ハッシュ値)を求める
	while(hashtable[hashcode] != null) { // その場所が空でなければ
	    hashcode++;
	    if (hashcode >= size) {
	        hashcode = 0;
            }
	}
	hashtable[hashcode] = key; // ハッシュ表にデータを格納する
    }

課題hash-14

実行すると以下のような出力が得られた。

1:
2:
3:xyz
4:abc
5:yyy
6:
7:
8:
9:
abcは存在します
bbbは存在しません
xyzは存在します
yyyは存在します
vxyzは存在しません

登録されているabc,xyz,yyyは存在する、 登録されていないbbb,vxyzは存在しないという正しい結果が出た。

課題hash-15

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 = (hashcode+1)%size;
	}
	System.out.println(key + "は存在しません");
    }

課題hash-16

setメソッドを以下のように書く。

    void set(String key) {
	int hashcode = hash(key); // ハッシュ表中の位置(ハッシュ値)を求める
	int initial_code = hashcode;
	while(hashtable[hashcode] != null) { // その場所が空でなければ
	    hashcode = (hashcode+1)%size; // 1つ下に移動する
	    if (hashcode == initial_code) {
		System.out.println("ハッシュが満杯で登録できません。");
		return;
	    }
	}
	hashtable[hashcode] = key; // ハッシュ表にデータを格納する
    }

ソフトウエア基礎