map 方法中的线程安全“如果更大则放置”

Question

我有一个

ConcurrentMap<Key, Long>

，它是从某个键到迄今为止所看到的最大值的缓存。如果两个值同时出现，我想确保将较大的值插入到地图中。最干净的方法是什么？

一种丑陋的方法是用

LargestLong

方法编写一个类

UpdateIfBigger

，这可能会涉及一些 CAS 循环。我没有找到直接在

ConcurrentHashMap

上执行此类 CAS 循环的方法。

或者在检索后使用

ConcurrentMap<Key, AtomicLong>

和 CAS 循环。我听说对这样的原子原语使用并发集合通常是设计缺陷的迹象，但这可能是一个例外。

Answer 1

最好的方法是使用 AtomicLong。您将获得当前值，如果它大于尝试替换它，如果失败再试一次。

ConcurrentMap<Key, AtomicLong> map = new ConcurrentHashMap<>();

public static boolean putIfGreater(Key key, long value){
     // assuming it's never null at this point
     AtomicLong val = map.get(key);
     long current = val.get();

     for(;;){
        if(value < current)
             return false;
        if(val.compareAndSet(current, value))
             return true;
         current = val.get();
     }
     return false;
}

在这种情况下，它首先检查它是否更大，如果是，它会尝试设置它。如果它无法设置它（另一个线程击败了该线程），那么它将再次尝试 IFF 它大于更新的值。

我听说使用并发通常是设计缺陷的标志 针对像这样的原子原语的集合，但这可能是一个 例外。

如果你的选择是使用锁，在这种情况下我倾向于不同意。如果您有该论点的任何链接，我将很乐意阅读它。

Answer 2

理想情况下，您应该从一个简单的同步块开始，确定它确实创建了瓶颈，然后尝试使其无锁。也许更复杂的解决方案不值得付出努力，或者您在其他地方遇到瓶颈？

John 的解决方案似乎更快，但是，如果这是程序的关键部分，您可能还想测试以下内容（仅使用 ConcurrentMap 的原子方法）：

ConcurrentMap<Key, Long> map = new ConcurrentHashMap<>();

public boolean putIfGreater(Key key, long value) {
    Long boxedValue = Long.valueOf(value);
    Long current = map.putIfAbsent(key, boxedValue);
    if (current == null) {
        return true;
    } else {
        while (true) {
            if (value < current) {
                return false;
            }
            if (map.replace(key, current, boxedValue)) {
                return true;
            }
            current = map.get(key);
        }
    }
}

Answer 3

那

map.merge(key, value, Long::max)

呢？

如果指定的键尚未与值关联或与 null 关联，则将其与给定的非 null 值关联。否则，用给定重映射函数的结果替换关联值，或者如果结果为空则删除。当组合一个键的多个映射值时，可以使用此方法。

给定

ConcurrentMap

，您可以假设这是线程安全的。

默认实现不保证此方法的同步或原子性属性。任何提供原子性保证的实现都必须重写此方法并记录其并发属性。特别是，子接口 ConcurrentMap 的所有实现都必须记录重映射函数是否仅在值不存在时原子应用一次。

但是假设您使用

ConcurrentHashMap

，那么：

整个方法调用都是原子执行的。

Answer 4

我认为这里的关键点是“同时”这个词。不会在完全相同的时间插入任何值。

我将创建第二个线程和一个收集所有传入数据的 ConcurrentSet，该线程将从 Set 中选取最大值并将值插入到缓存中。

因为不存在完全相同的时间，所以您只能通过以固定时间速率观察传入数据来优化它们。