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

I have a Map. In order to update the key, I need to check if it already exists. Else, I need to create a new Object and put it.

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

My function is this

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

I do not want to use synchronization. I am guessing it can probably be transformed into Map<K,AtomicReference<Foo>> map = new ConcurrentHashMap<K, AtomicReference<Foo>>() and furthermore do value.compareAndSet(old, new) where value is type AtomicReference<Foo>. However, two things. How does the case of a non-existing key be handled? And how is the comparison done between the old and new Foo objects?

A common pattern in lock-free algorithms is to use an optimistic algorithm wrapped in a retry loop.

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;
        }
    }
}

Note that this algorithm doesn't protect against the A-B-A problem, which can in principle be relevant if you allow deletions, depending on your desired semantics in that case.