ソフトウエア基礎
ここでは、オープンアドレス法におけるデータの削除について学ぶ。
オープンアドレス法でハッシュ表に登録されているデータを削除することを考える。 まず、思い付くのはハッシュ表の中のデータを探し出し、 そこを空(null)にすることである。しかし、それではうまくいかない。 空にしてしまうと、そこでデータの探索が終ってしまう。 したがって、削除した後に、別のデータを探索しようとする場合に、 本当はそこより下に登録してあるデータがあっても、 削除した場所で探索を止めてしまい見つからなくなってしまう。
この問題を解消するためには、「削除済」という値を設けると良い。 つまり、ハッシュ表に入る値は次の三種類となる。
※ 他の方法として、 ハッシュ表で削除する場所より下を1つ上に移動することが考えられるが、 本来のハッシュ値より上には移動できないので処理が複雑になり、 処理時間もかかりがちなので良い方法とは言いがたい。
以上のことを考慮したデータ削除のプログラムは以下のようになる。
public class Hash4 {
final int size = 10;
String hashtable[] = new String[size];
String deleted = new String("DELETED");
public static void main(String args[]) {
Hash4 s = new Hash4();
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"というデータを登録する
delete("xyz");
set("bbb");
set("zyx");
dump_hashtable(); // ハッシュ表の内容を表示する
print_exist("abc"); // "abc"というデータは存在するか?
print_exist("bbb"); // "bbb"というデータは存在するか?
print_exist("xyz"); // "xyz"というデータは存在するか?
print_exist("yyy"); // "yyy"というデータは存在するか?
}
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) {
int hashcode = hash(key);
while(hashtable[hashcode] != null && hashtable[hashcode] != deleted) {
hashcode++;
}
hashtable[hashcode] = key;
}
boolean delete(String key) {
int hashcode = hash(key);
while(hashtable[hashcode] != null) {
if (hashtable[hashcode] == key) {
hashtable[hashcode] = deleted;
return true;
}
hashcode++;
}
return false;
}
void print_exist(String key) {
int hashcode = hash(key);
while(hashtable[hashcode] != null) {
if (hashtable[hashcode] == key) {
System.out.println(key + "は存在します");
return;
}
hashcode++;
}
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]);
}
}
}
}
このプログラムでは、 「削除済」として"DELETED"という文字列データを使っている。 String deleted = new String("DELETED");
削除するメソッド delete は以下のようにしている。
boolean delete(String key) {
int hashcode = hash(key);
while(hashtable[hashcode] != null) {
if (hashtable[hashcode] == key) {
hashtable[hashcode] = deleted;
return true;
}
hashcode++;
}
return false;
}
戻り値として trueなら削除成功、falseなら削除失敗としている。 まず、データの探索を行ない、見つかればその場所に deleted変数 の値を代入している。
また、データを登録する set メソッドも若干修正している。
void set(String key) {
int hashcode = hash(key);
while(hashtable[hashcode] != null && hashtable[hashcode] != deleted) {
hashcode++;
}
hashtable[hashcode] = key;
}
while文の条件で、ハッシュ表のデータが空でないことに加え、 deleted(削除済)でもない、という条件になっている。 その条件が成り立つ時とは、通常の文字列データが入っている時である。
また、print_existメソッドは前のままである。 つまり、データを登録する時は、空か削除済の場所を探して登録する、 データを探索する時は、空の場所になるまで探し続ける(削除済の場合は 探し続ける)という違いがある。
なお、このプログラムで "DELETED"という文字列を登録した場合に、 変な動作をするのではないかと思うかもしれない。ところが、 大丈夫である。このプログラムはJava特有のテクニックを使っている。 deletedの値を決める時にnew String("DELETED") としているのがミソである。このため別に"DELETED"という文字列を登録しても、 アドレスが違うため、== や != などの比較演算子を使っても一致しない (Javaではオブジェクトの変数は値でなくポインタである。 ソフトウェア入門の内容を参照)。 このため、「削除済」と後で登録した"DELETED"は区別されるのである。
なお、この方法で削除を繰り返すとハッシュの効率が悪くなってくる。 データ探索の時に、本来比較しても一致しないのが明らかな「削除済」 の値と比較することが多くなり、探索に余計な時間がかかるようになる。 このため、オープンアドレス法によるハッシュでは、 削除することがあまり多くない用途に使用すべきである。
これまでは、1つのデータだけを扱うハッシュを学んだが、 複数のデータを1つにまとめてハッシュで扱うことも多い。 いわゆるレコード型データ構造である。 1つにまとめたものをレコード、あるいは組(tuple)と呼ぶ。
以下にレコード型データを扱うプログラムを示す。
public class Hash5 {
final int size = 10;
HashData hashtable[] = new HashData[size];
public static void main(String args[]) {
Hash5 s = new Hash5();
s.run();
}
public void run() {
// ハッシュ表をクリア(全部null)
for(int i = 0; i < hashtable.length; i++) {
hashtable[i] = null;
}
set("s03881", "情報太郎", 80, 85);
set("s03872", "大学花子", 70, 87);
dump_hashtable(); // ハッシュ表の内容を表示する
print_exist("s03881"); // "abc"というデータは存在するか?
print_exist("s03882"); // "abc"というデータは存在するか?
}
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, String name, int math, int english) {
int hashcode = hash(key);
HashData d = new HashData();
d.key = key;
d.name = name;
d.math = math;
d.english = english;
while(hashtable[hashcode] != null) {
hashcode++;
}
hashtable[hashcode] = d;
}
void print_exist(String key) {
int hashcode = hash(key);
while(hashtable[hashcode] != null) {
HashData d = hashtable[hashcode];
if (d.key == key) {
System.out.println(key + "は存在します" +
"(" + d.key + "," + d.name + "," +
d.math +"," + d.english + ")");
return;
}
hashcode++;
}
System.out.println(key + "は存在しません");
}
void dump_hashtable() {
for (int i = 0; i < hashtable.length; i++) {
System.out.print(i + ":");
HashData d = hashtable[i];
if (d == null) {
System.out.println();
} else {
System.out.println(d.key + "," + d.name + "," +
d.math +"," + d.english);
}
}
}
}
public class HashData {
public String key;
public String name;
public int math;
public int english;
}
ここでは2つのクラスを定義しており、どちらもpublicであるので、 Hash5.java と HashData.java という2つのソースファイルを書くこととなる。
HashDataクラスから作られるオブジェクトがハッシュに登録する一まとまり のデータとなる。この場合は、キー(学籍番号)、氏名、数学の点数、英語の点数 からなる。ハッシュ表は、このHashDataオブジェクトを要素とする配列になって いる。
以上の例では、レコードの内容(フィールド)は、publicになっており、 外部(HashDataオブジェクト外)からフィールドに直接アクセスしている。 しかし、オブジェクト指向プログラミングでは、このように外部から直接 フィールドにアクセスすることは好ましくなく、アクセス用のメソッドを 使うことが望ましい。このようなメソッドをアクセッサ(accessor)あるいは アクセスメソッドと呼ぶ。
アクセッサは以下の2つに分けられる。
アクセッサの名前には規則がある。例えば、フィールド名として nameがあるとする、nameのセッターはsetName(x)、nameのゲッターは getName()となる。つまりフィールド名の先頭を大文字に変えて、 セッターはset、ゲッターはgetを前に付けると良い。
JavaのAPIにはHashMapというハッシュを使うクラスが用意されている。 以下にHashMapクラスを使って例を示す。
import java.util.*;
public class HashMapTest1 {
public static void main(String args[]) {
Map students = new HashMap();
students.put("s03881", "情報太郎"); // s03881のデータを登録
students.put("s03872", "大学花子"); // s03872のデータを登録
// s03881,s03882をキーとしてデータを取得し表示
System.out.println("s03881 -> " + students.get("s03881"));
System.out.println("s03882 -> " + students.get("s03882"));
// s03881,s03882をキーとしてデータが存在するかどうか
System.out.println("s03881 ? " + students.containsKey("s03881"));
System.out.println("s03882 ? " + students.containsKey("s03882"));
// HashMapの内容を表示する
System.out.println(students);
// s03872のデータをハッシュから削除
students.remove("s03872");
System.out.println("s03872を削除");
// HashMapの内容を表示する
System.out.println(students);
}
}
HashMapは、何も引数を指定せずにオブジェクトを生成すると、 16の大きさのハッシュ表を作る。また、データの登録数がその75% を超えた時に自動的にハッシュ表を大きくする。
ハッシュに登録するには、putメソッドを使う。 ハッシュに登録する内容は、キーとデータの2つであり、これで1組となる。 キーとデータはそれぞれオブジェクトである必要がある。 例えば整数型のデータを扱いたい場合は、 new Integer(100)などとしてオブジェクト化しなければならない。
ハッシュからデータを得るにはgetメソッドを使う。引数にはキーを指定する。 指定したキーがハッシュに登録していない場合には、nullが返される。
指定したキーがハッシュに登録されているかどうかを知るには、containsKey メソッドを使う。戻り値がtrueなら登録されている、falseなら登録されていな いという意味である。
ハッシュから削除したい場合にはremoveメソッドを使う。引数にはキーを指 定する。
ハッシュに登録されているデータ全部を表示したい場合には、 printlnでHashMapオブジェクトをそのまま与えてやれば良い。 System.out.println(students);
さらなる詳細は、API仕様を参照のこと。
今までは、高速にデータを検索する目的でハッシュ法を紹介したが、 ハッシュは暗号技術としても非常に良く使われている。 一方向関数と呼ばれる関数をハッシュ関数に使い、ハッシュ値を求める。
一方向関数は、関数で求まる値から元の値を求めるのが非常に困難な関数である。 このため、ハッシュ値を変えずに、元のデータの値を変えることが事実上ほぼ不可能となる。 この性質を利用して、改竄(元のデータを書き変える)や偽称(本人以外が本人を騙る) がないことを証明でき、認証やデジタル署名などで使われている。 ハッシュを使う有名な暗号方式としてはMD5,SHA-1などがあり、 MD5はオープンソースのファイルが改竄されていないか確認するために広く使われている。
上のプログラム(Hash4.java)を実行し、データの削除が正しく行なわれているこ
とを確認せよ。
※ 要所でハッシュ表の一覧を表示させて確認せよ。
さらに、ハッシュ表の中で一度削除した部分に再び違うデータが
登録されるような例を考え、それを実行してみよ。
上のプログラム(Hash4.java)で、set("DELETED"); とした場合に、それと「削除済」の印が正しく区別されていることを確認せよ。
上のプログラム(Hash5.java, HashData.java)で、HashDataのフィールド にemail(電子メールアドレスを示す文字列)を追加せよ。
上のプログラム(Hash5.java, HashData.java)で、HashDataのフィールド (key, name, math, english)に直接アクセスせずに、ゲッターとセッター を定義して、それぞれを使うように書き変えよ。フィールドは全てprivate にするのを忘れずに。
課題hash-20に、さらに数学と英語の合計点を求めるgetTotalメソッドを 定義し、print_exist、dump_hashtableメソッドが呼ばれた場合に、 合計点も表示するようにせよ。
上のプログラム(HashMapTest1.java)を実行し動作を確認せよ。 さらに、16個以上のデータをハッシュに登録し、満足に動作する (自動的にハッシュの大きさが拡張される)ことを確認せよ。
ソフトウエア基礎
ohmi@rsch.tuis.ac.jp