Take the 2-minute tour ×

Please help me use/create Concurrent LinkedHashMap in multithreaded architecture.

As per my belief, if I use Collections.synchronizedMap(), I would have to use synchronized blocks for iterator. Would this implementation lead to sequential addition of elements

If I use ConcurrentSkipListMap<String,String> is there any way to implement a Comparator to store sequentially, as stored in Linked List or queue.

I would like to use java's built in instead of third party packages.



In Concurrent LinkedHashMap, the keys are the name, I wish to put the keys in sequence of their arrival. i.e. new value would be appened to either at start or end, but sequentially.

while iterating, the LinkedHashMap could be added with new entries, or removed. but the iteration should be follow the seqence in which the entries were added.

I understand that by using Collections.synchronizedMap(), an synchronized block for iteration would have to be implemented, but would the map be modifiable (entries could be added/removed) while it is being iterated.

share|improve this question
What getter/setter are you talking about? What are you trying to "store sequentially"? Please give more details - it's hard to understand what you're really trying to do at the moment. –  Jon Skeet Apr 23 '10 at 11:56
What are you trying to store sequentially? If your keys have a definable order then you should be able to write a Comparator. Perhaps you should provide more information about the keys in your map and how you would like them ordered. –  M. Jessup Apr 23 '10 at 11:58
add comment

4 Answers

A LinkedHashMap has a doubly linked list running through a hashtable. A FIFO only mutates the links on on a write (insertion or removal). This makes implementing a version fairly straightforward.

1) Write a LHM with only insertion order allowed. 2) Switch to a ConcurrentHashMap as the hashtable. 3) Protect #put() / #putIfAbsent() / #remove() with a lock. 4) Make the "next" field volatile.

On iteration, no lock is needed as you can safely follow the "next" field. Reads can be lock-free by just delegating to the CHM on a #get().

share|improve this answer
No offense, but I hate it when people talk like this. I know what's a doubly linked list. I know what's a hashtable. But what does a double linked list running through a hashtable supposed to mean? –  Pacerier Nov 5 '11 at 23:50
Yes, its hard to explain and visualize. See this presentation where I gave it a try. The idea is that a linked list maintains ordering and requires an O(n) seek. A hashtable is unordered and finds an entry in O(1) time. The combination is that the hash-table entry contains the list pointers so an entry is ordered on the list. Entries in the list can be appended to (FIFO order), moved to the head/tail (LRU order), and removed in O(1) time (eviction). This provides a insertion or access ordered map cheaply. –  Ben Manes Nov 6 '11 at 3:02
isn't it true that if I sort my HashMap, it would effectively become an "ordered" hashmap, which basically defeats the purpose of a LinkedHashMap ? –  Pacerier Nov 6 '11 at 5:57
Any comparison based sort is O(lg n) and requires something to compare with (e.g. timestamp). This is not comparison based and is faster for maintaining insertion or access order. –  Ben Manes Nov 6 '11 at 6:39
add comment

Use Collections#synchronizedMap().

As per my belief, if I use Collections.synchronizedMap(), I would have to use synchronized blocks for getter/setter.

This is not true. You only need to synchronize the iteration on any of the views (keyset, values, entryset). Also see the abovelinked API documentation.

share|improve this answer
if map is being iterated, then would it be possible for other thread to add or remove elements from the map? –  Nilesh Apr 23 '10 at 12:15
Would this implementation lead to sequential addition of elements –  Nilesh Apr 23 '10 at 12:21
1) Not if you synchronize the iteration as per the documentation (have you clicked the link anyway?). That's the whole point of synchronization. 2) Yes, the addition is already internally synchronized, that's also your whole intent, is it? –  BalusC Apr 23 '10 at 12:29
1) No - read the javadoc. 2) Yes - this implied by the javadoc, and guaranteed by the current implementation. –  Stephen C Apr 23 '10 at 12:31
it is possible to synchronize without serializing all get and put operations. For example, ConcurrentHashMap works that way. However, the javadoc implies that operations on a Map returned by this method will be serialized. –  Stephen C Apr 23 '10 at 12:34
add comment

If you use synchronizedMap, you don't have to synchronize externally, except for iteration. If you need to preserve the ordering of the map, you should use a SortedMap. You could use ConcurrentSkipListMap, which is thread-safe, or another SortedMap in combination with synchronizedSortedMap.

share|improve this answer
add comment

Until now, my project used LRUMap from Apache Collections but it is based on SequencedHashMap. Collections proposes ListOrderedMap but none are thread-safe.

I have switched to MapMaker from Google Guava. You can look at CacheBuilder too.

share|improve this answer
add comment

Your Answer


