12

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

  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.

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

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

4

3 回答 3

3

虽然不能保证，但我怀疑这导致问题的可能性微乎其微。

System.identityHashCodeObject.hashCode返回如果不被覆盖将返回的值，包括在文档中：

在合理可行的情况下，由 Object 类定义的 hashCode 方法确实为不同的对象返回不同的整数。

那么“尽可能多的合理实用”就足够了吗？虽然不能保证，但如果您遇到导致问题的情况，我会感到非常惊讶。您必须有两条消息具有完全相同的时间戳，并且JVM 的Object.hashCode实现为两条消息返回相同的值。

如果这个巧合的结果是“核电站爆炸”，那我不会冒险。如果这种巧合的结果是“我们未能向客户收费”——或者甚至“我们向客户收费两次，可能会被起诉”，如果没有提出更好的替代方案，我可能会接受这个机会。

于 2020-12-21T08:38:04.447 回答
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）才会被调用。

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

db = new ConcurrentSkipListSet<>(
                (Ordering.<Float>natural().<ImmutablePair<Float,Message>>onResultOf(x -> x.left))
                        .compound(Ordering.arbitrary().nullsFirst().<ImmutablePair<Float,Message>>onResultOf(x -> x.right)))
于 2020-12-22T08:47:15.087 回答
0

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

如前所述，identityHashCode 不是唯一的。

实际上，一个 64 位哈希值（而不是 identityHashCode 提供的 32 位值）可能就足够了

我认为这只会减少重叠的机会，而不是消除它们。哈希算法旨在限制重叠，但通常不能保证没有。例如，MD5 是 128 位，仍然有重叠。

AtomicLong使用.为每条消息分配一个唯一编号怎么样？然后你的比较函数会做：

  1. 按时间比较。如果可能的话，我会使用 long 而不是 float。
  2. 如果同一时间，则按唯一值进行比较。

如果您有多个系统来摄取这些消息，那么您将需要记录唯一的系统 ID 和消息编号以确保唯一性。

于 2020-12-22T18:57:40.913 回答