HashTable Java ... 내 코드를 확인할 수 있습니까

Question

자바에서 해시 테이블 용 클래스를 작성하고 있습니다 ... 지금까지 제대로 수행하고 있는지 확인하십시오.

은 내가 오랫동안 유형 인 학생의 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); 
     } 
    } 

} 

Answer 1

좋은 외모를 계산하고 .... 거기에 StudentRecord 객체를 저장해야합니다.

Answer 2

필자는 f (r) iendly SO 전문가의 온 전성 여부와 관계없이 실제 작동 여부를 확인하기 위해 단위 테스트를 작성하는 것이 좋습니다.

단순한 테스트 케이스를 넘어서 좋은 점은 표준 JDK HashMap과 구현의 기능을 비교하는 것입니다. 랜덤 키 및/또는 값을 생성하고 삽입, 제거 및 해당 상태가 두 구현간에 동일해야 함을 확인합니다.

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로 남겨 둘 수 있습니다. 새 항목이 실제로 null 버켓에 도달 할 때까지 각 목록 객체를 만들 때까지 기다릴 수 있습니다. 물론 읽는 버켓이 null인지 확인하고, 빈 버스트라고 가정하면 여분의 코드를 의미합니다.

Answer 5

equals 및 hashCode 메소드도 대체해야합니다.