1

私はJavaでハッシュテーブルのクラスを書いています...これまでに正しく行っていることを確認してください。

StudentRecordオブジェクトを格納する必要があります....long型の学生のIDに基づいてハッシュ値を計算しています...

package proj3;

import java.util.LinkedList;

public class HashTable {

    LinkedList<StudentRecord> [] buckets;
    int size;

    public HashTable(){
            size = 10;
            initialize();       
    }

    public HashTable(int initialSize){
        size = initialSize;
        initialize();
    }

    private void initialize(){
        for(int i=0; i<size; i++){
            buckets[i] = new LinkedList<StudentRecord>();
        }
    }
    /** for testing only
    private int calculateHashString(String s){
        int hash = 0;
        for(int i=0; i<s.length(); i++){
            hash += s.charAt(i);
        }
        return hash % size;
    }
    **/

    private int calculateHash(long l){
        return (int) (l % size);
    }


    public boolean contains(StudentRecord sr){
        int hash = calculateHash(sr.studentID);
        LinkedList<StudentRecord> l = buckets[hash];
        if(l.contains(sr)){
            return true;
        }
        return false;
    }

    public void put(StudentRecord sr){
        int hash = calculateHash(sr.studentID);
        LinkedList<StudentRecord> l = buckets[hash];
        if(!l.contains(sr)){
            buckets[hash].add(sr);
        }
    }

}
4

5 に答える 5

8

あなたの f(r)iendly SO の専門家が健全性をチェックするかどうかに関係なく、実際の機能を検証するために単体テストを作成することをお勧めします。

単純なテスト ケースを超えた良い点の 1 つは、実装の機能を標準の JDK HashMap と比較することです。ランダムなキーおよび/または値を生成し、挿入、削除、および 2 つの実装間で状態が (あるべき程度まで) 同一であることを確認します。

于 2009-05-02T03:26:34.210 に答える
3

buckets初期化されることはないようです。そうしようとすると、コンパイラは警告を出します。配列に優先してコレクションに固執します (プリミティブを除く)。

引数のないコンストラクターは、他のコンストラクター ( this(10) を呼び出すことで、より簡単に実装できます。

複数の理由により、式(int) (l % size)は正の値でも負の値を返すことがあります。size

コード

public boolean contains(StudentRecord sr){
    ...
    if(l.contains(sr)){
            return true;
    }
    return false;
}

より明確に次のように書くことができます

public boolean contains(Student student) {
    ...
    return list.contains(student);
}
于 2009-05-02T09:28:08.227 に答える
2

いいね。

于 2009-05-02T03:23:25.497 に答える
0

トムは正しいです。バケットを新しい LinkedList[size] として初期化する必要があります。

サイズを最終的なものにして、より大きな値、たとえば 256 から始めたいと思います。項目がテーブルに追加された後にサイズを調整する場合は、それらすべてを新しいバケットに移動する必要があります (変更されたハッシュ アルゴリズムから)。 .

一方、テストには 10 が適しています。同じバケットで多くの衝突が発生します。

メモリを節約するために、最初に新しい LinkedList() をすべて初期化する必要はなく、null のままにしておくことができます。新しいアイテムが実際に null バケットにヒットするまで、各リスト オブジェクトの作成を待つことができます。もちろん、それは、読み取ろうとしているバケットが null であるかどうかを確認するための余分なコードを意味し、その場合は空のリストであると想定します。

于 2009-05-02T09:30:35.363 に答える
0

equals と hashCode メソッドもオーバーライドする必要があります。

于 2009-05-22T16:25:31.113 に答える