Optimizing equals() method

Question

The equals() method (and for that matter, also the compareTo() method) can become a performance hotspot (e.g. in a high-traffic HashMap). I was wondering what tricks folks have adopted to optimize these methods for these cases when they prove necessary.

IntelliJ IDEA, for example, generates the following:

public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    ...
}

What else have you come across that can be a guideline for writing a good performing equals()?

Answer 1

Some general ideas that are not necessarily specific to equals()

• Fail as early as possible. Similar to the snippet you posted, start with the broadest exclusion criteria first and then become more fine grained, so that the method can return as soon as possible
• Compare only attributes required for equality. I've sometimes seen people compare every single piece of a information a class provides, even though only a handful of attributes actually play a semantic role for the equality of two class instances. This of course highly depends on your class and the design
• Avoid equality recursion, if possible. Depending on what kind of class attributes you are comparing, you might get yourself into situations where you are recursively calling equals() on yourself or other objects, which can have a hidden performance impact

In addition to performance considerations, don't forget the equals API contract to ensure that your equality is reflexive, symmetric, transitive and consistent and to always override hashcode() as well, when you override equals().

Answer 2

I think you're already onto a key part of it because you said:

...when they prove necessary.

Remember the general rules for optimization:

1. Don't
2. Don't... yet
3. Profile before optimizing

I've heard them in a class years ago and as close as I can tell C2 is the source.

Answer 3

Check out a book entitle "Effective Java" by Joshua Bloch. It has some amazing tips and a whole section on this question. Goodluck!

Answer 4

You might take a cue from string interning.

If your objects are immutable, you could implement your own "interning" by using a static factory method and stuffing the unique instances into a hash table. If you do this, then when the references are equal the objects are equal.

Answer 5

If your objects are within an environment where you are in complete control over what calls equals() on them, then you should track what kind of comparisons you're performing, and tune your equals() method appropriately.

You might be able to confirm that certain scenarios never happen, so do not need to be coded for within equals(), such as:

• comparing null
• comparing different types
• comparing self

You can also decide on an appropriate order for the checks you do perform, checking the most common failing reasons first.

Answer 6

How to Write an Equality Method in Java is an extremely detailed and well written article explaining common pitfalls in writing an equality method and how to avoid them.

Answer 7

I suggest making the HashMap larger is equals() is expensive (e.g. by decreasing the load factor). That way you will have less collisions and hopefully if(o == this) return true will match most often.