3

I have a scenario where an unknown amount of threads add elements to a collection on a server. The data in this collection doesn't have to be sorted and it also won't be iterated. Only two simple operations shall work on this collection:

  1. Adding an element (and removing old element in some cases)
  2. Reading all elements from the collection (not one by one, but the whole collection in order to serialize it and send it to a client. Of course the elements could also be moved to another collection which is then serialized afterwards.)

Which collection would be ideal for this use case? I would choose ConcurrentHashMap, bu I don't know if this choice is good.

Edit: I've forgotten one important requirement: If an element of a certain kind is already in this collection and another one of the same kind is added, then the old one shall be removed before the new one is added. For this requirement I wanted to use hash values to avoid searching. The objects that are stored are simple: They contain a unique user name and some strings and ints. The object's user name should be used as key.

user1812379
  • 827
  • 3
  • 11
  • 22
  • 1
    Why ConcurrentHashMap? Are you looking up key-value pairs? – John Ericksen Jun 08 '13 at 15:52
  • 1
    If this is all you really need to do then a `CopyOnWriteArrayList` will do the job; however, beware that one iteration creates a _new copy_ each time. As such, if you expect a lot of readers, this may not be the ideal choice... – fge Jun 08 '13 at 15:58
  • 1
    According to the doc it's very expensive to add and remove elements from CopyOnWriteArrayList. – user1812379 Jun 08 '13 at 16:21
  • If you use the username as a key and the object as a value, a ConcurrentHashMap seems indicated. – assylias Jun 08 '13 at 18:49

4 Answers4

3

Yes, ConcurrentHashMap is appropriate for this. Use the user name as key type (K) and the associated user information ("some strings and ints") as value type (V) in the map. Use put to add new key-value pairs, remove to remove key-value pairs, and entrySet to get all key-value pairs in the container (if that is what you meant by "reading all elements from the collection").

cic
  • 7,310
  • 3
  • 23
  • 35
  • Yes, I have done that: The value is the object itself and the key an object property. I have surrounded method calls like `put()` and `remove(`) with `synchronized(map) {.....}`. Are there any rules how a `ConcurrentHashMap` should be properly configured? A default concurrencyLevel of 16 might often be overkill. – user1812379 Jun 08 '13 at 23:15
  • 2
    @user1812379: You do not need to use `synchronized(map) { ... }` to use `put`, `remove` or any other operation on CHM instances -- that would defeat the purpose of using the CHM class. The operations on CHMs are already atomic, see the documentation for further details. As for the most appropriate value for `concurrencyLevel`, the Javadoc has some notes, but if it's really important you should measure (under realistic workloads) yourself as the "best" value differs between situations (that is why you are allowed to configure it). – cic Jun 09 '13 at 07:32
  • See also http://stackoverflow.com/questions/510632/whats-the-difference-between-concurrenthashmap-and-collections-synchronizedmap. – cic Jun 09 '13 at 07:38
2

i think the best thing to use is actually ConcurrentSkipListSet . the reason:

Iterators are weakly consistent, returning elements reflecting the state of the set at some point at or since the creation of the iterator. They do not throw ConcurrentModificationException, and may proceed concurrently with other operations. Ascending ordered views and their iterators are faster than descending ones.

this means you can go over the entire list and read all of the items, while adding other items. it's completely concurrent !

do note that adding items take O(logN) time.

android developer
  • 114,585
  • 152
  • 739
  • 1,270
  • Thanks. Yes, when the data in the ConcurrentHashMap is read it can already be outdated, but reading hash values is faster than tree traversal. – user1812379 Jun 08 '13 at 23:05
  • 1
    but one of the requirements is that you could read all of the items, concurrently. the iterator of the ConcurrentHashMap isn't designed to work with multiple threads : "iterators are designed to be used by only one thread at a time." http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentHashMap.html – android developer Jun 08 '13 at 23:09
  • Sorry, because in this regard I have been imprecise: I don't want to read every single element, but read the whole data at once and then send it to a remote host. The client then reads the object from the stream and stores the data in a TreeSet to display it in a certain order. – user1812379 Jun 08 '13 at 23:31
  • 1
    if you go over each of the items, and put them into a new collection, it's the same. if you use the ConcurrentHashMap you can't use multiple threads so you lose the concurrency for this action. there is also another concurrent collection which collects all of the items atomically , but then the writing to the collection is much slower so i didn't recommend about it. – android developer Jun 09 '13 at 06:43
  • @androiddeveloper: The Javadoc talks about that CHM iterator *instances* are not meant to be used from multiple threads, you can still modify a CHM instance from some thread when some other thread is iterating over the CHM's values (with the same weakly consistent semantics as CSLS iterators afaik). – cic Jun 09 '13 at 07:50
  • @cic you missed the point: you can't have multiple threads that will iterate through the collection. only a single thread is allowed. the requirement is to have concurrency so by default, each operation should be concurrent unless specified otherwise. if you block other threads from using a function, it's not concurrent. – android developer Jun 09 '13 at 08:48
  • But wouldn't it work if multiple threads iterate over the ConcurrentHashMap and each thread owns his own Iterator instance? – user1812379 Jun 09 '13 at 11:19
  • @androiddeveloper: That is simply wrong. See user1812379's suggestion below your comment. – cic Jun 09 '13 at 12:38
  • @cic i don't understand . what's wrong? if the requirement doesn't include concurrency for the iterator, it should've be written. i don't know how the class is implemented. i only wrote what the javadocs say , and what i understand is that it was meant to be used by a single thread. which part of it is "simply wrong" ? also, note that log(n) is very good considering that most cases the number of items isn't that huge to make the log(n) to become huge. for the real world, it's like O(32)=O(1) . – android developer Jun 09 '13 at 13:26
  • @androiddeveloper: If you want multiple threads to iterate the same CHM instance, just let each thread request its own iterator instance (as user1812379 said). Therefore, multiple threads can iterate the same CHM instance without any problems. Therefore, what you said is "simply wrong". But if you want to "split" the CHM instance into multiple part in such a way that each element from the container is given to one and only one thread get you have to use additional synchronization afaics. As I understood it, however, this is not what user1812379 wants. – cic Jun 09 '13 at 13:57
  • @cic that's not how i understand what the javadocs says. if each thread is using a different iterator , it is against what is written: "iterators are designed to be used by only one thread at a time." . you mean that you see it as : each iterator should be used by a different thread? maybe i'm wrong. it's not that clear. – android developer Jun 09 '13 at 14:24
  • @androiddeveloper: See http://stackoverflow.com/questions/3768554/is-iterating-concurrenthashmap-values-thread-safe – cic Jun 09 '13 at 14:45
1

I believe there is a concurrent list implementation in java.util.concurrent. CopyOnWriteArrayList which can be useful for your requirement.

or you can use :

 List<Object> objList = Collections.synchronizedList(new ArrayList<Object>());
Juned Ahsan
  • 67,789
  • 12
  • 98
  • 136
1

It's not part of the standard library, but you can use this concurrent doubly linked list. Its iterator is weakly consistent and won't throw a ConcurrentModificationException, or you can use toArray and loop through the returned array.

Zim-Zam O'Pootertoot
  • 17,888
  • 4
  • 41
  • 69