20

We are writing a class which requires very complicated logic to compute equals() and hashCode(). Something along lines with:

@Getters @Setters @FieldDefaults(level=AccessLevel.PRIVATE)
public class ExternalData {
  TypeEnum type;
  String data;
  List<ExternalData> children;
} 

We do not construct these objects, they are deserialized from XML from external complex system. There are 20+ types and depending on type data can be ignored, or processed with children, or processed without children and comparison of data for each type of node depend on type.

We created equals() and hashCode() to reflect all those rules, but recently ran into an issue that hashCode got out of sync with equals causing equal objects to be added twice to a HashSet. I believe HashMap (and HashSet for that matter) are implemented this way in Java: https://en.wikipedia.org/wiki/Hash_table The implementation first put objects in buckets based on hashCode and then for each bucket checks equals. In unfortunate scenario where 2 equal object will go to different buckets they will never be compared by equals(). By "Out of sync" here I mean that they go into different buckets.

What is the best way to make sure equals and hashCode do not get out of sync?

Edit: This question is different from What issues should be considered when overriding equals and hashCode in Java? There they ask about generic guidance and the accepted answer does not apply in my situation. They say "make equals and hashCode consistent", here I'm asking how exactly do I do that.

18
  • 4
    Property-based testing, probably. There is no simple rule, you have to test.
    – Paul Hicks
    Jul 3, 2016 at 21:30
  • 2
    Basically code review. You could probably do a static analyais in some cases, to check that equals and hashCode use the same fields, but the corner cases will probably overwhelm such a system. You could also use a project like Lombok to generate them for you.
    – yshavit
    Jul 3, 2016 at 21:30
  • 1
    Wherever possible, use auto-generation/etc. to help you. For example, check out the Immutables library - generates hashCode/equals for you. Jul 3, 2016 at 21:33
  • 4
    @Robert That's a horrible idea. The official documentation of hashCode indicates that unequal objects may have the same hashCode.
    – SE is dead
    Jul 4, 2016 at 1:43
  • 8
    @Robert Yes, equal objects must have the same hash code, but unequal objects may also have the same hash code, which is what dorukayhan said. Consider Long. There are 2^64 possible Long objects, and only 2^32 possible hash codes. By the pigeonhole principle, many unequal Long objects must have identical hash codes. Jul 4, 2016 at 3:59

4 Answers 4

6

The Guava testlib library has a class called EqualsTester that can be used to write tests for your equals() and hashCode() implementations.

Adding tests both helps you ensure that the code is correct now, and also ensures that it stays correct if/when you modify it in the future.

3
  • @T.J.Crowder I liked your answer yesterday, what was the comment? :)
    – Artem
    Jul 4, 2016 at 18:46
  • @T.J.Crowder I think it is actually a good idea and probably the only 100% way of guarantee that they are precisely the same not relying on people to write more tests and add in 2 places if they add functionality. Our system is offline (in a sense), there are no hard requirements on memory limits but there are on consistency. We actually do plan to have common code return a pair of hashCode and a boolean (if second argument was provided). So I'd be happy to accept your original answer :)
    – Artem
    Jul 5, 2016 at 7:38
  • @Artem: I wasn't happy with the answer for the reasons Daniel pointed out, but I've updated it to something I'm happy with now and undeleted it. (I've also removed my comments above, as they really have nothing to do with Daniel's answer here.) Jul 5, 2016 at 8:47
5

If the traversal algorithm is sufficiently complex that you want to avoid repeating yourself, isolate the algorithm into a method that both equals and hashCode can use.

I see two options, which (as is so often the case) trade-off between being broadly-applicable and being efficient.

Broadly-applicable

The first option is to write quite a general traversal method that accepts a functional interface and calls back to it at each stage of the traversal, so you can pass a lambda or instance into it containing the actual logic you want to perform while traversing; the Visitor pattern. That interface would want to have a way to say "stop traversing" (e.g., so equals can bail when it knows the answer is "not equal"). Conceptually, that would look something like:

private boolean traverse(Visitor visitor) {
    while (/*still traversing*/) {
        if (!visitor.visitNode(thisNode)) {
            return false;
        }
        /*determine next node to visit and whether done*/
    }
    return true;
}

Then equals and hashCode use that to implement equality checking or hash code building without having to know the traversal algorithm.

I've chosen above to have the method return a flag for whether traversal ended early, but that's a design detail. You might not return anything, or might return this for chaining, whatever's suitable in your situation.

The issue, though, is that using it means allocating an instance (or using a lambda but then you probably need to allocate something for the lamba to update anyway to keep track of what it's doing) and doing a lot of method calls. Maybe that's fine in your case; maybe it's a performance killer because your app needs to use equals a lot. :-)

Specific and efficient

...and so you might want to write something specific to this case, writing something that has the logic for equals and hashCode built into it. It would return the hash code when being used by hashCode, or a flag value for equals (0 = not equal, !0 = equal). No longer generally-useful, but it avoids creating a visitor instance to pass in / lambda overhead / call overhead. Conceptually, this might look something like:

private int equalsHashCodeWorker(Object other, boolean forEquals) {
    int code = 0;

    if (forEquals && other == null) {
        // not equal
    } else {
        while (/*still traversing*/) {
            /*update `code` depending on the results for this node*/
        }
    }

    return code;    
}

Again the specifics will be, um, specific to your case as well as your style guide and such. Some folks would make the other argument serve two purposes (both flag and the "other" object) by having equals handle the other == null case itself and only call this worker when it has a non-null object. I prefer to avoid doubling up on the meaning of arguments like that, but you see it often enough.

Testing

Whichever way you go, if you're in a shop with a testing culture, naturally you'll want to build tests for the complex cases you've already seen fail as well as other cases where you see failure opportunities.

Side note about hashCode

Regardless of the above, if you expect hashCode to be called a lot, you might consider caching the result to an instance field. If the object you're doing this with is mutable (and it sounds like it is), you'd invalidate that stored hashcode any time you mutate the object's state. That way, if the object hasn't changed, you don't have to repeat the traversal on subsequent calls to hashCode. But of course, if you forget to invalidate the hash code in even one of your mutator methods...

3
  • 4
    That doesn't really make sense to me: equals() requires a second object to compare to, but hashCode() doesn't. So I don't see any easy way to use the same code path for both. And I definitely would not encourage doing any allocations in equals() or especially hashCode(), since those methods will be called from code you don't control, often on a hot path. For example, adding an unrelated object to a HashMap that contains your object may cause your object's hashCode() to be invoked -- if that happens many thousands of times per second then you'll create a lot of GC pressure. Jul 3, 2016 at 22:56
  • 1
    @DanielPryden HashMap doesn't cache the hash code? Also, cached or not, it'll almost certainly only look at the hash of objects already in the table if it is resized, which will not happen on every insertion.
    – Random832
    Jul 4, 2016 at 3:29
  • @DanielPryden: Both very good points. I've updated the answer. Jul 5, 2016 at 8:46
5

one option to condsider may be code generation. Basically you write out a list of things that need to be compared and have a program that generates both an equals method and a hashcode method. Since both methods are generated from the same list of things to compare they should not fall out of sync (provided the individual elements don't of course).

0

if a.equals(b), this implies a.hashcode() == b.hashcode().

However, be careful. !a.equals(b) does NOT imply a.hashcode() != b.hashcode().

This is simply due to the fact that hash collisions can be a serious issue depending on your algorithm and a large number of factors. In general, if two objects are equal their hashcode will always be equal. However, you cannot determine if two objects are equal only by comparing hashcode, as a.hashode() == b.hashcode() also does not imply a.equals(b).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.