无法将同等优先级的对象插入 ConcurrentSkipListSet

Question

我在使用 ConcurrentSkipListSet 来处理插入期间跟踪观察者优先级的观察者模式的简单线程安全实现时遇到问题。大多数观察者不会被赋予任何特殊优先级，并且遵循此 Comparable#compareTo 方法将在比较时显示为同等优先级（其中 priority 是五个优先级枚举中的一个值从最高到最低）：

public int compareTo(BaseLink<?> link) {
    return this.priority.compareTo(link.getPriority());
}

当我将同等优先级的观察者添加到 ConcurrentSkipListSet 时，似乎一些添加的对象在插入过程中丢失了。更改我在测试时创建的任何观察者的优先级会导致这些观察者毫无问题地添加到集合中，但我假设如果有足够多的相同优先级的观察者，问题将再次出现。

我不确定是什么导致了这个问题，也不确定我应该做些什么来帮助解决它。我能做些什么来解决这个问题吗？或者，如果这是 ConcurrentSkipListSet 的固有问题，是否有任何其他线程安全数据结构可以为唯一对象提供合理的性能插入和排序时间？

Answer 1

我假设您正在像这样实例化 ConcurrentSkipListSet(myComparator) 其中 myComparator 实现 compareTo 正如您向我们展示的那样。

一个ConcurrentSkipListSet是一个Set。当您使用 Comparator 实例化一个时，它将用于：

对集合元素进行排序
确定新元素何时已在集合中。

在您的代码中，您的 Comparator.compareTo(...) 表示每个具有给定优先级的 BaseLink 都是相同的。这就是导致您出现问题的原因。

解决方案：

public int compareTo(BaseLink<?> link) {
    int res = this.priority.compareTo(link.getPriority());
    if (res == 0) {
        // tie-breaker for different links with the same priority
        res = // compare using some other key / identifier
    }
    return res;
}

如果您的 BaseLink 对象具有自然键或标识符，您可以将其用作具有相同优先级的对象的决胜局。即使对象的身份哈希码也可以……如果您不担心集合的排序中的 "fairness" 或 "reproducibility"。

无法将同等优先级的对象插入 ConcurrentSkipListSet

Unable to insert objects of equal priority into ConcurrentSkipListSet

java

multithreading

sorting

comparator

observer-pattern