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 |