我可以使用 identityHashCode 在尊重相同性的对象之间生成 compareTo 吗？

Question

我想在两个对象之间实现一个简单的比较器，它的唯一要求是

1. 它是一个有效的比较器（即定义所有对象的线性顺序）和
2. .compare当且仅当对象相同时才返回 0 。

会Comparator.comparing(System::identityHashCode)工作吗？还有其他方法吗？

动机： 我想构建一个集合，允许我将时间戳消息存储在线程安全集合中，该集合将支持诸如“获取时间戳位于 [a,b) 中的所有消息”之类的查询。

似乎番石榴TreeMultimap使用全局锁（编辑：如果用synchronizedSortedSetMultimap包装器包装），并且ConcurrentSkipListMap似乎每次只支持一个条目（它是一张地图，而不是多张地图）。所以我想只使用一组对：

ConcurrentSkipListSet<ImmutablePair<Float,Message>> db,

其中对按词法排序，首先按时间（使用Float.compareTo），然后按类似Comparator.nullsFirst(Comparator.comparing(System::identityHashCode)).

• 的nullsFirst是有只是让db.subSet(ImmutablePair.of(a,null), ImmutablePair.of(b,null))查询半开时间区间[a，b）中。

• 你明白为什么我关心比较器保持相同性：如果消息比较器对不相同的消息返回零，消息可能会被删除。

• 你也明白了为什么我不需要比较器的其他东西：它就在那里，所以我可以使用ConcurrentSkipListSet. 我当然不想强加于用户（好吧，只是我 :-) 为Message.

• 另一种可能的解决方案是使用 a ConcurrentSkipListMap<Float, Set<Message>>（带有线程安全的 Set<> 实例），但在内存方面似乎有点浪费，一旦消息被删除，我需要自己删除 emptySet 以节省内存。

编辑：正如一些人所指出的，identityHashCode 可能会产生冲突，实际上我现在已经确认在我的设置中存在这种冲突（大致相当于上面的 4K 集合，每个集合每个时间段填充 4K 消息）。这很可能是我看到一些消息丢失的原因。所以我现在比以往任何时候都更有兴趣找到某种方法来拥有一个真正尊重相同性的“不可知”比较运算符。实际上，64 位哈希值（而不是 identityHashCode 提供的 32 位值）可能就足够了。

Answer 1

正如 @StuartMarks 在他的评论中指出的，Guava 支持 Ordering.arbitrary()，它提供了线程安全的碰撞处理。该实现有效地利用了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;
}

因此，仅当存在哈希冲突时getUid（使用记忆的 AtomicInteger 计数器来分配 uid）才会被调用。

在“一行”中编写所需的带时间戳的消息容器也很容易（也许不太容易阅读？）：

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