In Java, some built-in libraries depend on the object’s implemented hashcode method. For example, HashMap and HashSet depend on the value returned from this method. Ensuring the proper implementation of hashCode is a MUST, not just for these data structures to work effectively, but also to enable them to process these objects efficiently.

In this article, we are going to explore the general contract of proper implementation of the hashCode, when it’s important to implement it, how to write the state-of-the-art one, and some tricks to optimize its performance.

---

Relation between equals and hashCode

When the equals() method is overridden in a class, it’s important to also provide an implementation for the hashCode() method to ensure the proper functioning of the class in collections that rely on hash codes, such as HashMap and HashSet.

Remember that it’s important to include every significant field in the computation of the hash code for a class that is involved in the equals() method. Think of them like they are a reflection of each other. For a class that iterates an array to check for equality, the implementation of the hashCode() method also needs to iterate over the same array to calculate the hash code for each element.

You can check my post about the implementation of the equals method to ensure these two methods work reliably.

---

The general contract of Object.hashCode() implementation

• If the hashCode() method is called multiple times on an object during the execution of an application, it should always return the same value as long as no information used in equals() comparisons has been modified.
• If two objects are equal, according to their equals(Object) method, then calling their hashCode methods should produce the same result.
• It’s better for unequal objects to have distinct hash codes. In a less-than-ideal world, it’s possible for two objects that are not equal to have the same hash code. Equal objects must have equal hash codes. The violation of this rule would make a collection like HashMap behave unexpectedly. Let’s see an example of the HashMap behavior as a result of a violation of the second part of the contract. Assume the Person.hashCode() has a wrong implementation that produces different results for equal objects.

/* Example of HashMap behaviour as result of 
   violation of the second part of the contract */
Map<Person, Integer> map = new HashMap<>();
Person p1 = new Person("Name", 20);
Person p2 = new Person("Name", 20);
p1.equals(p2); // true
map.put(p1, 800);
map.get(p2); // Is null

We can assume p1.hashCode() returns 10, and p2.hashCode() returns 100. Calling map.put(p1, 800) inserts p1 into a bucket corresponding to its hash code, which is 10. On the other hand, calling map.get(p2) tries to find p2 in a bucket that corresponds to its hash code, which is 100. Clearly, it will return null because it doesn’t exist there.

This is what will happen when violating the second part of the contract. When equal objects, based on the implementation of the equals method, have different hash codes, any collection or client code that relies on this hash value will behave in a wrong way.

When writing the hashCode function, we aim to fulfill two fundamental requirements:

1. Objects that are considered equal must produce the same hash code. Also, a good hash function tends to produce distinct results for different objects.
2. The hash function is better to generate hash codes that are evenly distributed among a finite range of values. Doing so reduces the number of collisions during the insertion into hash-based data structures. If all objects have the same hash, this means a data structure like HashMap will behave like a LinkedList, because it handles collisions using a concept called Separate Chaining. In the real world, collision prevention is almost impossible, but we could achieve better results with the good implementation of the hashCode method.

---

How to reach a fair approximate for no collisions solution

1. Calculate the hashCode for the first significant field “A” and store it in a variable (assume its name is hashResult).
   • If “A” is a primitive type, call its wrapper class hashCode method.
   • Call A.hashCode() if it’s an object reference. If the object is null you can replace it with any constant value, but zero is the most common.
   • If it’s an array, we consider every entry as if it’s a significant object. So, iterate through the array and accumulate each hash code to the hashResult.
2. For the remaining significant fields, call their hashCode method and sum it to the previously calculated hashResult * 31.

Choosing the number 31 because it’s a prime number and easy to get calculated using the shift operator, which is much faster than the normal multiplication.

An example is better to illustrate these steps.

class Employee {
    private int age;
    private int salary;
    private String name;
    private int hashResult;
 
    public Employee(int age, int salary, String name) {
        this.age = age;
        this.salary = salary;
        this.name = name;
    }
 
    @Override
    public int hashCode() {
        hashResult = Integer.hashCode(age);
        hashResult = 31 * hashResult + Integer.hashCode(salary);
        hashResult = 31 * hashResult + (name == null ? 0 
                    : name.hashCode());
        return hashResult;
    }
}

Here the equals method is eliminated to shorten the code, but it must use these fields for its result — in this case, the age, salary, and name.

If the object contains any derived field (a field whose value gets derived from one or more fields) — for example, integer field days gets calculated from the start and end dates — it shouldn’t participate in hash code calculation if the values used to derive it were already used in the computation. In this case, we may exclude the days field if start and end dates are involved in calculating the hash code.

Multiplying the hashResult each time by 31 yields a much more solid result that depends on the order of the fields. So, if two classes have the same values for different fields, the result would be different for both. In our example, if an employee e1 has age = 30, salary = 50, and another e2 has age = 50, salary = 30, the hashResult would be different for each of them.

Performance Tip: It’s better to optimize the multiplication by using the shift operator in your code. So hashResult * 31 == (hashResult << 5) - hashResult is true. The shift operator is known to be faster than the normal multiplication operation.

---

Building your own hashCode or using Java’s built-in method (Performance Tip)

The Java Object class contains an implementation that looks almost the same as ours: Object.hash(Object... values). Although it performs all the calculations that we need, it has a drawback that should prevent us from using it.

The hash method takes a variable number of arguments of object type, which leads to an array creation to hold these objects as well as the process of boxing and unboxing them. This could yield a slow performance if you are using many fields in the hash code computation and the hashCode method gets called multiple times. So it’s better to build your own using the same steps that we mentioned.

---

Cache the hash result for immutable classes (Performance Tip)

If the hashCode() method of an immutable class gets called frequently, it is advisable to cache the hash code result instead of calculating it each time it is requested. See the below code snippet to see how to do that.

// Immutable class
class Point {
    private final int x;
    private final int y;
    private int hashResult; 
 
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
 
    @Override
    public int hashCode() {
        int result = hashResult;
 
        if (result == 0) {
            result = Integer.hashCode(x);
            result = 31 * result + Integer.hashCode(y);
 
            hashResult = result;
        }
        return hashResult;
    }
}

In order to minimize collisions and enhance the performance of the HashMap, it’s crucial to incorporate the highly significant fields, even if it comes at the expense of the hashCode method performance. Incorporating these fields helps to avoid situations where multiple objects are mapped to the same hash codes, which can cause the HashMap to behave like multiple LinkedLists and lead to a quadratic time complexity instead of linear. It is recommended to concentrate on using fields that have a higher probability of being unique, such as an employee’s ID, which cannot be identical for two different employees.

---

Conclusion

You are required to write a hash function that produces equal hash codes for equal objects and, as much as possible, distinct results for unequal objects. Use the same fields that are used in the object’s equals method. Don’t rely on Objects.hash(Object... values) because it will badly affect your performance and memory usage a bit. Remember to cache the hash code for immutable objects if they get called multiple times. To achieve a more even distribution of hash codes, it’s recommended to select the most significant fields that are unlikely to have identical values and utilize them for hash code computation.