25

This issue is most apparent when you have different implementations of an interface, and for the purposes of a particular collection you only care about the interface-level view of the objects. For example, suppose you had an interface like this:

public interface Person {
    int getId();
}

The usual way to implement hashcode() and equals() in implementing classes would have code like this in the equals method:

if (getClass() != other.getClass()) {
    return false;
}

This causes problems when you mix implementations of Person in a HashMap. If the HashMap only cares about the interface-level view of Person, then it could end up with duplicates that differ only in their implementing classes.

You could make this case work by using the same liberal equals() method for all the implementations, but then you run the risk of equals() doing the wrong thing in a different context (such as comparing two Persons that are backed by database records with version numbers).

My intuition tells me that equality should be defined per collection instead of per class. When using collections that rely on ordering, you can use a custom Comparator to pick the right ordering in each context. There is no analogue for hash-based collections. Why is this?

Just to clarify, this question is distinct from "Why is .compareTo() in an interface while .equals() is in a class in Java?" because it deals with the implementation of collections. compareTo() and equals()/hashcode() both suffer from the problem of universality when using collections: you can't pick different comparison functions for different collections. So for the purposes of this question, the inheritance hierarchy of an object doesn't matter at all; all that matters is whether the comparison function is defined per-object or per-collection.

  • 5
    You can always introduce wrapper objects for Person that implement the expected equals and hashCode behaviour. You'd then have a HashMap<PersonWrapper, V>. This is one example where a pure-OOP approach is not elegant: not every operation on an object makes sense as a method of that object. Java's whole Object type is an amalgam of different responsibilities – only the getClass, finalize and toString methods seem remotely justifiable by today's best practices. – amon May 7 '15 at 9:54
  • 1
    1) In C# you can pass an IEqualityComparer<T> to a hash based collection. If you don't specify one, it uses a default implementation based on Object.Equals and Object.GetHashCode(). 2) IMO overriding Equals on a mutable reference type is rarely a good idea. That way the default equality is pretty strict, but you can use a more relaxed equality rule when you need it via a custom IEqualityComparer<T>. – CodesInChaos May 7 '15 at 12:05
  • 2
    Related meta question: Are these questions duplicates of each other? – user22815 Jun 4 '15 at 18:42
23

This design is sometimes known as "Universal Equality", it is the belief that whether two things are equal or not is a universal property.

What's more, equality is a property of two objects, but in OO, you always call a method on one single object, and that object gets to solely decide how to handle that method call. So, in a design like Java's, where equality is a property of one of the two objects being compared, it isn't even possible to guarantee some basic properties of equality such as symmetry (a == bb == a), because in the first case, the method is being called on a and in the second case it is being called on b and due to the basic principles of OO, it is solely a's decision (in the first case) or b's decision (in the second case) whether or not it considers itself equal to the other one. The only way to gain symmetry is to have the two objects cooperate, but if they don't… tough luck.

One solution would be to make equality not a property of one object, but either a property of two objects, or a property of a third object. That latter option also solves the problem of universal equality, because if you make equality a property of a third "context" object, then you can imagine having different EqualityComparer objects for different contexts.

This is the design chosen for Haskell, for example, with the Eq typeclass. It is also the design chosen by some third-party Scala libraries (ScalaZ, for example), but not the Scala core or standard library, which uses universal equality for compatibility with the underlying host platform.

It is, interestingly, also the design chosen with Java's Comparable/Comparator interfaces. The designers of Java clearly were aware of the problem, but for some reason only solved it for ordering, but not for equality (or hashing).

So, as to the question

why is there a Comparator interface but no Hasher and Equator?

the answer is "I don't know". Clearly, the designers of Java were aware of the problem, as evidenced by the existence of Comparator, but they obviously didn't think it a problem for equality and hashing. Other languages and libraries make different choices.

  • 7
    +1, but note that there are OO languages where multiple dispatch exists (Smalltalk, Common Lisp). So always is too strong in the following sentence: "in OO, you always call a method on one single object". – coredump May 7 '15 at 12:45
  • I've found the quote I was looking for; according to JLS 1.0, The methods equals and hashCode are declared for the benefit of hashtables such as java.util.Hashtable, i.e. both equals and hashCode were introduced as Object methods by Java devs solely for the sake of Hashtable - there's no notion of UE or anything silimar anywhere in the spec, and the quote is clear enough for me; if not for the Hashtable, equals would've probably been in an interface like Comparable. As such, while I formerly believed your answer to be correct, now I consider it unsubstantiated. – vaxquis May 17 '16 at 15:42
  • @JörgWMittag it was a typo, IFTFY. BTW, speaking of clone - it was originally an operator, not a method (see Oak Language Specification), quote: The unary operator clone is applied to an object. (...) The clone operator is normally used inside new to clone the prototype of some class, before applying the initializers (constructors) - the three keyword-like operators were instanceof new clone (section 8.1, operators). I assume that's the real (historic) reason of the clone/Cloneable mess - Cloneable was simply a later invention, and existing clone code was retrofit with it. – vaxquis May 17 '16 at 15:47
  • 2
    "This is the design chosen for Haskell, for example, with the Eq typeclass" This is sort of true, but it's worth noting that Haskell explicitly states up front that two objects of different types are never equal while Java's approach doesn't. The equality operation is thus part of the type, (hence "typeclass") not part of a third context value. – Jack May 17 '16 at 16:00
19

The real answer to

why is there a Comparator interface but no Hasher and Equator?

is, quote courtesy of Josh Bloch:

The original Java APIs were done very quickly under a tight deadline to meet a closing market window. The original Java team did an incredible job, but not all of the APIs are perfect.

The problem lies solely in Java's history, as with other similar matters, e.g. .clone() vs Cloneable.

tl;dr

it's for historical reasons mainly; current behaviour/abstraction was introduced in JDK 1.0 and wasn't fixed later on because it was virtually impossible to do so with maintaining backward code compatibility.


First, let's sum up a couple of well-known Java facts:

  1. Java, from the very beginning to the present day, was proudly backwards-compatible, requiring legacy APIs to be still supported in newer versions,
  2. as such, almost each and every language construct introduced with JDK 1.0 lived to present day,
  3. Hashtable, .hashCode() & .equals() were implemented in JDK 1.0, (Hashtable)
  4. Comparable/Comparator was introduced in JDK 1.2 (Comparable),

Now, it follows:

  1. it was virtually impossible & senseless to retrofit .hashCode() & .equals() to distinct interfaces while still maintaining backwards compatibility after the people realized there are better abstractions than putting them in superobject, because e.g. each and every one Java programmer by 1.2 knew that every Object has them, and they had to stay there physically to provide compiled code (JVM) compatibility also - and adding an explicit interface to every Object subclass that really implemented them would make this mess equal (sic!) to Clonable one (Bloch discusses why Cloneable sucks, also discussed in e.g. EJ 2nd and many other places, including SO),
  2. they just left them there for the future generation to have a constant source of WTFs.

Now, you may ask "what does Hashtable have with all this"?

The answer is: hashCode() / equals() contract and not-so-good language design skills of core Java developers in 1995/1996.

Quote from Java 1.0 Language Spec, dated 1996 - 4.3.2 The Class Object, p.41:

The methods equals and hashCode are declared for the benefit of hashtables such as java.util.Hashtable (§21.7). The method equals defines a notion of object equality, which is based on value, not reference, comparison.

(note this exact statement has been changed in later versions, to say, quote: The method hashCode is very useful, together with the method equals, in hashtables such as java.util.HashMap., making it impossible to make the direct Hashtable-hashCode-equals connection without reading historical JLS!)

Java team decided they wanted a good dictionary-style collection, and they created Hashtable (good idea so far), but they wanted the programmer to be able to use it with as little code/learning curve as possible (oops! trouble incoming!) - and, since there was no generics yet [it's JDK 1.0 after all], that would mean that either every Object put into Hashtable would have to explicitly implement some interface (and interfaces were still just in their inception back then... no Comparable yet even!), making this a deterrent to use it for many - or Object would have to implicitly implement some hashing method.

Obviously, they went with solution 2, for the reasons outlined above. Yup, now we know they were wrong. ... it's easy to be smart in hindsight. chuckle

Now, hashCode() requires that every object having it has to have a distinct equals() method - so it was quite obvious that equals() had to be put in Object as well.

Since the default implementations of those methods on valid a&b Objects are essentially useless by being redundant (making a.equals(b) equal to a==b and a.hashCode() == b.hashCode() roughly equal to a==b also, unless hashCode and/or equals is overriden, or you GC hundreds of thousands of Objects during the lifecycle of your application1), it's safe to say they were provided mainly as a backup measure and for usage convenience. This is exactly how we get to the well-known fact that always override both .equals() & .hashCode() if you intend on actually comparing the objects or hash-storing them. Overriding only one of them without the other is a good way to screw your code (by wicked compare results or insanely high bucket collision values) - and getting your head around it is a source of constant confusion & errors for beginners (search SO to see it for yourself) and constant nuisance to more seasoned ones.

Also, note that although C# deals with equals & hashcode in a bit better way, Eric Lippert himself states that they did almost the same mistake with C# that Sun did with Java years before C#'s inception:

But why should it be the case that every object should be able to hash itself for insertion into a hash table? Seems like an odd thing to require every object to be able to do. I think if we were redesigning the type system from scratch today, hashing might be done differently, perhaps with an IHashable interface. But when the CLR type system was designed there were no generic types and therefore a general-purpose hash table needed to be able to store any object.

1of course, Object#hashCode can still collide, but it takes a bit of effort to do that, see: http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6809470 and linked bug reports for details; https://stackoverflow.com/questions/1381060/hashcode-uniqueness/1381114#1381114 covers this subject more in-depth.

  • It's not just Java, though. Many of its contemporaries (Ruby, Python, …) and predecessors (Smalltalk, …) and some of its successors also have Universal Equality and Universal Hashability (is that a word?). – Jörg W Mittag Mar 12 '16 at 2:36
  • @JörgWMittag see programmers.stackexchange.com/questions/283194/… - I've to disagree about "UE" in Java; UE was historically never a real concern in Object's design; hashability was. – vaxquis May 17 '16 at 13:02
  • @vaxquis I don't want to harp on this, but my previous comment shows that two simultaneously reachable objects can have the same (default) hash code. – Solomonoff's Secret Aug 10 '17 at 17:02
  • 1
    @vaxquis OK. I buy that. My concern is that someone who is learning will see this and think they are clever by using the System hashcode instead of equals etc. If they do it, it will likely work well enough except for the rare times it doesn't and there will be no way to reproduce the issue reliably. – JimmyJames Aug 10 '17 at 20:33
  • 1
    This should be the accepted answer, since the accepted answer's conclusion is "i don't know" – Phoenix Aug 11 '17 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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