CODEWITHSUNDEEP
javamultithreadingperformancecollections
Yazan Jaber
Yazan Jaber

Reputation: 2068

What is the right Java collection to use in this case?

I need to hold a large number of elements (500k or so) in a list or a set I need to do high performance traversal, addition and removal. This will be done in a multithreaded environment and I don't care if I gets to see the updates done after traversal began (weakly consistent), what Java collection is right for this scenario?

Upvotes: 7

Views: 4720

Answers (8)

卢声远 Shengyuan Lu
卢声远 Shengyuan Lu

Reputation: 32004

On other hand, due to large size of data, is it possible to store the data in database? And use memory collection as cache.

Upvotes: 0

bestsss
bestsss

Reputation: 12056

I need to hold a large number of elements (500k or so) in a list or a set I need to do high performance traversal, addition and removal. ... This will be done in a multithreaded environment

ConcrrentSkipListMap - it's not a List but List semantics are practically useless in concurrent environment. It will have the elements sorted in a tree alike structure and not accessible via hashing, so you need some natural ordering (or external via comparator)

If you need only add/remove at the ends of a Queue - ConcurrentLinkedQueue.

Synchronized collections are not suited for multi-threaded environment if you expect even moderate contention. They require full lock holding during the entire traverse operation as well. I'd advise against ConcurrentHashMap, either.

In the end: if you are going for real multi-CPU like 64+ and expect high contention and don't want natural ordering follow the link: http://sourceforge.net/projects/high-scale-lib

Upvotes: 3

Rogach
Rogach

Reputation: 27200

If you need to add or remove items in the middle of a list quickly, LinkedList is a good choice. To use it in multithreaded enviroment, you need to synchronise it like this:

List l = Collections.synchronisedList(new LinkedList());

Upvotes: 0

BernardMarx
BernardMarx

Reputation: 916

If you do addition and removal often, then something "linked" is probably the best choice. That way everytime you add/remove only an index has to be updated, in contrast to an ArrayList for example where the whole Array has to be "moved". The problem is that you are asking for the holy grail of Collections.

Taking a look at the Concurrent Collections might help.

But what do you mean by "traversal"?

Upvotes: 1

maaartinus
maaartinus

Reputation: 46422

Multithreaded - so look at j.u.concurrent. Maybe ConcurrentHashMap used as a Set - e.g. use put(x, x) instead of add(x).

Upvotes: 1

GuruKulki
GuruKulki

Reputation: 26418

Here is a very good article on selecting a collection depending on your application

http://www.developer.com/java/article.php/3829891/Selecting-the-Best-Java-Collection-Class-for-Your-Application.htm

you can try this as well

http://www.javamex.com/tutorials/collections/how_to_choose.shtml

Upvotes: 2

duffymo
duffymo

Reputation: 308763

If traversal == read, and add/remove == update, I'd say that it's not often that a single collection is optimized for both operations.

But your best bet is likely to be a HashMap.

Upvotes: 1

Azodious
Azodious

Reputation: 13872

are duplicate items allowed?

is yes, Set can't be used. you can use SortedSet otherwise.

Upvotes: -1

Related Questions