45

The JDK ships with CopyOnWrite* implementations for Set and List, but none for Map and I've often lamented this fact. I know there are other collections implementations out there that have them, but it would be nice if one shipped as standard. It seems like an obvious omission and I'm wondering if there was a good reason for it. Anyone any idea why this was left out?

Jens Piegsa
  • 7,399
  • 5
  • 58
  • 106
sgargan
  • 12,208
  • 9
  • 32
  • 38
  • 4
    A lot of people assume the java.util.Map is a Collection, but it isn't. This isn't directly related to your question, but some of the wording made me think that perhaps you had made this assumption, so I thought I'd point this out. – pkaeding Nov 22 '10 at 01:24
  • 1
    Agreed, It might not implement the Collection interface and we could argue the semantics of what a true collection. But the result of such minutia wouldn't make a CopyOnWriteMap less valuable or less missing. – sgargan Nov 22 '10 at 04:07
  • Iteration isn't as common a use-case for maps as it is for other collections. – clstrfsck Nov 28 '10 at 20:21
  • 2
    If you are looking for a high-performance CopyOnWriteMap, we have an impl here: https://labs.atlassian.com/wiki/display/CONCURRENT/CopyOnWriteMap – Jed Wesley-Smith Jan 24 '12 at 01:47
  • @JedWesley-Smith, that link is behind a login. – Erik van Oosten May 22 '13 at 18:24
  • 1
    @ErikvanOosten Thx, the code moved to Bitbucket: https://bitbucket.org/atlassian/atlassian-util-concurrent/wiki/CopyOnWrite%20Maps – Jed Wesley-Smith May 22 '13 at 22:04

2 Answers2

35

I guess this depends on your use case, but why would you need a CopyOnWriteMap when you already have a ConcurrentHashMap?

For a plain lookup table with many readers and only one or few updates it is a good fit.

Compared to a copy on write collection:

Read concurrency:

Equal to a copy on write collection. Several readers can retrieve elements from the map concurrently in a lock-free fashion.

Write concurrency:

Better concurrency than the copy on write collections that basically serialize updates (one update at a time). Using a concurrent hash map you have a good chance of doing several updates concurrently. If your hash keys are evenly distributed.

If you do want to have the effect of a copy on write map, you can always initialize a ConcurrentHashMap with a concurrency level of 1.

Fredrik Bromee
  • 511
  • 4
  • 4
  • The two kinds of collections serve different purposes. A CopyOnWrite collection will be read much more frequently than written and can generally avoid the overhead of locking for reads at the expense of the complete copy on each infrequent write. ConcurrentHashMap will still require a lock regardless of the concurrency value. – sgargan Nov 29 '10 at 06:57
  • Really what I'm looking for is a Map implementation that can be used very efficiently a lookup table. It would be written to very infrequently, (in most case once) and be optimized for reads without locks. – sgargan Nov 29 '10 at 07:02
  • 1
    Please read the javadoc for ConcurrentHashMap again, I think it suits your need. Here are two snippets from it: "A hash table supporting full concurrency of retrieval..." and "...all operations are thread-safe, retrieval operations do not entail locking...". So yes, it is a perfect fit for a concurrent lookup table. – Fredrik Bromee Nov 29 '10 at 10:25
  • You are quite correct, It serves my purpose and answers the question. Thanks kindly. – sgargan Nov 30 '10 at 22:25
  • 1
    This is an old thread, but its worth mentioning: ConcurrentHashMap uses lock striping. This means two threads accessing different parts of your map will not grab the same lock. Lock overhead will only be slow for multiple threads that pile up on a single common stripe. If this happens reduce the load factor (although if it's the same key then not much you can do). – reccles Sep 22 '11 at 15:50
  • 7
    In our testing, our CopyOnWriteMap (with an underlying j.u.HashMap) outperformed ConcurrentHashMap for reads. We use it for read-mostly (eg. config) performance-critical areas. https://labs.atlassian.com/wiki/display/CONCURRENT/CopyOnWriteMap – Jed Wesley-Smith Jan 24 '12 at 01:46
  • @JedWesley-Smith is that posted anywhere that's accessible to people without an Atlassian extranet login? – David Moles Jun 04 '13 at 17:55
  • 3
    yes, for some reason they decided to redirect those to an internal info page and not to the actual destination on bitbucket: https://bitbucket.org/atlassian/atlassian-util-concurrent/wiki/CopyOnWrite%20Maps – Jed Wesley-Smith Jun 04 '13 at 22:04
  • I think it's worth mentionning that you have an excellent non-blocking alternative, namely ConcurrentSkipListMap. Quite convenient in an EJB 3 environment where you have no container-managed singletons and where you are not supposed to manage threads or synchronization. – ymajoros Jan 24 '14 at 17:08
  • 2
    Using copyOnWrite isn't quite the same as ConcurrentHashMap. For example in my case, i want to take a snapshot of the current view of the map and I don't want my reads to be blocked by some 'writings'. I really don't care about any new data, I want a consistent view of the map, when i did my first 'put'. – egelev Jan 14 '15 at 15:16
  • @Jed, could you please share those mentioned tests results or at least magnitude value by which CopyOnWriteMap outperforms ConcurrentHashMap for reads? – Vadzim Jul 30 '15 at 14:08
  • sorry @Vadzim I don't have them at hand, but it was significant. The tests should be pretty easy to reproduce though. – Jed Wesley-Smith Aug 28 '15 at 01:17
  • 3
    if you need to iterate over the whole map in one thread, while a `put` is happening in another thread, it's nice to know that your iteration won't `throw` a `ConcurrentModificationException` in the middle. – Jayen Dec 08 '15 at 07:02
  • Your sarcastic tone suggests there would be no use for a CopyOnWriteMap. If that is the case, how would you suggest implementing a concurrent WeakHashMap? Wrapping in a Collections.synchronizedMap is often far too slow. Hence a CopyOnWriteMap would be the ideal solution. – bremen_matt Oct 05 '17 at 11:50
  • Each `ConcurrentHashMap` can use large amounts of memory, so be careful before creating large numbers of them. https://ria101.wordpress.com/2011/12/12/concurrenthashmap-avoid-a-common-misuse/ – Enwired Oct 09 '17 at 21:14
  • 1
    @JedWesley-Smith I did a quick benchmark, and it doesn't seem like CopyOnWriteMap is any faster than ConcurrentHashMap. Are my benchmarks missing something? https://github.com/tomwhoiscontrary/concurrent-map-bench – Tom Anderson Apr 23 '19 at 09:28
-3

The easiest implementation of a set would usually be to use an underlying map. They even have a Collections.newSetFromMap() method [maybe from 1.6 only].

What they should have done was have a CopyOnWriteMap and the CopyOnWriteSet being equivalent to Collections.newSetFromMap(new CopyOnWriteMap()).

But as you can see the CopyOnWriteArraySet is actually backed by an array not a map. And wouldn't Collections.newSetFromMap(ConcurrentHashMap()) be acceptable for your usecase?

Ustaman Sangat
  • 1,505
  • 1
  • 14
  • 26