Categories
Java Technology

Java Data Structures

            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