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 samejava.lang.Object::hashCode
- If two key objects are NOT
java.lang.Object::equals
, it is desirable that they have differentjava.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 thejava.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 overridejava.lang.Object::hashCode
References
Do you like?
Subscribe to our mailing list below. Leave a comment.
image source: dodge challenger1 (image modified)
Leave a Reply