I want to implement a simple comparator between two Objects, whose only requirements are that
.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.
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)))