As you might now, important part of HashMap is hash function which determines which bucket that key-value pair will go to. This makes hashcode() method in key object very important. Just to put it in perspective, below is a small experiment.
Same hashcode all the time !
If a key object coded in a way to send same hashcode all the time, then eventually all the key-value pairs will end up in same bucket inside HashMap. If your HashMap has n key-value pairs, then while you try to get the value back, HashMap will have to iterate through all n key-value pairs.
Lets take example of map of employee & department. Below Employee class has equals overridden but hashcode() method return 1 all the time.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Employee { String firstName; public Employee(String firstName) { this.firstName = firstName; } @Override public boolean equals(Object obj) { return firstName.equals(((Employee) obj).firstName); } @Override public int hashCode() { return 1; } } |
This is Department object just to use as value
|
1 2 3 4 5 6 7 |
class Department { String name; public Department(String name) { this.name = name; } } |
Now lets test the performance by loading 10,000 key-value pairs in a map. After loading we will try to get all the values back & record how much time it takes.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public class HashMapPerformanceTest { public static void main(String[] args) { /* * Fill HashMap with 10000 records. Employee key & Department as value. */ HashMap<Employee, Department> employees = new HashMap<>(); for (int i = 0; i <= 10000; i++) { employees.put(new Employee("name" + i), new Department("dept" + i)); } System.out.println("Completed inserting records. Lets find records now"); /* * Count time required to get all the values from HashMap */ long start = (long) System.currentTimeMillis(); for (int i = 0; i <= 10000; i++) { employees.get(new Employee("name" + i)); } System.out.println("Time to find dept is " + (System.currentTimeMillis() - start) + " ms . "); } } |
Output:
|
1 2 |
Completed inserting records. Lets find records now Time to find dept is 2547 ms . |
It took around 2547 mills (might slightly vary every time) to get all the elements due to iteration in same bucket.
Different hashcodes
Now lets try same example by implementing hashcode i.e. lets use hashcode() of member variable i.e. “return firstName.hashCode();”
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Employee { String firstName; public Employee(String firstName) { this.firstName = firstName; } @Override public boolean equals(Object obj) { return firstName.equals(((Employee) obj).firstName); } @Override public int hashCode() { return firstName.hashCode(); } } |
Now when we do the same test above, here is the latest output
|
1 2 |
Completed inserting records. Lets find records now Time to find dept is 6 ms . |
Time got down to 6 ms which is huge reduction. So basically hashcode plays vital role in HashMap performance. But still this doesn’t mean you have to go to extreme lengths to make hashcode unique. You can follow code as advised by author “Joshua Bloch” or you can try builder provided by Apache i.e. HashCodeBuilder . There might also be several other alternatives present online on different blogs or sites which can be followed.