Here are list Java 7 data structures and their thread model and expected performance. (<span style="line-height: 1.714285714; font-size: 1rem;">See </span><a style="line-height: 1.714285714; font-size: 1rem;" href="http://bigocheatsheet.com/">BigO Cheat Sheet</a><span style="line-height: 1.714285714; font-size: 1rem;"> for more algorithm speeds):-</span>
| Name |
Overiew |
Threading Method |
Sorted |
Index |
Search / Contiains or Get |
Insert |
Delete |
Who |
| Maps |
|
|
|
|
|
|
|
|
| HashMap |
Hashtable |
Not thread safe |
No |
n/a |
O(1) |
O(1) |
O(1) |
Java |
| ConcurrentHashMap |
Segmented hashtable |
Non blocking |
No |
n/a |
|
|
|
Java |
| Hashtable |
Old School, don’t use |
Intrinsic blocks |
|
n/a |
O(1) |
O(1) |
O(1) |
Java |
| ConcurrentSkipListMap |
Tree like skipped list |
Lock free CAS |
Yes |
n/a |
O(log(N)) |
O(log(N)) |
O(log(N)) |
Java |
|
|
|
|
|
|
|
|
|
| Lists |
|
|
|
|
|
|
|
|
| ArrayList |
Resizable array |
Not thread safe |
No |
O(1) |
O(N) |
O(N) |
O(N) |
Java |
| LinkedList |
Double linked list |
Not thread safe |
No |
O(N) |
O(N) |
O(1) |
O(1) |
Java |
| Vector |
Old School, don’t use |
Intrinsic blocks |
No |
O(N) |
O(N) |
O(1) |
O(1) |
Java |
|
|
|
|
|
|
|
|
|
| Sets |
|
|
|
|
|
|
|
|
| HashSet |
HashMap backed |
Not thread safe |
No |
n/a |
O(1) |
O(1) |
O(1) |
Java |
| TresSet |
Tree backed |
Not thread safe |
Yes |
n/a |
O(log(N)) |
O(log(N)) |
O(log(N)) |
Java |
| ConcurrentSkipListSet |
As ConcurrentSkipListMap |
As ConcurrentSkipListMap |
yes |
n/a |
O(log(N)) |
O(log(N)) |
O(log(N)) |
Java |
|
|
|
|
|
|
|
|
|
| Queue / FIFO |
|
|
|
|
|
|
|
|
| ConcurrentLinkedQueue |
|
Non blocking |
No |
|
|
|
|
Java |
| PriorityQueue |
Balanced binary heap |
Not thread safe |
Yes |
n/a |
O(N) |
O(log(N)) |
O(log(N)) |
Java |
| ArrayBlockingQueue |
Bounded array |
Reentrant lock |
No |
O(1) |
O(N) |
O(1) |
O(N) |
Java |
| PriorityBlockingQueue |
Array based binary heap |
Reentrant lock |
Yes |
n/a |
O(N) |
O(log(N)) ? |
O(log(N)) ? |
Java |
| LinkedBlockingQueue |
Typically greater throughput than array backed |
Reentrant lock |
No |
|
|
|
|
Java |
| LinkedTransferQueue |
Producer waits for consumer |
Short spin then park/unpark |
No |
|
|
|
|
Java |
| SynchronousQueue |
Insert waits for remove |
Short spin then park/unpark |
No |
|
|
|
|
Java |
| DelayQueue |
Backed by PriorityQueue |
Reentrant lock |
Yes |
|
|
|
|
Java |
| ForwardingBlockingQueue |
Blocking queue to another Blocking queue |
Not thread safe |
No |
|
|
|
|
Google |
| EvictingQueue |
Evicts from head |
Not thread safe |
No |
|
|
|
|
Google |
|
|
|
|
|
|
|
|
|
| Dequeue / FIFO or LIFO |
|
|
|
|
|
|
|
|
| LinkedList |
List, double linked list |
Not thread safe |
No |
O(N) |
O(N) |
O(1) |
O(1) |
Java |
| LinkedBlockingDeque |
Linked list |
Reentrant lock |
No |
|
|
|
|
Java |
| ArrayDeque |
Array backed |
Not thread safe |
No |
|
|
|
|
Java |
| ConcurrentLinkedDeque |
|
Non blocking |
No |
|
|
|
|
Java |
| ForwardingDeque |
Abstract |
Not thread safe |
No |
|
|
|
|
Google |
| ForwardingBlockingDeque |
Abstract |
Not thread safe |
No |
|
|
|
|
Google |
