Comparators

This post is part of a series on Comparing Objects.

Some things lend themselves to default ordering, such as sorting users by their alphabetized last names. Yet users are often sorted by other criteria, such as the number of purchases they make per year, the amount their account is in debit, or what time they clicked the "purchase" button during a limited promotion. To represent this in Java, simply define a comparator for each context:

enum UserByPromoClick implements Comparator<User> {
    INSTANCE;
    public int compare(User left, User right) {
        ...
    }
}

enum UserByPurchases implements Comparator<User> {
    ...

enum UserByDebit implements Comparator<User> {
    ...

Implementation note: compare(left, right) and compareTo(other) are both instance methods, which means you need to create an instance of the appropriate Comparator in order to use them.  Most comparators are immutable and unchanging.  This means they should be implemented as Enums with a single immutable instance shared and reused by all clients.

Various sort orders are often combined. Two accounts equally in debit could be sorted to show up next to each other on an expense report. Their names would only be used as the "tie breaker" in this ordering.

public int compare(User left, User right) {
    // Assuming getPromoClickMs returns Integer.MAX_VALUE
    // if the user didn't click on the promo.
    if (left.getPromoClickMs() > right.getPromoClickMs()) { return 1; }
    if (left.getPromoClickMs() < right.getPromoClickMs()) { return -1; }

    // In a tie, sort by name instead.
    return UserByName.compare(left, right);
}

The implementation of Objects.equals(left, right) performs a referential equality check for speed and to ensure that each object is equal to itself.  This has the side effect that if someone passes compare(null, null) it returns true, which makes sense some: undefined is undefined.  But should we ever compare anything to null? For a while I thought, "What harm could come from just sorting nulls last?"

What harm indeed!  Really, there is no meaningful way to compare a value to null because null represents "undefined." Well, isGreaterThan(other) can meaningfully return false if other is null, but the general-purpose compare(left, right) method cannot.  It must return less-than (any negative int), greater-than (any positive int), or equal (0). The only rational thing to do if either parameter to the compare(a, b) method is null is to throw an exception.

if (left == null) {
    throw new IllegalArgumentException("Can't compare nulls");
}
if (left == right) { return 0; } // Also ensures right != null

If your class can be represented as an integer, compare() could be implemented as a simple subtraction.  Just keep in mind that if your subtraction could exceed Integer.MIN_VALUE, it can roll and give you a positive result instead of a negative one. So if that could happen, you must use greater-than/less-than comparasions instead of subtraction.

int ret = left.getPromoClickMs() - right.getPromoClickMs();
if (ret != 0) { return ret; }

// In a tie, sort by name instead.
return UserByName.compare(left, right);

You can have as many repetitions of this kind of thing as you want:

ret = Xxxxx.compare(this, that);
if (ret != 0) { return ret; }

Persistence and Proxy Objects

When implementing a Comparator (as opposed to Comparable), then neither object can be trusted to be initialized and get/set should be used instead of direct access to instance fields on both objects. If you implement your Comparator as a separate class and your fields are private, the compiler will enforce this for you. But for Comparable and for Comparators implemented in the same class file as the object they are comparing, the compiler will NOT warn you, so you must be very careful.

Comparing Objects is Relative

This post is part of a series on Comparing Objects.

Equality

@djspiewak Ah. To me, universal equality is a failed experiment. Equality is always a contextual construct — the means as how to compare.

— Viktor Klang (@viktorklang) September 12, 2013

For those of us who are implementation minded, that means that boolean equals(Object other) is a flawed API because there is no one definition of equality that will work in every context. In a previous post on Using Java Collections Effectively by Implementing equals() and hashCode(), I quoted Josh Bloch and said that "The behavior of equals(), hashCode(), and compareTo() must be consistent." Java subtly encourages us to define a single definition of equality and comparison per class.

@runarorama Your mission, should you choose to accept it, is to ensure symmetry by only controlling one side of the relationship :)

— Hugues Chabot (@hugueschabot) March 14, 2014

Java programmers have been "ensuring symmetry by controlling only one side of the equation" for years. There's nothing wrong with defining a *default* context for comparison and equality.  Just don't mistake default equality and compareTo() as the only context for comparing objects.

A small potato and a slice of bread might have an equal number of calories (they are equivalent in one context), but the potato takes much more energy to heat up (they are different in another context). So Ideally, we'd like Heating equality and Caloric equality to be different for small potatoes vs. bread.

A context-relative definition of equality might look like this

boolean equals(Object left, Object right)

Hmm... equality and sorting have a good deal of overlap. The Comparator interface already defines something like equality - it returns 0 when things are sorted the same ("equally"), something else otherwise. Better still, any implementation of Comparator provides a context for that comparison.

interface Sugars {
    int gramsSugar();
    public static final Comparator<Sugars> COMPARATOR = (left, right) ->
            left.gramsSugar() - right.gramsSugar();
}

interface Heating {
    int cookingEnergy();
    public static final Comparator<Heating> COMPARATOR = (left, right) ->
            left.cookingEnergy() - right.cookingEnergy();
}

Could we use this for context-relative equality?

The ubiquitous ArrayList, Set, and Map use equals(), hashCode(), and compareTo() are all fixed in their one-sided ways. But the classes implementing SortedSet and SortedMap behave very differently from the other collections when passed a separate Comparator.

Using Context-Relative Equality (in Java)

When you pass a Comparator to TreeSet or TreeMap, you are using context-relative equality. All comparisons for get(), put(), and contains() are made with the Comparator NOT with the methods that the other standard collections use! With a little care you can use this to your advantage:

static class Food implements Heating, Sugars {
    private final int gramsSugar;
    private final int cookingEnergy;
    private Food(int g, int c) { gramsSugar = g; cookingEnergy = c; }
    @Override public int gramsSugar() { return gramsSugar; }
    @Override public int cookingEnergy() { return cookingEnergy; }
    @Override public String toString() {
        return "Food(" + gramsSugar + "," + cookingEnergy + ")";
    }
}

public static void main(String[] args) {
    List<Food> foods = Arrays.asList(new Food(5,3), new Food(4,4));
    SortedSet<Food> foodsByHeat = new TreeSet<>(Heating.COMPARATOR);
    foodsByHeat.addAll(foods);
    System.out.println("Foods by heat:");
    for (Food f : foodsByHeat) { System.out.println(f); }

    SortedSet<Food> foodsBySugar = new TreeSet<>(Sugars.COMPARATOR);
    foodsBySugar.addAll(foods);
    System.out.println("Foods by sugar:");
    for (Food f : foodsBySugar) { System.out.println(f); }
}

Output

Foods by heat:
Food(5,3)
Food(4,4)
Foods by sugar:
Food(4,4)
Food(5,3)

More

Here is the Source for the above.

Here is my earlier SetInterface test.

Object Mutability

This post is part of a series on Comparing Objects.

I've read a lot lately about making objects immutable whenever possible. "Programming in Scala" lists Immutable Object Tradeoffs as follows:

Advantages of Immutable Objects

1. Often easier to reason about because they do not have complex state.
2. Can be passed freely (without making defensive copies) to things that might try to modify them
3. Impossible for two threads accessing the same immutable object to corrupt it.
4. They make safe Hashtable keys (if you put a mutable object in a Hashtable, then change it in a way that changes its hashcode, the Hashtable will no longer be able to use it as a key because it will look for that object in the wrong bucket and not find it).

Disadvantages

1. Sometimes require a large object graph to be copied (to create a new, modified version of the object). This can cause performance and garbage collection bottlenecks.

For most purposes, an object representing a month can be made immutable - February 2003 will never become anything other than what it is. But a User record is not immutable. People get married or change their name for other reasons. Phone numbers, addresses, hair color, height, weight, and virtually every other aspect of a person can change. Yet the person is still the same person. This is what surrogate keys model in a database - that everything about a record can change, yet it can still be meaningfully the same record.

In order to use an object in a hash-backed Collection (in Java), its hashcode must NOT change. The simplest way to accomplish this is to make the hashcode of a mutable persistent object its surrogate key and to use that key as a primary comparison in the equals method as well (see my older post on Implementing equals(), hashcode(), and compareTo()).

To make an immutable object, you sometimes need a mutable constructor object, like StringBuilder and String. StringBuilder allows you to change your object as many times as you want, then get an immutable version by calling toString(). This is clean and safe, but has some small costs in time and memory (transforming the immutable StringBuilder into a new immutable String object, then throwing away the StringBuilder). An alternative that I have not seen much is to create an immutable interface, extend a mutable interface from it, and then extend your object from that.

Here's an example based on java.util.List. Pretend each interface or class is in its own file:

// All the immutable-friendly methods from java.util.List.
// Interfaces like these could easily be retrofitted into
// the existing Java collections framework
public interface ImmutableList {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean containsAll(Collection<?> c);
    boolean equals(Object o);
    int hashCode();
    E get(int index);
    int indexOf(Object o);
    int lastIndexOf(Object o);
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);
    List<E> subList(int fromIndex, int toIndex);
}

// This interface adds the mutators
public interface java.util.List extends ImmutableList {
    boolean add(E e);
    boolean remove(Object o);
    boolean addAll(Collection<? extends E> c);
    boolean addAll(int index, Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    boolean retainAll(Collection<?> c);
    void clear();
    E set(int index, E element);
    void add(int index, E element);
    E remove(int index);
}

public class java.util.ArrayList implements List {
    // just as it is now...
}

public class MyClass {
    someMethod(ImmutableList<String> ils) {
        // can't change the list
    }

    public static void main(String[] args) {
        List<String> myStrings = new ArrayList<String>();
        myStrings.add("hello");
        myStrings.add("world");
        someMethod(myStrings);
        // Totally safe:
        System.out.println(myStrings.get(1));
    }
}

This doesn't solve the problem of passing a list to existing untrusted code that might try to change it. It also doesn't prevent the calling code from modifying myStrings from a separate thread while someMethod() is working on it. But it does provide a way (going forward) for a method like someMethod() to declare that it cannot modify the list. The programmer of someMethod() cannot compile her code if she tries to modify the list (well, short of using reflection).

Guaranteed immutability can be critical in writing concurrent code and for keys in hashtables. Not all objects can be made immutable, but many of those objects have immutable surrogate keys that, if used properly, work around the pitfalls of mutability. Limiting mutability and avoiding common mutable object pitfalls can lead to fewer bugs, easier readability, and improved maintainability.

Using Java Collections Effectively by Implementing equals() and hashCode()

IMPORTANT: The techniques in this post, while interesting, are outdated and sub-optimal. In short, follow standard equals() and hashCode() practice, but TEST your classes using something like TestUtils. I find a bug almost every time I use that.

This post is the first in a series on Comparing Objects.

These three methods must be implemented correctly in order for the Java collections to work properly.  Even though popular IDEs automatically generate stubs of some of these methods, you should still understand how they work, particularly how the three methods work together because I don't see many IDE's writing meaningful compareTo() methods yet. For much of what follows, I am endebted to Joshua Bloch and his book, Effective Java. Buy it, read it, live it.

1. The behavior of equals(), hashCode(), and compareTo() must be consistent.
2. You must base these methods on fields whose values do not change while they are in a collection.

If you store an object in a collection (e.g. as a key in a HashMap) and it's hashcode changes, you generally won't be able to retrieve it from that hashtable anymore! Thanks to "Programming in Scala" Section 30.2 p. 657. See also my later post on Object Mutability. You can use collections effectively with mutable objects so long as those objects use surrogate keys. In these examples I store my surrogate key in a private long id field with public getId() and setId() methods as many popular frameworks expect.

hashCode()

hashCode() is meant to provide a very cheap "can-equal" test.  It allows the put() and contains() methods on hashtables to run blazingly fast.  In small hashtables, the low bits from hashCode() determine which hash bucket an object belongs in.  In larger hashtables, all the bits are used.  The (presumably more expensive) equals() test is then applied against all the other objects already in that bucket.  If you had all your objects return some number, say, 31 for their hashCode(), this would completely destroy the performance of any hashtable based collections, since all objects would go in the same hash bucket and each object would have to be compared to all other objects using equals().

Bloch's Item 9 states, "Always override hashCode() when you override equals()". The following are specifically required (see: Object.hashCode()):

1. x.hashCode() must always equal y.hashCode() when x.equals(y).
2. It's OK for x.hashCode() to equal y.hashCode() when x.equals(y) is false, but it's good to minimize this.

Truncating the database row number from a long to an int is an ideal way to ensure efficient, equal distribution of values. If you don't use surrogate keys, you need to construct an int from the "significant" fields (the ones that uniquely identify this object):

@Override
public int hashCode() {
    if (id == 0) {
        return intField1 + intField2 + objField3.hashCode();
    }
    // return (possibly truncated) surrogate key
    return (int) id;
}

If your object does not have a surrogate key, then the field-by-field comparison in this solution is correct, though not quite as fast. If you like playing with bits, you can sometimes or and shift various fields into your hashcode in a way that is very efficient and not too hard to read.

equals()

a.equals(b) should return true only when a and b represent the same object. Bloch (Item 8) says that the equals() method must be reflexive, symmetric, transitive and a few other things as well which I won't cover here. For any non-null value:

• x.equals(x) must be true.
• If x.equals(y) then y.equals(x) must be true.
• If x.equals(y) and y.equals(z) then x.equals(z) must also be true.

The following should get you off to a good start in writing an equals method that is all of the above.  Checking the hashCode() should be cheap and guarantees that two objects can't equal each other if their hashCodes are different.

@Override
public boolean equals(Object other) {
    // Cheapest operation first...
    if (this == other) { return true; }

    if ( (other == null) ||
         !(other instanceof MyClass) ||
         (this.hashCode() != other.hashCode()) ) {
        return false;
    }
    // Details...
    final MyClass that = (MyClass) other;

    // If this is a database object and both have the same surrogate key (id),
    // they are the same.
    if ( (id != 0) && (that.getId() != 0) ) {
        return (id == that.getId());
    }

    // If this is not a database object, compare significant fields here.
    // Return true only if they are all sufficiently the same.
    if (!this.getParent().equals(that.getParent())) {
        return false;
    }

    if (description == null) {
        if (that.getDescription() != null) {
            return false;
        }
    } else if (that.getDescription() == null) {
        return false;
    } else {
        // For each test, check and only return a non-zero result
        int ret = description.compareTo(that.getDescription());
        if (ret != 0) { return false; }
    }

    // Compare other fields
    // If all the same, return true
    return true;
}

Both objects must be valid before you compare them.  Your equals() method should either compare significant fields OR surrogate keys - not both! The danger of providing a field-by-field equals comparison for a database object is that it will work in some cases with invalid objects, but it not always.  This is a case where it's much better to fail fast, than to be scratching your head when an intermittent bug crops up in production. For database objects, using surrogate keys acknowledges that everything about an object can change over time, yet it is still essentially the same object (The Artist Formerly Known as Prince). For non-database objects, (including those that just haven't been given a surrogate key yet) you must compare individual fields.

With care, you can ensure consistency of equals() and compareTo() by defining one in terms of the other, but be careful not to create an infinite loop by defining them both in terms of each other!

Persistence/Hibernate

Persistence or communication frameworks create temporary surrogate objects in order to avoid fetching any extra objects from the database before they are needed.  Hibernate replaces a surrogate object with the actual object the first time a field other than id is accessed, or any methods other than persistent field accessors are accessed.  All of the above examples are designed to work with a persistence framework like Hibernate.

So your object can trust itself to be initialized inside equals(), hashcode(), and compareTo(). It should NOT trust that the other object being compared to is initialized! You can access the this.whatever fields directly, but always use that.getWhatever().

Scala's Case Classes

Declaring your class as a "case" class in Scala takes care of all the above items for you. It prevents inheritance, but for simple classes, it saves a ton of thought and typing! For non-case classes, you must do more work in Scala than in Java in order to support meaningful equals comparisons with inheritance. You have to implement a canEqual() method as well to support the idea that a parent class might think it was "close enough" to a child class, but the child might think they were different (because it defines extra fields relevant to the equals() method), so the child must implement canEqual() and the parent must check it in order to block the parent from thinking they are equal. I've never been bitten by this in Java, but I don't immediately see what prevents it.

Clojure

All Clojure's common built-in datatypes are immutable and implement the above methods for you, making them extremely easy to work with.

SerialVersionUID

I have not verified this, but it stands to reason that if you change hashCode() you probably need to update the SerialVersionUID just as you would if you changed any persistent field. Otherwise, you may end up with two of the same objects in a set (one with the old hashCode and one with the new). I'm not sure if this can happen in practice or not. Maybe someone will post test code in the comments that proves it one way or the other?

Using @Deprecated more liberally

I recently created a class and an interface for managing dates as just a month and year (ignoring the day) and called them YearMonth and YearMonthInterface. I then added comparison methods to YearMonth: greaterThan(YearMonthInterface x), lessThan(YearMonthInterface x), and equals(YearMonthInterface x). Do you see the problem?

equals() overrides Object.equals() and has a special significance for the Java Collections framework. According to the Java SE 6 spec, equals() must be reflexive, symmetric, transitive, and consistent, and x.equals(null) should return false. I had no way of knowing that any class that implemented the YearMonthInterface could satisfy those conditions. In fact, I already had one implementing class that could never satisfy symmetry: myYearMonth.equals(myOtherClass) would often not equal myOtherClass.equals(myYearMonth) because my other class was dependent on another object and could only be equal when its associated objects were also equal.

I decided to keep the YearMonth.equals(Object o) method as overriding Object.equals() so that YearMonth would work correctly with collections, but create a new method, YearMonth.equalTo(YearMonthInterface x), for manual comparisons. My concern was that I never wanted to mistakenly use equals() instead of equalTo(). The solution? Deprecate YearMonth.equals() and provide a comment suggesting the use of equalTo() instead. The compiler will now catch any attempt to use the wrong method and the collections framework can still use the equals() method without problem.

/**

This is deprecated because it does not compare YearMonthInterface objects,

rather it overrides Object's equals method.  It still works in

collections, but there should be no reason to ever call it directly.

Use equalTo() instead which really compares two YearMonthInterfaces as

you would expect, but doesn't need to be symmetric.



@param other another YearMonth (or it will return false).

@return true of the YearMonths are equal.

*/

@Deprecated

@Override

public boolean equals(Object other) {

   // Check address and null first for speedy return

   if (this == other) {

       return true;

   }

   if (other == null) {

        return false;

   }

   if ( !(other instanceof YearMonth) ) {

       return false;

   }

   final YearMonth that = (YearMonth) other;

   return (this.year == that.year) && (this.month == that.month);

}



public boolean equalTo(YearMonthInterface that) {

   // Check address and null first for speedy return

   if (this == that) {

       return true;

   }

   if (that == null) {

        return false;

   }

   return (this.year == that.getYear()) && (this.month == that.getMonth());

}

This technique would not work if I were to release this class to the public, but for a utility class with limited application, it can prevent me and my coworkers from making a simple but costly mistake.

For a full explanation of how to write a good equals() method, see Effective Java Second Edition by Joshua Bloch Chapter 3 (pp 35-36 is specifically about symmetry). I'm about half way through this book and really enjoying it.