Java Map synchronization

Question

I'm working on something where I have a Collections.synchronizedMap defined.

In one thread A, it will just get the value, and put an updated value so it is not a problem.

In another thread B, it will iterate through the entries and then based on the values of an entry, do some comparisons, and if it matches some condition, it will delete that entry from the map.

My understanding is that a synchronized Map will block access.

But is it possible that thread B gets an entry, then thread A updates the value, and then thread B deletes the value because it matches some condition, but it shouldn't have because of the value thread A updated it to. And what would be the best implementation to work around this?

you can lock the critic section and avoid problems – Marco Acierno Jan 28 '14 at 21:08 — Marco Acierno, Jan 28 '14 at 21:08

score 3 · Answer 1 · answered Jan 28 '14 at 21:08

It sounds like you just need to synchronize the "fetch, check and delete" part. For example:

Iterable<String> keys;
synchronized (map) {
    keys = new ArrayList<>(map.keySet());
}
for (String key : keys) {
    synchronized (map) {
        Integer value = map.get(key);
        // The other thread won't be able to update the value at this point
        if (value != null && value < 0) {
            map.remove(key);
        }
    }
}

Your updating thread may need to do the same thing - it's unclear from your description whether it needs to "see" the deletion.

score 2 · Answer 2 · edited May 23 '17 at 12:11

2

You need to synchronize the block of code that you are using the map as well.

Take a look here: Java synchronized block vs. Collections.synchronizedMap

edited May 23 '17 at 12:11

Community

1
1

answered Jan 28 '14 at 21:08

Eduardo Briguenti Vieira

4,351
3
37
49

score 1 · Answer 3 · answered Jan 28 '14 at 22:40

This can be done entirely without blocking using a ConcurrentHashMap like this:

final ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>(); // creation
map.put("aKey", "aValue"); // example content

// Thread A:
map.replace("aKey", "aNewValue"); // atomic replace call

// Thread B:
for (String key : map.keySet()) {
  do {
    processed = true;
    final String value = map.get(key);
    if ((value != null) && shouldRemove(value)) { // some comparison or check
      if (map.remove("aKey", value) == false) { // is value still the same?
        processed = false; // value has been changed in between, try again
      }
    }
  } while (processed == false);
}

This is thread-safe because Thread B only removes the value (atomically), if it has not been changed in between. If it did change in between, Thread B will try again and compare using the new value. This is similar to the concept of compareAndSet used in other Atomic-classes.

If Thread A does change rarely, Thread B will execute almost the same speed as an unsynchronized map. If Thread A does a lot of changes, there can be several repeated calls in Thread B, depending on how long it takes to do the comparison and how often the value will change. But under all cases this will be thread-safe and faster than any synchronized implementation.

score 0 · Answer 4 · answered Jan 28 '14 at 21:23

0

It sounds like you are trying to implement a cache. There are many good concurrent cache implementations out there. I believe guava has a pretty decent implementation.

answered Jan 28 '14 at 21:23

jtahlborn

52,909
5
76
118

score 0 · Answer 5 · answered Feb 28 '14 at 01:55

First about solution. I think best solution is standard ConcurrentHashMap. It has CAS operation for remove as below:

boolean remove(Object key, Object value)
Removes the entry for a key only if currently mapped to a given value.

Hope it helps.

Now second thing is about "My understanding is that a synchronized Map will block access." which i don't think is complete understanding as see the below details of Synchronized map javadoc:

* It is imperative that the user manually synchronize on the returned
 * map when iterating over any of its collection views:
 * <pre>
 *  Map m = Collections.synchronizedMap(new HashMap());
 *      ...
 *  Set s = m.keySet();  // Needn't be in synchronized block
 *      ...
 *  synchronized (m) {  // Synchronizing on m, not s!
 *      Iterator i = s.iterator(); // Must be in synchronized block
 *      while (i.hasNext())
 *          foo(i.next());
 *  }
 * </pre>

Java Map synchronization

5 Answers5