Is this wrapper of LinkedHashMap thread safe? If not how can it become thread safe?

Question

I am attempting to implement a class with the following features by wrapping one of the built in Map classes.

1. Basic map functionality. (Only basic put, get, remove)
2. Can iterate over the values of the map in the order they were added. (as in LinkedHashMap)
3. Is thread safe.

Currently using a generic implementation but in the current use-case there will only ever be a handful of objects in the map. And additions/removal happen extremely infrequently - nominally additions occur only once.

Basically this one container should provide clients the ability to lookup a single Value object by Key AND/OR iterate through the Values (with order guarantee). In either case, the caller will likely be modifying the Value object, so it can't be read-only. Finally, callers may be coming from multiple threads.

This a minimized version of what I have right now:

public class MapWrapper<K, V> implements Iterable<V>
{
    private Map<K, V> map = new LinkedHashMap<K, V>();

    public void add(K key, V value)
    {
        // Does some other stuff

        synchronized (map)
        {
            map.put(key, value);
        }
    }

    public V get(K key)
    {
        V retVal;
        synchronized (map)
        {
            retVal = map.get(key);
        }
        return retVal;
    }

    @Override
    public Iterator<V> iterator()
    {
        List<V> values = new ArrayList<V>(map.values());
        return values.iterator();
    }
}

I feel like the iterator part is preventing this from being fully thread-safe. I see classes such as ConcurrentHashMap state that any client obtaining an iterator on the object MUST manually synchronize on the map object itself. Is there a way to make the code above thread-safe but still allow clients direct iterator access? Ie, I would like to be able to use a for-in loop, but I can not synchronize on the underlying map within MapWrapper.

MapWrapper<String, Object> test = new MapWrapper<String,Object>();
test.add("a", new Object());
test.add("c", new Object());
for (Object o: test) { o.setSomething(); } 

Answer 1

I believe the following solves the issue by keeping ordered and hashed references, while maintaining thread safety with minimal effort:

import java.util.Iterator;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

public class OrderedConcurrentHashMap<K, V> implements Iterable<V>
{
    private ConcurrentHashMap<K, V> map = new ConcurrentHashMap<>();
    private ConcurrentLinkedQueue<V> queue = new ConcurrentLinkedQueue<>();

    public void add(K key, V value)
    {
        map.put(key, value);
        queue.add(value);
    }

    public V get(K key)
    {
        return map.get(key);
    }

    public boolean remove(K key)
    {
        return queue.remove(map.remove(key));
    }

    @Override
    public Iterator<V> iterator()
    {
        return queue.iterator();
    }
}

Given the following from the OP:

• Only a handful of items
• Rarely will items be added or removed

This is probably an optimal solution using only built-in collections and concurrency utilities.

The remove method here can be modified according to behavior that clients expect; this simplest implementation is just a suggestion.

Of particular note from the ConcurrentLinkedQueue docs for Java 8:

Iterators are weakly consistent, returning elements reflecting the state of the queue at some point at or since the creation of the iterator. They do not throw ConcurrentModificationException, and may proceed concurrently with other operations. Elements contained in the queue since the creation of the iterator will be returned exactly once.

And:

This class and its iterator implement all of the optional methods of the Queue and Iterator interfaces.

Assuming that you ensure V is thread-safe, this wrapper collection should ensure container thread safety.

Another thing to keep in mind is that the java.util.concurrent collections are not null-tolerant (ConcurrentHashMap.put(k, v), ConcurrentLinkedQueue.add(v), ConcurrentHashMap.get(k)).

From the put(k, v) doc:

Throws: NullPointerException - if the specified key or value is null

From the add(v) doc:

Throws: NullPointerException - if the specified element is null

From the get(k) doc:

Throws: NullPointerException - if the specified key is null

I'm still thinking about how this would be handled. It seems that introducing nulls significantly complicates things (as it always does).

EDIT: After some research, I found this: https://stackoverflow.com/a/9298113

I did come up with an extension of the implementation I shared above that handles nulls, but I'd be uncomfortable regarding race conditions outside of an experimental setting.

Answer 2

Planning on taking advantage of

java.util.concurrent.ConcurrentSkipListMap

The "natural ordering" provided by the keys being used is sufficient.

Answer 3

I think this should work.

public class MapWrapper<K, V> implements Iterable<V> {
    private Map<K, V> map = new LinkedHashMap<K, V>();
    private int currentSize = 0;

    public void add(K key, V value) {
        // Does some other stuff

        synchronized (map) {
            map.put(key, value);
            currentSize++;
        }
    }

    public V get(K key) {
        V retVal;
        synchronized (map) {
            retVal = map.get(key);
            currentSize--;
        }
        return retVal;
    }

    @Override
    public Iterator<V> iterator() {
        return new SyncIterator();
    }

    // Inner class example
    private class SyncIterator implements Iterator<V> {

        private int currentIndex = 0;

        @Override
        public boolean hasNext() {
            return currentIndex < currentSize;
        }

        @Override
        public V next() {

            synchronized (map) {

                List<V> values = new ArrayList<V>(map.values());
                return values.get(currentIndex++);
            }
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}