Java Big-O summary for Java Collections Framework implementations

Big-O summary for Java Collections Framework implementations

List Implementations

                      get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(n)      O(n)
LinkedList            O(n) O(1) O(n)     O(1) O(1)      O(1)
CopyOnWrite-ArrayList O(1) O(n) O(n)     O(1) O(n)      O(n)

Set implementations:

                      add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table capacity
LinkedHashSet         O(1)     O(1)     O(1) 
CopyOnWriteArraySet   O(n)     O(n)     O(1) 
EnumSet               O(1)     O(1)     O(1) 
TreeSet               O(log n) O(log n) O(log n)
ConcurrentSkipListSet O(log n) O(log n) O(1)

Map implementations:

                      get      containsKey next     Notes
HashMap               O(1)     O(1)        O(h/n)   h is the table capacity
LinkedHashMap         O(1)     O(1)        O(1) 
IdentityHashMap       O(1)     O(1)        O(h/n)   h is the table capacity 
EnumMap               O(1)     O(1)        O(1) 
TreeMap               O(log n) O(log n)    O(log n) 
ConcurrentHashMap     O(1)     O(1)        O(h/n)   h is the table capacity 
ConcurrentSkipListMap O(log n) O(log n)    O(1)

Queue implementations:

                      offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
ConcurrentLinkedQueue O(1)     O(1) O(1)     O(n)
ArrayBlockingQueue    O(1)     O(1) O(1)     O(1)
LinkedBlockingQueue   O(1)     O(1) O(1)     O(1)
PriorityBlockingQueue O(log n) O(1) O(log n) O(1)
DelayQueue            O(log n) O(1) O(log n) O(1)
LinkedList            O(1)     O(1) O(1)     O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)
LinkedBlockingDeque   O(1)     O(1) O(1)     O(1)

The performance of collection operations.

In Java, the performance of collection operations varies significantly based on the data structure used. Below, I’ll outline some common Java collections categorized by their typical performance for the contains/get, add, and remove operations. The performance can vary based on many factors, including the initial conditions, the nature of data, and specific use cases, but here's a general ranking from faster to slower:

1. contains / get Operations

• Faster: HashMap, HashSet, ConcurrentHashMap
  • These collections use a hash table structure. Retrieval operations (get, contains) generally have constant time complexity, O(1), assuming a good hash function with low collision.
• Moderate: TreeMap, TreeSet
  • These are based on red-black trees, providing log(n) time complexity for these operations. They are slower than hash table-based collections but offer ordered traversal.
• Slower: ArrayList, LinkedList
  • For ArrayList, get is fast (O(1)), but contains is O(n) because it may need to iterate through all elements. LinkedList requires O(n) time for both get and contains as it needs to traverse the list from the start (or end) to the target index.

2. add Operations

• Faster: ArrayList, HashSet, HashMap
  • ArrayList has a typical amortized constant time complexity for add operations, especially when adding at the end of the list. HashSet and HashMap offer O(1) performance, typically.
• Moderate: LinkedList
  • Adding is generally O(1) at the beginning or end but can be O(n) if inserting at a specific position, as it requires traversal.
• Slower: TreeMap, TreeSet
  • Both have log(n) time complexity for add operations due to the need to maintain a balanced tree.

3. remove Operations

• Faster: HashMap, HashSet
  • Removals are generally O(1) due to direct hash-based indexing.
• Moderate: ArrayList, LinkedList, TreeMap, TreeSet
  • ArrayList removals are O(n) because it may need to shift elements after the removed element.
  • LinkedList offers O(1) removal if you directly have a reference to the node, but finding the node itself is O(n) unless it's specifically at the head or tail.
  • TreeMap and TreeSet provide O(log n) for removal, maintaining tree balance.
• Slower: N/A in this context, as the other collections not listed here do not significantly degrade in performance in ways that merit categorization below the listed options.

These categories give a broad overview and can serve as a general guide when choosing between different collections in Java based on the required operations and their performance implications.

Links: Java Big-O summary for Java Collections Framework implementation. Conclusions from CUP theorem for vectors data sets. What is the CAP Theorem?;