How to add new member in ConcurrentHashMap> without synchronized or lock

Question

I've read question ConcurrentHashMap: avoid extra object creation with “putIfAbsent”. For ConcurrentHashMap<String, List<String>>, multiple threads will get-set the same list. Before values.add(value); get executed, entry may be removed and new member fail to be added. How to add new member in ConcurrentHashMap<String, List<String>> without synchronized or lock?

private ConcurrentHashMap<String, List<String>> entries =
                        new ConcurrentHashMap<String, List<String>>();

public void record(String key, String value) {
    List<String> values = entries.get(key);
    if (values == null) {
        values = Collections.synchronizedList(new ArrayList<String>());
        List<String> values2 = entries.putIfAbsent(key, values);
        if (values2 != null)
            values = values2;  
    }
    values.add(value); // entry may be removed here, and this member will lose.
}

use `computeIfAbsent` and `computeIfPresent` – Antoniossss May 21 '18 at 08:19 — Antoniossss, May 21 '18 at 08:19
@Antoniossss or even just plain `compute`. – Kayaman May 21 '18 at 08:22 — Kayaman, May 21 '18 at 08:22

Kayaman · Accepted Answer · 2018-05-21T09:13:14.113

4

The computeXXX methods are thread-safe (and atomic!), and prevent each other from messing things up. It's not completely lock-free, but it's a lot better than synchronizing by hand.

public void record(String key, String value) {
    entries.compute(key, (k, v) -> {
        List<String> vals = v;
        if(vals == null)
            vals = new ArrayList<>();
        vals.add(value);
        return vals;
    });
}

I made the list a regular ArrayList, since in the above code the compute should guarantee visibility. If other code is dependent on them being synchronizedLists, change accordingly (or rewrite the other code).

Example delete method:

public void delete(String key, String value) {
    entries.compute(key, (k, v) -> {
        List<String> vals = v;
        if(vals == null)
            return null; // No mapping, return null to keep the status quo

        vals.remove(value); // Or whatever you intend to do
        return vals.isEmpty() ? null : vals;
    });
}

edited May 21 '18 at 09:13

answered May 21 '18 at 08:34

Kayaman

72,141
5
83
121

If Java 8+. Otherwise, a lock-free solution seems impossible, since `record` must be atomic. – kagmole May 21 '18 at 08:40
@kagmole I don't provide solutions for obsolete Java versions. – Kayaman May 21 '18 at 08:42
@Kayaman I'm new to symbol `->` and have read docs about `compute()`. Can you show me the key code how to delete element in the list and delete the whole list if it's empty? – Hel May 21 '18 at 08:44
@Hel if you return `null` from `compute` it will remove the mapping. You can make a similar delete method that uses `compute`, removes an element from the list and then returns null if the list is empty, or the list itself if it still has elements in it. – Kayaman May 21 '18 at 08:47
@Kayaman Code can't be compiled. `compute()` should take 2 parameters. Am I missing sth? – Hel May 21 '18 at 09:09
@Hel my bad, it's missing the key parameter. There, fixed. – Kayaman May 21 '18 at 09:12
@Kayaman if I recall correctly synchronized would be used only when there is contention on non-empty bin – Eugene May 21 '18 at 10:30

How to add new member in ConcurrentHashMap> without synchronized or lock

1 Answers1