使用无锁算法将值放入自定义对象的 Map 中

Question

我有一张地图。为了更新密钥，我需要检查它是否已经存在。否则，我需要创建一个新对象并将其放入。

Map<K,Foo> map = new ConcurrentHashMap<K, Foo>();

我的功能是这样的

put(Object value)  {
   if(!map.containsKey(K key)) {
       map.put(key, new Foo());
   } else {
       Foo modifiedFoo = modifyFoo(map.get(key));
       map.put(key, modifiedFoo));
   }
}

我不想使用同步。我猜它可能会被转换成 Map<K,AtomicReference<Foo>> map = new ConcurrentHashMap<K, AtomicReference<Foo>>() 并且进一步做 value.compareAndSet(old, new) 其中 value 是类型 AtomicReference<Foo>。然而，有两件事。如何处理不存在的密钥？新旧 Foo 对象是如何进行比较的？

Answer 1

无锁算法中的一个常见模式是使用包裹在重试循环中的乐观算法。

insertOrUpdate(key) {
    while(true) {
        var foo = map.get(key);
        if (foo == null) {
            if (map.putIfAbsent(key, new Foo())) break;
        } else {
            if (map.replace(key, foo, modifyFoo(foo))) break;
        }
    }
}

请注意，此算法无法防止 A-B-A problem，如果您允许删除，原则上这可能是相关的，具体取决于您在这种情况下所需的语义。

使用无锁算法将值放入自定义对象的 Map 中

Using lock-free algorithm to put values into a Map of custom objects

java

nonblocking

lock-free

atomicreference