Can I use identityHashCode to produce a compareTo between Objects respecting same-ness?

Question

I want to implement a simple comparator between two Objects, whose only requirements are that

1. it is a valid comparator (i.e. defines a linear order on all objects) and
2. .compare will return 0 if and only if the objects are the same.

Will Comparator.comparing(System::identityHashCode) work? Is there another way?

Motivation: I want to build a collection that will allow me to store time-stamped messages in a thread-safe collection, which will support queries like "get me all the messages whose timestamp lies in [a,b)".

It seems that Guava's TreeMultimap uses a global lock (edit: if wrapped with the synchronizedSortedSetMultimap wrapper), and ConcurrentSkipListMap seems to support only one entry per time (it is a map, not a multi map). So I thought of using just a set of pairs:

ConcurrentSkipListSet<ImmutablePair<Float,Message>> db,

where the pairs are lexically ordered, first by the times (using Float.compareTo) and then by something like Comparator.nullsFirst(Comparator.comparing(System::identityHashCode)).

• The nullsFirst is there just so db.subSet(ImmutablePair.of(a,null), ImmutablePair.of(b,null)) queries the half-open time interval [a,b).

• You see why I care about the comparator preserving sameness: if the message comparator returns zero for non-same messages, messages may be deleted.

• You also see why I don't need much else from the comparator: it's just there so I can use the storage mechanism of ConcurrentSkipListSet. I certainly don't want to impose on the user (well, just me :-) to implement a comparator for Message.

• Another possible solution is to use a ConcurrentSkipListMap<Float, Set<Message>> (with thread-safe Set<> instances) but it seems a bit wasteful in terms of memory, and I will need to remove emptySet's myself to save memory once messages are deleted.

EDIT: As several people noted, identityHashCode may produce collisions, and in fact I've now confirmed that such collisions exist in my setup (which is roughly equivalent to having 4K collections as above, each populated with 4K messages per time bin). This is most likely the reason I see some messages dropped. So I'm now even more interested than ever in finding some way to have an "agnostic" comparison operator, that truly respects sameness. Actually, a 64 bit hash value (instead of the 32bit value provided by identityHashCode) would probably suffice.

Answer 1

As @StuartMarks noted in his comment, Guava supports Ordering.arbitrary(), which provides thread-safe collision handling. The implementation makes an efficient use of identityHashCode:

@Override
public int compare(Object left, Object right) {
  if (left == right) {
    return 0;
  } else if (left == null) {
    return -1;
  } else if (right == null) {
    return 1;
  }
  int leftCode = identityHashCode(left);
  int rightCode = identityHashCode(right);
  if (leftCode != rightCode) {
    return leftCode < rightCode ? -1 : 1;
  }

  // identityHashCode collision (rare, but not as rare as you'd think)
  int result = getUid(left).compareTo(getUid(right));
  if (result == 0) {
    throw new AssertionError(); // extremely, extremely unlikely.
  }
  return result;
}

so only if there is a hash collision, getUid (which uses a memoized AtomicInteger counter to allocate uid's) is invoked.

It's also quite easy to write (perhaps less easy to read?) the desired timestamped message container in "one" line:

db = new ConcurrentSkipListSet<>(
                (Ordering.<Float>natural().<ImmutablePair<Float,Message>>onResultOf(x -> x.left))
                        .compound(Ordering.arbitrary().nullsFirst().<ImmutablePair<Float,Message>>onResultOf(x -> x.right)))

Answer 2

While it's not guaranteed, I suspect the chances of this causing a problem are vanishingly small.

System.identityHashCode returns the value that Object.hashCode would return if not overridden, including this in the documentation:

As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects.

So is "as much as is reasonably practical" sufficient? While it's not guaranteed, I would be very surprised if you ever ran into a situation where it causes a problem. You'd have to have two messages with exactly the same timestamp and where the JVM's Object.hashCode implementation returns the same value for the two messages.

If the result of that coincidence were to be "nuclear power plant explodes" then I wouldn't risk it. If the result of that coincidence were to be "we fail to bill a customer" - or even "we bill a customer twice, and might get sued" I'd probably accept that chance, if no better alternatives are suggested.

Answer 3

Will Comparator.comparing(System::identityHashCode) work? Is there another way?

As mentioned, identityHashCode is not unique.

Actually, a 64 bit hash value (instead of the 32bit value provided by identityHashCode) would probably suffice

I think this would just be reducing the chances of overlap, not removing them. Hash algorithems are designed to limit overlaps but typically have no guarantees about none. For example, MD5 is 128 bit and still has overlaps.

How about just assigning a unique number to each message with AtomicLong. Then your comparison function would do:

1. Compare by time. I would use long if possible instead of float.
2. If same time then compare by the unique value.

If you have multiple systems doing the ingesting of these messages then you are going to need to record unique system-id and message number to ensure uniqueness.