ソフトウエア基礎

ハッシュ法(1) 解答例

課題hash-1

public class SimpleArrayBoolean {
    boolean a[] = new boolean[1000];
    public static void main(String args[]) {
	// SimpleArrayBooleanオブジェクトを生成してrun()を実行する
	SimpleArrayBoolean s = new SimpleArrayBoolean();
	s.run();
    }

    public void run() {
	// 配列をクリア(全部false)
	for(int i = 0; i < a.length; i++) {
	    a[i] = false;
	}
	
	a[102] = true; // 102というデータを登録する
	a[253] = true; // 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] == false) {
	    System.out.println(key + "は存在しません");
	} else {
	    System.out.println(key + "は存在します");
	}
    }
}

if (a[key] == false) {の部分は、 if (!a[key]) {と書いても良い。あるいは、 if で実行する部分と elseで実行する部分を逆転させて、 if (a[key]) {と書いても良い。

課題hash-2

// [[[注意]]] このプログラムにはシノニムを考慮していません
public class SimpleHash1_2 {
    final int size = 1000;
    int a[] = new int[size];
    public static void main(String args[]) {
	SimpleHash1_2 s = new SimpleHash1_2();
	s.run();
    }

    public void run() {
	// 配列をクリア(全部0)
	for(int i = 0; i < a.length; i++) {
	    a[i] = 0;
	}
	
	set(530102); // 530102というデータを登録する
	set(345253); // 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 set(int value) {
	a[hash(value)] = 1;
    }

    void print_exist(int key) {
	int hashcode = hash(key);
	if (a[hashcode] == 0) {
	    System.out.println(key + "は存在しません");
	} else {
	    System.out.println(key + "は存在します");
	}
    }
}

課題hash-3

hashメソッドを以下のように書き変える。

    int hash(int key) {
        int value = key % size;
	System.out.println(key + "->" + value);
	return value;
    }

課題hash-4

削除(欠番)

課題hash-5

例えば、runメソッドの最後にprint_exist(111102); と記述する。111102はハッシュ表に登録していないにもかかわらず、 見つかった(存在する)という結果が出る。これは、111102のハッシュ値が 登録されている530102のハッシュ値と等しいためである。

課題hash-6

// [[[注意]]] このプログラムはシノニムを考慮していません
public class StringHash1 {
    final int size = 1000;
    int a[] = new int[size];
    public static void main(String args[]) {
	StringHash1 s = new StringHash1();
	s.run();
    }

    public void run() {
	// 配列をクリア(全部0)
	for(int i = 0; i < a.length; i++) {
	    a[i] = 0;
	}
	
	set("ABC"); // "ABC"というデータを登録する
	set("XYZ"); // "XYZ"というデータを登録する

	print_exist("AAA"); // "AAA"というデータは存在するか?
	print_exist("ABC"); // "ABC"というデータは存在するか?
	print_exist("XYZ"); // "XYZ"というデータは存在するか?
	print_exist("ZZZ"); // "ZZZ"というデータは存在するか?
    }

    int hash(String key) {
        int v = 0;
	for (int i = 0; i < key.length(); i++) {
	    v += key.charAt(i);
	}
	return v % size;
    }

    void set(String value) {
	a[hash(value)] = 1;
    }

    void print_exist(String key) {
	int hashcode = hash(key);
	if (a[hashcode] == 0) {
	    System.out.println(key + "は存在しません");
	} else {
	    System.out.println(key + "は存在します");
	}
    }
}

課題hash-7

例えば、runメソッドの最後にprint_exist("YYY"); と記述する。"YYY"はハッシュ表に登録していないにもかかわらず、 見つかった(存在する)という結果が出る。これは、"YYY"のハッシュ値が 登録されている"XXX"のハッシュ値と等しいからである。

課題hash-8

課題hash-9のプログラムを作成し、 hashメソッド内で戻り値の値を表示するようにすると容易に求まる。 "ABC"は41,"CBA"は75,"BBB"は58,"CAB"は31となる。

課題hash-9

hashメソッドを以下のように書き変えればよい。

    int hash(String key) {
        int v = 0;
	int m = 1;
	for (int i = 0; i < key.length(); i++) {
	    v += key.charAt(i)*m;
	    m *= 128;
	}
	return v % size;
    }

ソフトウエア基礎