Simple use of hashing to create a generic hash set class.

HashExample.java

// A relatively simple example of a hash set class with support for generic
// types. Since the point was to demonstrate the use of hash functions and
// collision resolution (chaining, in this case), we implemented a hash set
// instead of a table, which has a simpler, more straight-forward
// implementation.  A hash table can be implemented in almost the exact same
// way, but by storing pairs of (key, item) in the linked lists instead of just
// the items.

import java.util.LinkedList;
import java.util.ArrayList;

public class HashExample {
    // Use the hash set and student class
    public static void main(String[] args) {
        //TODO: Write some test code here!
        MyHashSet<Student> students = new MyHashSet<Student>();
        students.add(new Student("V001"));
        students.add(new Student("V031"));
        students.add(new Student("V861"));
        students.add(new Student("V326"));

        // The next three produce collisions
        // because they all hash to the same
        // value. (Why?)
        students.add(new Student("V201"));
        students.add(new Student("V021"));
        students.add(new Student("V120"));

        System.out.println(students);

        System.out.println();

        Student s = new Student("V004");
        System.out.println("Is V004 in there? " + students.contains(s));

        s = new Student("V001");
        System.out.println("Is V001 in there? " + students.contains(s));

        System.out.println("Removing V001");
        students.remove(s);
        System.out.println("Is V001 in there? " + students.contains(s));

        System.out.println();
        System.out.println(students);
    }
}

class MyHashSet <T> {
    static final int HASH_SIZE = 5;
    ArrayList<LinkedList<T>> table;
    int size;

    public MyHashSet() {
        size = 0;
        table = new ArrayList<LinkedList<T>>(HASH_SIZE);
        for(int i = 0; i < HASH_SIZE; i++ ) {
            table.add(new LinkedList<T>());
        }
    }

    private int getIndexForObject(T s) {
        int h = s.hashCode() % HASH_SIZE;
        // In case h is negative, add HASH_SIZE to make it positive and in
        // the range 0 <= h < HASH_SIZE.
        // Java is funny with the % operator.
        // For example, -2 % 3 is -2 and not 1 in Java
        if(h < 0) {
            h += HASH_SIZE;
        }
        return h;
    }

    public void add(T s) {
        if(s == null) {
            throw new IllegalArgumentException("Can not add null object to set.");
        }
        int h = getIndexForObject(s);
        if(!table.get(h).contains(s)) {
            // Only add if it is not already in the set
            table.get(h).add(s);
            size ++;
        }
    }

    public boolean remove(T s) {
        int h = getIndexForObject(s);
        boolean removed = table.get(h).remove(s);
        // Change size here
        if(removed) {
            size --;
        }
        return removed;
    }

    public boolean contains(T s) {
        int h = getIndexForObject(s);
        return table.get(h).contains(s);
    }

    public void clear() {
        size = 0;
        for(LinkedList<T> l : table) {
            l.clear();
        }
    }

    public String toString() {
        String r = "Hash set with " + this.size + " items:";
        for(int i = 0; i < HASH_SIZE; i++) {
            r += "\n" + i + ": " + table.get(i).toString();
        }
        return r;
    }

    public int size() {
        return size;
    }
}

class Student {
    private String studentId;
    // We could have more data here but they will not play a role in our hash
    // calculation here, so for simplicity let's leave them out.
    // private String firstName;
    // private String lastName;
    // ...

    public Student(String id) {
        this.studentId = id;
    }

    public String getStudentId() {
        return this.studentId;
    }

    public void setStudentId(String id) {
        // Later, we can do error checking here
        this.studentId = id;
    }

    public String toString() {
        return this.studentId;
    }

    @Override
    public boolean equals(Object other) {
        if(other instanceof Student) {
            Student o = (Student) other;
            return o.studentId.equals(this.studentId);
        }
        // If o is not even of type Student then it is not equal to this.
        return false;
    }

    @Override
    public int hashCode() {
        //TODO: Calculate the hash
        // One simple method would be to simply sum all the integer values of
        // all the characters in the student id. What are easy ways
        // of producing collisions this hash function?
        char[] chars = this.studentId.toCharArray();
        int h = 0;
        for(char c : chars) {
            h += (int)c;
        }
        return h;
    }
}