HashTable Java ...私のコードをチェックすることができます

Question

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

私はタイプの長である学生のIDに基づいてハッシュ値を計算しています....それにStudentRecordオブジェクトを格納する必要があります...

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); 
     } 
    } 

} 

Answer 1

がよさそうです。

Answer 2

私はあなたのf（r）iendly SOの専門家の健全性をチェックするかどうかに関係なく、その実際の機能を確認するために単体テストを書いたがっていると思います。

単純なテストケースを超えて良いことの1つは、実装の機能を標準のJDK HashMapと比較することです。ランダムなキーや値を生成し、その状態が2つの実装間で同一であることを挿入、削除、チェックします。

Answer 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); 
} 

Answer 4

トムのように書くことができたコードは、右あなたが新しいLinkedListの[サイズ]としてバケットを初期化する必要があります。

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

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

メモリを節約するために、新しいLinkedList（）を最初に初期化する必要はありません。最初はnullにしておくだけです。新しい項目が実際にヌルバケットに当たるまで、各リストオブジェクトの作成を待つことができます。もちろん、それはあなたが読もうとしているバケツがヌルであるかどうかをチェックするために余分なコードを意味し、空のリストであると仮定します。

Answer 5

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