Does java have a "LinkedConcurrentHashMap" data structure ?

Question

I need a data structure that is a LinkedHashMap and is thread safe.

How can I do that ?

Answer 1

Collections.synchronizedMap(new LinkedHashMap())

Answer 2

You can use a LinkedHashMap and surround the calls to it with a synchronized block. For example:

Map<X,Y> map = new LinkedHashMap<X,Y>();
synchronized(map) {
  map.put(new X(), new Y());
}

Answer 3

You can wrap the map in a Collections.synchronizedMap to get a synchronized hashmap that maintains insertion order. This is not as efficient as a ConcurrentHashMap (and doesn't implement the extra interface methods of ConcurrentMap) but it does get you the (somewhat) thread safe behavior.

Even the mighty Google Collections doesn't appear to have solved this particular problem yet. However, there is one project that does try to tackle the problem.

I say somewhat on the synchronization, because iteration is still not thread safe in the sense that concurrent modification exceptions can happen.

Answer 4

You should check out the java.util.concurrent -package. It contains implementations of thread-safe maps and queues and other handy concurrency stuff.

Also, if you choose to use the Collection.synchronizedMap -method then be sure to read the API documentation. You should never use the map you've synchronized through reference to the original map and traversing the map should be synchronized manually using a synchronized block or some other construct.

Answer 5

Since the ConcurrentHashMap offers a few important extra methods that are not in the Map interface, simply wrapping a LinkedHashMap with a synchronizedMap won't give you the same functionality, in particular, they won't give you anything like the putIfAbsent(), replace(key, oldValue, newValue) and remove(key, oldValue) methods which make the ConcurrentHashMap so useful.

Unless there's some apache library that has implemented what you want, you'll probably have to use a LinkedHashMap and provide suitable synchronized{} blocks of your own.

Answer 6

The answer is pretty much no, there's nothing equivalent to a ConcurrentHashMap that is sorted (like the LinkedHashMap). As other people pointed out, you can wrap your collection using Collections.synchronizedMap(-yourmap-) however this will not give you the same level of fine grained locking. It will simply block the entire map on every operation.

Your best bet is to either use synchronized around any access to the map (where it matters, of course. You may not care about dirty reads, for example) or to write a wrapper around the map that determines when it should or should not lock.

Answer 7

There's a number of different approaches to this problem. You could use:

Collections.synchronizedMap(new LinkedHashMap());

as the other responses have suggested but this has several gotchas you'll need to be aware of. Most notably is that you will often need to hold the collections synchronized lock when iterating over the collection, which in turn prevents other threads from accessing the collection until you've completed iterating over it. (See Java theory and practice: Concurrent collections classes). For example:

synchronized(map) {
    for (Object obj: map) {
        // Do work here
    }
}

Using

new ConcurrentHashMap();

is probably a better choice as you won't need to lock the collection to iterate over it.

Finally, you might want to consider a more functional programming approach. That is you could consider the map as essentially immutable. Instead of adding to an existing Map, you would create a new one that contains the contents of the old map plus the new addition. This sounds pretty bizarre at first, but it is actually the way Scala deals with concurrency and collections

Answer 8

There is one implementation available under Google code. A quote from their site:

A high performance version of java.util.LinkedHashMap for use as a software cache.

Design

• A concurrent linked list runs through a ConcurrentHashMap to provide eviction ordering.
• Supports insertion and access ordered eviction policies (FIFO, LRU, and Second Chance).

Answer 9

You can use a ConcurrentSkipListMap, only available in Java SE/EE 6 or later. It is order presevering in that keys are sorted according to their natural ordering. You need to have a Comparator or make the keys Comparable objects. In order to mimik a linked hash map behavior (iteration order is the order in time in which entries were added) I implemented my key objects to always compare to be greater than a given other object unless it is equal (whatever that is for your object). A wrapped synchronized linked hash map did not suffice because as stated in http://www.ibm.com/developerworks/java/library/j-jtp07233.html: "The synchronized collections wrappers, synchronizedMap and synchronizedList, are sometimes called conditionally thread-safe -- all individual operations are thread-safe, but sequences of operations where the control flow depends on the results of previous operations may be subject to data races. The first snippet in Listing 1 shows the common put-if-absent idiom -- if an entry does not already exist in the Map, add it. Unfortunately, as written, it is possible for another thread to insert a value with the same key between the time the containsKey() method returns and the time the put() method is called. If you want to ensure exactly-once insertion, you need to wrap the pair of statements with a synchronized block that synchronizes on the Map m."

So what only helps is a ConcurrentSkipListMap which is 3-5 times slower than a normal ConcurrentHashMap.