HashTable Java... Can you check my code

Question

Hi, I'm writing an class for a hash table in java... can you please make sure that I am doing it correctly so far.

I need to store StudentRecord objects in it.... I am calculating the hash value based on the student's ID which is of type long...

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

Looks good.

Answer 2

I think you might want to write unit tests to verify its actual functioning, independent of whether your f(r)iendly SO experts sanity check it.

One good thing beyond simple test cases is to compare functioning of your implementation with the standard JDK HashMap; generate random keys and/or values, insert, remove, and check that state is identical (to the degree they should be) between the two implementations.

Answer 3

buckets never seems to get initialised. When you try to do so, the compiler should give you a warning. Stick to collections in preference to arrays (except for primitives).

Your no-args constructor could be more simply implemented by calling the other constructor (this(10).

The expression (int) (l % size) can return a negative even with a positive size, for more than one reason.

The code

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

could be more clearly written as

public boolean contains(Student student) {
    ...
    return list.contains(student);
}

Answer 4

Tom is right you need to initialize buckets as new LinkedList[size].

I think you want to make size final, and start with a larger value, say 256. If you adjust size after items have been added to the table, you will need to move them all into their new buckets (from the changed hash algorithm).

On the other hand, 10 is good for testing - lots of collisions on the same buckets!

To save memory, you don't have to initialize all those new LinkedList()s at the start, you could just leave them as null. You can wait to create each list object until a new item actually hits a null bucket. Of course that will mean extra code throughout, to check if the bucket you are trying to read is null, and if so assume it's an empty list.

Answer 5

You have to override equals and hashCode method too .