Java Null Object that is used in Hash Tables and Comparables

Question

I have an object that represents an UNKNOWN value, or "Null object".

As in SQL, this object should never be equal to anything, including another UNKNOWN, so (UNKNOWN == UNKNOWN) -> false.

The object is used, however, in hashtables and the type is Comparable, so I created a class as follows:

public class Tag implements Comparable {    
  final static UNKNOWN = new Tag("UNKNOWN");
  String id;

  public Tag(String id) { 
    this.id = id; 
  }

  public int hashCode(){
    return id.hashCode();
  }

  public String toString(){
    return id;
  }

  public boolean equals(Object o){    
    if (this == UNKNOWN || o == UNKNOWN || o == null || !(o instanceof Tag))
      return false;

    return this.id.equals(((Tag)o).id);
  }

  public int compareTo(Tag o){
    if (this == UNKNOWN)
      return -1;
    if (o == UNKNOWN || o == null)
      return 1;

    return this.id.compareTo(o.id);
  }
}

But now compareTo() seems "inconsistent"?

Is there a better way to implement compareTo()?

Answer 1

The simple answer is: you shouldn't.

You have contradiction requirements here. Either your tag objects have an implicit order (that is what Comparable expresses) OR you can have such "special" values that are not equal to anything, not even themselves.

As the other excellent answer and the comments point out: yes, you can somehow get there; for example by simply allowing for a.compare(b) < 0 and b.compare(a) < 0 at the same time; or by throwing an exception.

But I would simply be really careful about this. You are breaking a well established contract. And the fact that some javadoc says: "breaking the contract is OK" is not the point - breaking that contract means that all the people working on this project have to understand this detail.

Coming from there: you could go forward and simply throw an exception within compareTo() if a or b are UNKNOWN; by doing so you make at least clear that one shouldn't try to sort() a List<Tag> for example. But hey, wait - how would you find out that UNKNOWN is present in your list? Because, you know, UNKNOWN.equals(UNKNOWN) returns false; and contains() is using equals.

In essence: while technically possible, this approach causes breakages wherever you go. Meaning: the fact that SQL supports this concept doesn't mean that you should force something similar into your java code. As said: this idea is very much "off standards"; and is prone to surprise anybody looking at it. Aka "unexpected behavior" aka bugs.

Answer 2

You're correct that your compareTo() method is now inconsistent. It violates several of the requirements for this method. The compareTo() method must provide a total order over the values in the domain. In particular, as mentioned in the comments, a.compareTo(b) < 0 must imply that b.compareTo(a) > 0. Also, a.compareTo(a) == 0 must be true for every value.

If your compareTo() method doesn't fulfil these requirements, then various pieces of the API will break. For example, if you sort a list containing an UNKNOWN value, then you might get the dreaded "Comparison method violates its general contract!" exception.

How does this square with the SQL requirement that null values aren't equal to each other?

For SQL, the answer is that it bends its own rules somewhat. There is a section in the Wikipedia article you cited that covers the behavior of things like grouping and sorting in the presence of null. While null values aren't considered equal to each other, they are also considered "not distinct" from each other, which allows GROUP BY to group them together. (I detect some specification weasel wording here.) For sorting, SQL requires ORDER BY clauses to have additional NULLS FIRST or NULLS LAST in order for sorting with nulls to proceed.

So how does Java deal with IEEE 754 NaN which has similar properties? The result of any comparison operator applied to NaN is false. In particular, NaN == NaN is false. This would seem to make it impossible to sort floating point values, or to use them as keys in maps. It turns out that Java has its own set of special cases. If you look at the specifications for Double.compareTo() and Double.equals(), they have special cases that cover exactly these situations. Specifically,

Double.NaN == Double.NaN // false

Double.valueOf(Double.NaN).equals(Double.NaN) // true!

Also, Double.compareTo() is specified so that it considers NaN equal to itself (it is consistent with equals) and NaN is considered larger than every other double value including POSITIVE_INFINITY.

There is also a utility method Double.compare(double, double) that compares two primitive double values using these same semantics.

These special cases let Java sorting, maps, and so forth work perfectly well with Double values, even though this violates IEEE 754. (But note that primitive double values do conform to IEEE 754.)

How should this apply to your Tag class and its UNKNOWN value? I don't think you need to follow SQL's rules for null here. If you're using Tag instances in Java data structures and with Java class libraries, you'd better make it conform to the requirements of the compareTo() and equals() methods. I'd suggest making UNKNOWN equal to itself, to have compareTo() be consistent with equals, and to define some canonical sort order for UNKNOWN values. Usually this means sorting it higher than or lower than every other value. Doing this isn't terribly difficult, but it can be subtle. You need to pay attention to all the rules of compareTo().

The equals() method might look something like this. Fairly conventional:

public boolean equals(Object obj) {
    if (this == obj) {
        return true;
    }

    return obj instanceof Tag && id.equals(((Tag)obj).id);
}

Once you have this, then you'd write compareTo() in a way that relies on equals(). (That's how you get the consistency.) Then, special-case the unknown values on the left or right-hand sides, and finally delegate to comparison of the id field:

public int compareTo(Tag o) {
    if (this.equals(o)) {
        return 0;
    }

    if (this.equals(UNKNOWN)) {
        return -1;
    }

    if (o.equals(UNKNOWN)) {
        return 1;
    }

    return id.compareTo(o.id);
}

I'd recommend implementing equals(), so that you can do things like filter UNKNOWN values of a stream, store it in collections, and so forth. Once you've done that, there's no reason not to make compareTo consistent with equals. I wouldn't throw any exceptions here, since that will just make standard libraries hard to use.

Answer 3

A couple seconds of critical thinking:

There is already a null in Java and you can not use it as a key for a reason.

If you try and use a key that is not equal to anything else including itself you can NEVER retrieve the value associated with that key!

Answer 4

The documentation for compareTo mentions this situation:

It is strongly recommended, but not strictly required that

(x.compareTo(y)==0) == (x.equals(y))

Generally speaking, any class that implements the Comparable interface and violates this condition should clearly indicate this fact. The recommended language is "Note: this class has a natural ordering that is inconsistent with equals."

Therefore, if you want your object to be Comparable and yet still not allow two UNKNOWN objects to be equal via the equals method, you must make your compareTo "Inconsistent with equals."

An appropriate implementation would be:

public int compareTo(Tag t) {
    return this.id.compareTo(t.id);
}

Otherwise, you could make it explicit that UNKNOWN values in particular are not Comparable:

public static boolean isUnknown(Tag t) {
    return t == UNKNOWN || (t != null && "UNKNOWN".equals(t.id));
}

public int compareTo(Tag t) {
    if (isUnknown(this) || isUnknown(t)) {
        throw new IllegalStateException("UNKNOWN is not Comparable");
    }
    return this.id.compareTo(t.id);
}