Java Collections – Performance (Time Complexity)
Details of available data structures and their time complexity and performance of the various data structures, in terms of time.
We will discuss about most basic data structures, typically, Array, Map and Linked List.
Before we start you most learn about -
Big O notation - it describes how the time to do a given task grows with the size of the input
O(1) - constant time
O(xn) - 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
|
No comments:
Post a Comment