Here are list Java 7 data structures and their thread model and expected performance. (See BigO Cheat Sheet for more algorithm speeds):-
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 | |||||
EvictingQueue | Evicts from head | Not thread safe | No | |||||
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 | |||||
ForwardingBlockingDeque | Abstract | Not thread safe | No |