A concurrent collection that maintains insertion order

Question

I'm looking for a concurrent list that can maintain the insertion order. Does anyone have some good recommendation ?

I look at some from guava e.g. SetFromMap, but they are deprecated in the new version.

Thank you.

Are you looking for a list or a set? Because lists maintain insertion order by definition. — Mena, Apr 19 '16 at 16:48
https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html — ΦXocę 웃 Пepeúpa ツ, Apr 19 '16 at 16:49
Possible duplicate of [Is there a concurrent List in Java's JDK?](http://stackoverflow.com/questions/6916385/is-there-a-concurrent-list-in-javas-jdk) — Stefan Dollase, Apr 19 '16 at 16:49
I depends on your use case: Do you have a lot of write operations? Do you have mostly read op and few wrtie op? Do you have a lot of elements to store into your collection? — Nicolas Filotto, Apr 19 '16 at 17:19
@Nicolas I expect to have more write operations and read operations — Xitrum, Apr 19 '16 at 17:21
What about the total amount of elements in your collection? About 10/100/1 000/10 000... elements? — Nicolas Filotto, Apr 19 '16 at 17:24
If so the CopyOnWriteArrayList is clearly not the right candidate, have a look to this question http://stackoverflow.com/questions/6074111/alternative-to-copyonwritearraylist-for-frequent-writes-occasional-iterating — Nicolas Filotto, Apr 19 '16 at 17:39
@Nicolas can you make the comment as answer? Since it is what im looking for. — Xitrum, Apr 19 '16 at 17:50
@ΦXoce웃Пepeúpa well, thank you for proposing but I don't want to benefit from other responses but I proposed my own response to your question — Nicolas Filotto, Apr 19 '16 at 21:08

score 4 · Answer 1 · answered Apr 19 '16 at 16:48

4

A CopyOnWriteArrayList is a List that both maintains insertion order (as expected from a List) and allows concurrent access.

Docs here.

answered Apr 19 '16 at 16:48

Mena

47,782
11
87
106

This assumes a very low write rate, but it's the closest match. – Peter Lawrey Apr 19 '16 at 17:54

Nicolas Filotto · Accepted Answer · 2016-04-20T06:28:37.570

If you have mostly read operations, very few write operations and you don't have too much elements then you can use CopyOnWriteArrayList as it is a lock free implementation of a List for read operations such that it can hardly be faster but it is very costly for the write operations as for every single write, it re-builds the entire List to be able to provide a new read-only copy for the next read operations.

As in your case, you have many write operations and a lot of elements to put in your collection, CopyOnWriteArrayList is clearly not an option for you.

What I suggest in your case, is to use one thread-safe Queue that you can find into the java.util.concurrent package. According to your context and your JDK version the best choice may change, but if you don't specifically need a blocking queue or a deque but only a pure collection, the best choices are probably ArrayBlockingQueue, ConcurrentLinkedQueue or LinkedBlockingQueue but according to this benchmark result (a little bit old), the LinkedBlockingQueue provides the best overall performances.

But when we talk about performances, the first and most important advice is: always test on your target environment, it is the only valid way to know what is the best choice for you.

score 0 · Answer 3 · answered Apr 19 '16 at 17:58

Maximum will be 10k elements

If you have an extremely low update rate, CopyOnWriteArrayList is a possible solution. This will allow concurrent reads efficiently.

The problem you have is that concurrent and ordered are opposite concerns. To have ordering, you need to serialize updates to determine the order. To have concurrency you need to discard ordering.

There is a ConcurrentLinkedQueue, however this only allows concurrent read (1) and write (1)

A concurrent collection that maintains insertion order

3 Answers3

Linked