java - 使用无锁算法将值放入自定义对象的 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)where valueis type 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;
        }
    }
}

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