modifying a ConcurrentHashMap and Synchronized ArrayList in same method

Question

I have a collection of objects that is modified by one thread and read by another (more specifically the EDT). I needed a solution that gave me fast look up and also fast indexing (by order inserted), so I'm using a ConcurrentHashMap with an accompanying ArrayList of the keys, so if want to index an entry, I can index the List for the key and then use the returned key to get the value from the hash map. So I have a wrapper class that makes sure when and entry is added, the mapping is added to the hash map and the key is added to the list at the same time, similarly for removal.

I'm posting an example of the code in question:

private List<K> keys = Collections.synchronizedList(new ArrayList<K>(INITIAL_CAPACITY));

private ConcurrentMap<K, T> entries = new ConcurrentHashMap<K, T>(INITIAL_CAPACITY, .75f);

public synchronized T getEntryAt(int index){
     return entries.get(keys.get(index));
}

**public synchronized void addOrReplaceEntry(K key, T value){
     T result = entries.get(key);
     if(result == null){
         entries.putIfAbsent(key, value);
         keys.add(key);
     }
     else{
         entries.replace(key, result);
     }
}**

public syncrhonized T removeEntry(K key, T value){
     keys.remove(key);
     entries.remove(key, value);
}

public synchronized int getSize(){
     return keys.size();
}

my question is: am I losing all the benefits of using the ConcurrentHashMap (over syncrhonized hashmap) by operating on it in synchronized methods? I have to synchronize the methods to safely modify/read from the ArrayList of keys (CopyOnWriteArrayList is not an option because a lot of modification happens...) Also, if you know of a better way to do this, that would be appreciated...

It might not be a good idea to use a synchronized collection in the EDT size the constant synchronization done in the background might slow down the GUI. (I'm not sure if it is something that is generally recommended to avoid... so comments from those who know better are welcomed.) — toto2
Also, using keys.remove(key) is O(n), you lose all your quick access by key advantage. — Paŭlo Ebermann
While lockless soloutions are often desirable, most applications just use some form of synchronization to allow EDT and background threads to share data in a safe manner. Obviously long operations that block the data structure are not desirable, e.g. locking it and then iterating over each element doing some slow maths. In such cases copying the data is preferable. — brain
@brain When you say "some form of synchronization" you mean using synchronized data type and not using SwingUtils.invokeLater? — toto2
remove happens very rarely... one thread gets objects over a socket connection, adds them to the collection (or replaces if they exist) a UI componenent uses the collection to display certain values (so for example get(index) is called on the edt. — sethro

brain brain · Accepted Answer · 2011-07-28T14:26:09

Yes, using a Concurrent collection and a Synchronized collection in only synchronized blocks is a waste. You wont get the benefits of ConcurrentHashMap because only one thread will be accesing it at a time.

You could have a look at this implementation of a concurrent linked hashmap, I havnt use it so can't attest to it's features.

One thing to consider would be to switching from synchronized blocks to a ReadWriteLock to improve concurrent read only performance.

I'm not really sure of the utility of proving a remove at index method, perhaps you could give some more details about the problem you are trying to solve?

modifying a ConcurrentHashMap and Synchronized ArrayList in same method

5 Answers