How to Improve HashMap Performance

Providing a good implementation of java.lang.Object::hashCode, is essential to HashMap performance.

This tutorial, complete with a source code visualization, describes how HashMap performance can be improved…

If you haven’t read our Hashmap Introduction Tutorial, be sure to read that post first.

API

Pertinent methods are described:

• If two key objects are java.lang.Object::equals, they must have the same java.lang.Object::hashCode
• If two key objects are NOT java.lang.Object::equals, it is desirable that they have different java.lang.Object::hashCode, but not required. It is desirable for keys to have as unique as possible hashCodes, as this increases the performance of the HashMap. When different keys have the same hashCode there is a collision and the keys are then stored in a linked list at that bucket.

Example

The following example shows a poorly written java.lang.Object::hashCode, which causes two collisions. This reduces the performance of the put and get operations.

Click on the flashing arrow to step through the example.

Http iframes are not shown in https pages in many major browsers. Please read this post for details.

Tips

• There is no need to write java.lang.Object::hashCode implementations yourself.  Use a Integrated Development Environment like IntelliJ or Eclipse, to generate the java.lang.Object::hashCode method for you. However it is important to understand how hashCode works, to detect and fix performance problems if they arise
• Java 8 brings HashMap performance improvements. When there are many key collisions, balanced trees are used rather than a linked list to store keys. Note that a balanced tree still does not perform as well as a good hashCode method
• If you override java.lang.Object::equals you must override java.lang.Object::hashCode

References

• Javadoc for HashMap
• Java 8 HashMap performance improvements

Do you like?

Subscribe to our mailing list below.  Leave a comment.

 

image source: dodge challenger1 (image modified)