ソフトウエア基礎
deleteメソッドを呼ぶ直前と直後に、dump_hashtableメソッドを呼ぶと 以下のような結果が出力される。
0: 1: 2: 3:xyz 4:abc 5:yyy 6: 7: 8: 9: 0: 1: 2: 3:DELETED 4:abc 5:yyy 6: 7: 8: 9: 0: 1: 2: 3:zyx 4:abc 5:yyy 6:bbb 7: 8: 9:
ハッシュ表の3にxyzが格納されていたのが、削除することで、DELETEDに変え られ、その後、zyxが格納されていることが分かる。
ハッシュ表の中で一度削除した部分に再び違うデータが格納される例を考え
る課題:
例えば、runメソッド内に以下のように記述する。
set("fff");
set("efg");
dump_hashtable();
delete("fff");
dump_hashtable();
set("feg");
dump_hashtable();
実行すると以下のような結果を得る(5〜8のみ示す)。
5: 6:fff 7:efg 8: 5: 6:DELETED 7:efg 8: 5: 6:feg 7:efg 8:
runメソッド内に以下のように記述する。
set("fff");
dump_hashtable();
delete("fff");
set("DELETED");
dump_hashtable();
set("feg");
set("yyy");
dump_hashtable();
実行すると以下のような結果を得る(3〜7のみ示す)。
3: 4: 5: 6:fff 7: 3:DELETED 4: 5: 6:DELETED 7: 3:DELETED 4:yyy 5: 6:feg 7:
まず、fffはハッシュ表の6に格納された。次にfffを削除し、ハッシュ表の 6に削除を示すDELETED(変数deletedの値)が格納された。文字列DELETEDの ハッシュ値は3となり、ハッシュ表の3に格納された。 次にfegをハッシュ表に格納しようとすると、ハッシュ値である6の場所には、 削除を示すDELETEDが入っており、そこにfegが格納された。 yyyを格納しようとすると、ハッシュ値である3の場所には、set("DELETED") で格納した文字列データが入っており、そこには格納されず、その1つ下の 4にyyyが格納された。このように、削除を示すDELETEDと、set("DELETED") でハッシュ表に格納したデータが区別されていることが分かる。
public class HashData {
public String key;
public String name;
public int math;
public int english;
public String email;
}
Hash5.java
public class Hash5 {
final int size = 10;
HashData hashtable[] = new HashData[size];
String deleted = new String("DELETED");
// String deleted = new String("DELETED");
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, "yamada@hogehoge.example");
set("s03872", "松田二郎", 70, 87, "matsuda@hogehoge.example");
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, String email) {
int hashcode = hash(key);
HashData d = new HashData();
d.key = key;
d.name = name;
d.math = math;
d.english = english;
d.email = email;
while(hashtable[hashcode] != null &&
hashtable[hashcode].key != deleted) {
hashcode++;
}
hashtable[hashcode] = d;
}
boolean delete(String key) {
int hashcode = hash(key);
while(hashtable[hashcode] != null) {
if (hashtable[hashcode].key == key) {
hashtable[hashcode].key = deleted;
return true;
}
hashcode++;
}
return false;
}
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 + "," + d.email + ")");
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 + "," + d.email);
}
}
}
}
public class HashData {
private String key;
private String name;
private int math;
private int english;
public String getKey() { return key; }
public String getName() { return name; }
public int getMath() { return math; }
public int getEnglish() { return english; }
public void setKey(String k) { key = k; }
public void setName(String n) { name = n; }
public void setMath(int m) { math = m; }
public void setEnglish(int e) { english = e; }
}
Hash5.java
public class Hash5 {
final int size = 10;
HashData hashtable[] = new HashData[size];
String deleted = new String("DELETED");
// String deleted = new String("DELETED");
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.setKey(key);
d.setName(name);
d.setMath(math);
d.setEnglish(english);
while(hashtable[hashcode] != null &&
hashtable[hashcode].getKey() != deleted) {
hashcode++;
}
hashtable[hashcode] = d;
}
boolean delete(String key) {
int hashcode = hash(key);
while(hashtable[hashcode] != null) {
if (hashtable[hashcode].getKey() == key) {
hashtable[hashcode].setKey(deleted);
return true;
}
hashcode++;
}
return false;
}
void print_exist(String key) {
int hashcode = hash(key);
while(hashtable[hashcode] != null) {
HashData d = hashtable[hashcode];
if (d.getKey() == key) {
System.out.println(key + "は存在します" +
"(" + d.getKey()+ "," + d.getName() + "," +
d.getMath() +","+ d.getEnglish() + ")");
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.getKey() + "," + d.getName() + "," +
d.getMath() +"," + d.getEnglish());
}
}
}
}
HashData.javaに以下のメソッドを追加する。
public int getTotal() { return math+english; }
また、Hash5.javaのprint_exist,dump_hashtableメソッドを 以下のように修正する。
void print_exist(String key) {
int hashcode = hash(key);
while(hashtable[hashcode] != null) {
HashData d = hashtable[hashcode];
if (d.getKey() == key) {
System.out.println(key + "は存在します" +
"(" + d.getKey() + "," + d.getName() + "," +
d.getMath() +"," + d.getEnglish() +
"," + d.getTotal() + ")");
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.getKey() + "," + d.getName() + "," +
d.getMath() +"," + d.getEnglish() +"," +
d.getTotal());
}
}
}
ソフトウエア基礎
ohmi@rsch.tuis.ac.jp