Collection Framework

Data Structure is a way to store and organize data so that it can be used efficiently.  For example, we can store a list of items having the same data-type using the array data structure.

A Collection is a group of individual objects represented as a single unit.

Java provides Collection Framework which defines several classes and interfaces to represent a group of objects as a single unit.

Two main “root” interfaces of Java collection classes:-

Collection interface (java.util.Collection)
Map interface (java.util.Map)

Need for Collection Framework :
Before Collection Framework (or before JDK 1.2) was introduced, the standard methods for grouping Java objects (or collections) were Arrays or Vectors or Hashtables. All of these collections had no common interface.




Array vs ArrayList

Array -

• fixed size data structure.
• can contain both primitive data types as well as objects of class.
• mandatory to provide size of Array, once Array is created we can’t change length of it.

ArrayList -

• dynamic size data structure.
• supports object entries not primitive data types.
• java will create Arraylist with default size, resize itself when gets full depending upon capacity and load factor.  mechanism will be creating new Array and copying content from old array to new array.

int newCapacity = (oldCapacity * 3)/2 + 1;

=10*3/2 + 1
=30/2+1
=15+1=16

Default initial capacity - 10
Load factor - 1 ( when the list is full)

Growth rate - current size + current size /2
____________________________________________________________________________

ArrayList vs LinkedList

Similarities:-

• both maintain the elements insertion order
• non synchronised 
• fail-fast iterator(if 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)

Differences:-

• Search
• ArrayList - O(1)
• LinkedList - O(n)

• Deletion
• ArrayList - O(n), O(1)
• LinkedList - O(1)

• Insert
• ArrayList - O(n), O(1)
• LinkedList - O(1)

• Memory Overhead
• ArrayList - less
• LinkedList- high

____________________________________________________________________________

HashSet | LinkedHashSet | TreeSet

HashSet

• doesn’t maintain any order, the elements would be returned in any random order.
• doesn’t allow duplicates.
• allows null values.
• non synchronised.
• Fail Fast iterator

LinkedHashSet

• maintains the insertion order.
• allows null values.

TreeSet

• sorts the elements in ascending order.
• doesn’t allow null values.

____________________________________________________________________________

HashMap | LinkedHashMap | TreeMap

HashMap - 

unordered data structure

non synchronised

allows null values

LinkedHashMap - 

ordered data structure

allows null values

TreeMap - 

sorts the elements in ascending order of keys.

____________________________________________________________________________

Load factor

Load factor represents at what level data structure capacity should be doubled/increased.

HashMap

Default initial capacity - 16

Default load factor- 0.75

capacity * load factor 

16 * 0.75 = 12

This represents that after storing 12th  key-value pair into the HashMap, its capacity becomes 32.