javacomparatorjava.util.concurrentskip-listsconcurrentskiplistmap

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


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)).

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.


Solution

  • 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)))