I assume readers have basic knowledge about data general purpose data structures and Java Collections framework to under stand this article.
Java Collections framework was designed and implemented using general purpose data structures to cater to different kinds of users. We do not need to write our own hash table or linked list to handle huge data items.
Basically, Java collections classes (Set/Map) falls into three core data structures such as Hash Table, Red black Tree and Linked List.
Why Hash Table ?.
 It is based on arrays
 Uses hashing technique which offers very fast insertion and searching.
 If we don’t need to visit items in order, and we can predict in advance the size of our data, hash tables are unparalleled in speed and convenience.
 It is based on arrays
 Uses hashing technique which offers very fast insertion and searching.
 If we don’t need to visit items in order, and we can predict in advance the size of our data, hash tables are unparalleled in speed and convenience.
Why Red Black Tree ?
 It is a balanced tree, guarantees O(logN) performance whether the input data is ordered or not.
 Advantage in a redblack tree is that sorted data doesn’t lead to slow O(N) performance.
Why LinkedList ?
 Used whenever the amount of data to be stored cannot be predicted in advance or when data will frequently be inserted and deleted.
1) Comparison of HashMap / HashSet / TreeSet / LinkedHashMap:
HashMap/HashSet : Underlying data structure is HashTable. As the you see, name Hash*  indicates Hash Table data structure.
TreeMap/TreeSet : Underlying data structure is Red black Tree.
LinkedHashMap/LinkedHashSet : Underlying data structure is doubly Linked List and Hash Table.
HashMap/HashSet/LinkedHashMap/LinkedHashSet  all of them have constant time performance for retrieval,insertion and deletion operations. But LinkedHashMap/LinkedHashSet performance is bit lesser than HashTable since it needs to maintain additional linked list.
Except redblack tree (which is nonlinear), all the data structures used here are linear type.
Operations

HashTable

Red black Tree

Linked List + HashTable

Retrieval (get)
 O(1)  HashMap/HashSet  O(log N) TreeMap/TreeSet  O(1)  LinkedHashMap. 
Insertion (put)
 O(1)  HashMap/HashSet  O(log N)  TreeMap/TreeSet  O(1)  LinkedHashMap 
Deletion
 O(1)  HashMap/HashSet  O(log N)  TreeMap/TreeSet  O(1)  LinkedHashMap 
Parameters affecting performance

Initial Capacity and Load Factor
 
Initial Capacity and Load Factor

Iteration Order  Does not guarantee the iteration order  Sorted according to the natural order  This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertionorder). Insertion order is not affected if a key is reinserted into the map. 
O(1)  constant time : Better performance.
O(n)  linear time : Worst performance for the large data.
O(log N)  logarithmic time : Average Performance.
2) Comparison ArrayList and LinkedList
Array list allows random access , so we can grab any element in constant time whereas linked list allows sequential access of elements. You can walk front/back but grabbing element in the middle is proportional to the size of the list.
ArrayList is useful when
 we need random access of elements.
 we don’t need to remove elements inbetween.
 adding elements at amortized time
LinkedList is useful when
 we prefer iteration over the the random access
 we need efficient removal in between the elements or at start.
Operations

ArrayList

LinkedList

Base Data Structure

Dynamically resizing array

Doubly linked list

Retrieval (get)

O(1)

O(n)

Insertion (add)

O(1)  on average
O(n)  on worst case

O(1)

Deletion

O(n)

O(1)  Iterator.remove

Mostly useful for

Efficient Retrieval  (by random access)

Efficient Removal

Is NULL permitted

Yes

Yes

Iterators

Iterator and ListIterator which are failfast*

Iterator and ListIterator which are fail fast*

* Failfast : If the list is structurally modified at any time after the iterator is created, in any way except through the Iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException.
No comments:
Post a Comment