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

Question

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

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问题，原则上，如果您允许删除，这可能是相关的，这取决于您在这种情况下所需的语义。