12

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.

7
  • Note: the contract of compareTo requires that it is consistent with equality. You can violate this contract if you are sure you know what you are doing; but it might have surprising effects. Dec 21, 2020 at 8:32
  • System::identityHashCode doesn't guarantee that non equal objects will have distinct hash codes. Hence your .compare will return 0 if and only if the objects are the same. requirement is not guaranteed to be satisfied.
    – Eran
    Dec 21, 2020 at 8:33
  • 2
    @AndyTurner: No, the contract doesn't require it to be consistent with equality. The documentation explicitly states that it doesn't have to be - but that when it's not consistent with equality, you may get odd results in some situations.
    – Jon Skeet
    Dec 21, 2020 at 8:33
  • I may be missing something but wouldn't using equals be more straight forward approach here? Comparisons are mostly for ordering objects, not for detecting equal objects. Dec 21, 2020 at 8:44
  • 2
    Try Guava’s Ordering.arbitrary() which will induce a total ordering among all unique objects. Dec 22, 2020 at 1:49

3 Answers 3

3

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.

10
  • Thanks, that's pretty much what I thought too, you'd need something like 4G messages in a time bin to get a collision, and that's even without the implementation trying to anti-correlate the hash values. But is there a reason why the guarantee is only partial? Is it too difficult to provide a full guarantee in a parallel context?
    – Just Me
    Dec 21, 2020 at 8:56
  • correction: I see identityHashCode returns a 32 bit int - so you only need a little over 64K messages in a time bin to get an expected collision, assuming random values.
    – Just Me
    Dec 21, 2020 at 9:13
  • 1
    @JustMe: Not sure what you mean by an "expected" collision, but I think the chances of a collision with 64K messages is still pretty small - and of course they're not random values, in that the implementation is trying to return unique values.
    – Jon Skeet
    Dec 21, 2020 at 9:29
  • 1
    @JustMe: Having tested this myself just now, I was wrong... admittedly using a 31-bit range rather than a 32-bit range, but with 64K samples, a random selection fails about 63% of the time. With 10,000 samples (and a 31-bit range) it fails 2.5% of the time. But I still think that with the additional "JVM is trying to make them unique" you'll be okay.
    – Jon Skeet
    Dec 21, 2020 at 9:46
  • 1
    @JustMe: Agreed that it's hard to be sure. Do you have stats about how many values you're likely to get with the same timestamp? (And any reason the timestamp is a float? That's an unusual way of timestamping.) Ultimately you'll probably want to test it hard on the JVM implementation you're planning on using.
    – Jon Skeet
    Dec 21, 2020 at 9:50
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)))
0

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.

1
  • Thanks! I think the Ordering.arbitrary() solution is similar to what you're suggesting, except messages are first compared using their identityHashCode and, only if that produces a hit, they get a assigned a unique id: stackoverflow.com/a/65405632/9398584 This should reduce contention on the global uid provider.
    – Just Me
    Dec 25, 2020 at 17:25

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.