Many developers 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 socalled “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^{n}) which is “exponential time”. The following chart summarizes the growth in complexity due to the growth of input (n). In our data structure walkthrough, we sometimes use the symbol h to signify the Hash Table capacity.
Before we start it is helpful to understand the socalled “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^{n}) which is “exponential time”. The following chart summarizes the growth in complexity due to the growth of input (n). In our data structure walkthrough, 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)

Redblack 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)

Redblack tree

ConcurrentHashMap

O(1)

O(1)

O(h / n)

Hash Tables

ConcurrentSkipListMap

O(log n)

O(log n)

O(1)

Skip List

Reference: http://infotechgems.blogspot.com/
No comments:
Post a Comment