Internal HashMap working : How to implement hashCode in java

Question

I am struggling to write proper hashCode function for the Student class given below.

1) What I believe that hashCode should be good enough so that two different object's hashCode should not collide with each other.

Observation : For this implementation, when I debugged and checked for 'internal table object of HashMap' class I found each entry in HashMap is assigned different bucket location.

Question : What is the purpose of having a bucket(list/tree) at each index.

Implementation :

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + id;
    return result;
}

2) If I allow collision of hashCode:

Observation : For this implementation, when I debugged and checked, found that 'size of internal table of hashMap' keeps increasing and only buckets within the range of hashCode gets used. Rest all bucket indexes shows null.

Question : What is the purpose of increasing internal table size, if the buckets out of hashCode range are always null.

Implementation :

@Override
public int hashCode() {
    return id%20;
}

Need Help for proper hashCode Implementation, so that Above issues can be fixed. Thanks for the help in advance.

============================ Code ===========================

public class HashMapTest {

public static void main(String a[]) {
    HashMap<Student, Integer> set = new HashMap<Student, Integer>();

    for (int i = 0; i < 5000; i++) {
        set.put(new Student(i), i);
    }

    set.put(new Student(5001), 5001);
    System.out.println(set.size());
}
}

class Student {
private int id;

public Student(int id) {
    this.id = id;
}

// Add here hashCode() provided in comments.


@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Student other = (Student) obj;
    if (id != other.id)
        return false;
    return true;
}

}

Answer 1

What is the purpose of having a bucket(list/tree) at each index.

HashMap does not require the hashCode to be unique, because this can generally not be accomplished (for instance, there are 2^32 hashcodes, but infinitely many Strings, so it is impossible to use a different hashCode for every String). Instead, it only requires that collisions be rare.

Therefore, the HashMap is implemented such that it still works correctly even if there is a collision (though it may work more slowly in that case). That's why the HashMap uses buckets that can store several elements if necessary.

What is the purpose of increasing internal table size, if the buckets out of hashCode range are always null.

The HashMap resizes the table because doing so splits buckets. Usually, splitting a bucket will cause some elements to go in one, and some elements in the other bucket, improving performance. It does not realize that your hashCode is so bad that all elements will remain in the same bucket, so keeps trying :-)

Need Help for proper hashCode Implementation, so that Above issues can be fixed.

I'd use

@Override
public int hashCode() {
    return id;
}

if id is unique (which its name seems to imply), this is a perfect hash function, and it's even quick to compute :-)

(note that the hashCode may be greater than the table size; the HashMap will take care of that by truncating it as necessary)