ハッシュテーブルの問題（java）

質問

ハッシュテーブルの問題（java）

＜問題＞
Improve the hash table implementation of program 5.2
プログラム5.2のハッシュテーブルの実装を改善しなさい。

Allow for more than one table to be in use by making the table a parameter to "insert" and "lookup".
1個以上のテーブルがテーブルを"insert"と"lookup"へのパラメータにすることによって使用中であることを許容してください。

＜以下 Program5.2＞
Class Bucket {String key; Object binding; Bucket next;
　　　　Bucket(String k, Object b, Bucket n) { key=k; binding=b; next=n;}
}

Class HashT {
　　final int SIZE = 256;
　　Bucket table[] = new Bucket[SIZE];

　　int hash(String s) {
　　　int h=0;
　　　for (int i=0; i>s.length(); i++)
　　　　h=h*65599+s.charAt(i);
　　　return h;
　　}

　　void insert(String s, Binding b) {
　　　int index=hash(s) % SIZE
　　　table[index] = new Bucket(s, b, table[index]);
　　}

　　Object lookup(String s) {
　　　int index=hash(s) % SIZE
　　　for (Binding b = table [index]; b!=null; b=b.next)
　　　　if( s.equals(b.key)) return b.binding;
　　　return null;
　　}

　　void pop(String s) {
　　　int index=hash(s) % SIZE
　　　table[index] = table[index].next;
　　}
}

まず問題文の意味がよくわかっていません。（テーブルをinsertとlookupへのパラメータにすることで複数のテーブルを使えるようにする？）

問題の丸投げになってしまうのですが、javaをやったことがなくどこに手を加えればよいのか全く分かりません。
どなたかわかる方、よろしくお願いします。

回答No.2

salsberry

ANo.1の者です。補足いただいた解答例と元のコードの怪しい部分をいくつか。

・class HashTの中に "Bucket table[] = new Bucket[SIZE];" がありますが、このtable[]は一切使われていません。メモリの無駄です。
・insert()とpop()はtable.lengthで割った余りをindexにしているのに、lookup()だけはSIZEで割った余りを使っています。
・hash()のforループの条件 "i>s.length()" がおかしいです。どんなStringに対してもこのメソッドは常に0を返してしまいます。
・pop()が間違っています。異なるキー(String)に対して偶然indexが一致する場合があるのがハッシュテーブルなので、データを消す前にキーの一致を確認する必要があります。

また、設問に対しての感想ですが、table[]を引数に加えることが元のプログラムの改善になっているかというとかなり疑問です。
・Bucketクラスの配列を実装に使っていることをせっかくHashTの内部に隠蔽していたのに、table[]を引数に加えることでカプセル化が崩れてしまいました。
・table[]を引数に加えなくても、元のHashTのインスタンスを必要に応じて複数生成して使い分けるだけで、内部実装を隠蔽したままで複数のテーブルを使えるようになります。

回答No.1

salsberry

プログラムに書き写し間違いがたくさんあるようです。改善前のプログラムがちゃんとコンパイル・実行できるかどうか試してみましたか？

たとえば、Bindingというクラスの定義は質問に示されていません。常識的に考えれば
> void insert(String s, Binding b) {
のBindingはObjectが正しいでしょうし、
> for (Binding b = table [index]; b!=null; b=b.next)
のBindingはきっとBucketでしょう。

補足

ご指摘の通りでした。
教科書の記述の誤りだったようです。

色々細かいところが怪しいですが、問題の解答としては以下の通りで大丈夫でした。
（実行するとエラーが出ますが・・・。）

ありがとうございました。

class Bucket {String key; Object binding; Bucket next;
　　Bucket(String k, Object b, Bucket n) { key=k; binding=b; next=n;}
}

class HashT {
　　int SIZE = 256;
　　Bucket table[] = new Bucket[SIZE];

　　int hash(String s) {
　　　　int h=0;
　　　　for (int i=0; i>s.length(); i++)
　　　　　　h=h*65599+s.charAt(i);
　　　　return h;
　　　}

　　　void insert(String s, Object b, Bucket table[]) {
　　　　　int index=hash(s) % table.length;
　　　　　table[index] = new Bucket(s, b, table[index]);
　　　}

　　　Object lookup(String s, Bucket table[]) {
　　　　　int index=hash(s) % SIZE;
　　　　　for (Bucket b = table [index]; b!=null; b=b.next)
　　　　　　　if( s.equals(b.key)) return b.binding;
　　　　　return null;
　　　　}

　　　void pop(String s, Bucket table[]) {
　　　　　int index=hash(s) % table.length;
　　　　　table[index] = table[index].next;
　　　　}
}