Java Collections – Performance (Time Complexity)

Many developers I came across in my career as a software developer are only familiar with the most basic data structures, typically, Array, Map and Linked List. These are fundamental data structures and one could argue that they are generic enough to fit most of the commercial software requirements. But what worries me most is that even seasoned developers are not familiar with the vast repertoire of available data structures and their time complexity. In this post the ADTs (Abstract Data Types) present in the Java Collections (JDK 1.6) are enlisted and the performance of the various data structures, in terms of time, is assessed.

Before we start it is helpful to understand the so-called “Big O” notation. This notation approximately describes how the time to do a given task grows with the size of the input. Roughly speaking, on one end we have O(1) which is “constant time” and on the opposite end we have O(xⁿ) which is “exponential time”. The following chart summarizes the growth in complexity due to growth of input (n). In our data structure walk-through we sometimes use the symbol h to signify the Hash Table capacity.

List

A list is an ordered collection of elements.

	Add	Remove	Get	Contains	Data  Structure
ArrayList	O(1)	O(n)	O(1)	O(n)	Array
LinkedList	O(1)	O(1)	O(n)	O(n)	Linked List
CopyonWriteArrayList	O(n)	O(n)	O(1)	O(n)	Array

Set

A collection that contains no duplicate elements.

	Add	Contains	Next	Data Structure
HashSet	O(1)	O(1)	O(h/n)	Hash Table
LinkedHashSet	O(1)	O(1)	O(1)	Hash Table + Linked List
EnumSet	O(1)	O(1)	O(1)	Bit Vector
TreeSet	O(log n)	O(log n)	O(log n)	Red-black tree
CopyonWriteArraySet	O(n)	O(n)	O(1)	Array
ConcurrentSkipList	O(log n)	O(log n)	O(1)	Skip List

Queue

A collection designed for holding elements prior to processing.

	Offer	Peak	Poll	Size	Data Structure
PriorityQueue	O(log n )	O(1)	O(log n)	O(1)	Priority Heap
LinkedList	O(1)	O(1)	O(1)	O(1)	Array
ArrayDequeue	O(1)	O(1)	O(1)	O(1)	Linked List
ConcurrentLinkedQueue	O(1)	O(1)	O(1)	O(n)	Linked List
ArrayBlockingQueue	O(1)	O(1)	O(1)	O(1)	Array
PriorirityBlockingQueue	O(log n)	O(1)	O(log n)	O(1)	Priority Heap
SynchronousQueue	O(1)	O(1)	O(1)	O(1)	None!
DelayQueue	O(log n)	O(1)	O(log n)	O(1)	Priority Heap
LinkedBlockingQueue	O(1)	O(1)	O(1)	O(1)	Linked List

Map

An object that maps keys to values. A map cannot duplicate keys; each key can map to at most one value.

	Get	ContainsKey	Next	Data Structure
HashMap	O(1)	O(1)	O(h / n)	Hash Table
LinkedHashMap	O(1)	O(1)	O(1)	Hash Table + Linked List
IdentityHashMap	O(1)	O(1)	O(h / n)	Array
WeakHashMap	O(1)	O(1)	O(h / n)	Hash Table
EnumMap	O(1)	O(1)	O(1)	Array
TreeMap	O(log n)	O(log n)	O(log n)	Red-black tree
ConcurrentHashMap	O(1)	O(1)	O(h / n)	Hash Tables
ConcurrentSkipListMap	O(log n)	O(log n)	O(1)	Skip List