Java 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.

HashSet | LinkedHashSet | TreeSet

HashSet is Implemented using a hash table. Elements are not ordered. The add, remove, and contains methods have constant time complexity O(1).

TreeSet is implemented using a tree structure(red-black tree in algorithm book). The elements in a set are sorted, but the add, remove, and contains methods has time complexity O(log (n)). It offers several methods to deal with the ordered set like first(), last(), headSet(), tailSet(), etc.

1) First major difference between HashSet and TreeSet is performance. HashSet is faster than TreeSet and should be preferred choice if sorting of element is not required.

2) Second difference between HashSet and TreeSet is that HashSet allows null object but TreeSet doesn't allow null Object and throw NullPointerException, Why, because TreeSet uses compareTo() method to compare keys and compareTo() will throw java.lang.NullPointerException.

3) Another significant difference between HashSet and TreeSet is that , HashSet is backed by HashMap while TreeSet is backed by NavigableMap in Java.

4) One more difference between HashSet and TreeSet which is worth remembering is that HashSet uses equals() method to compare two object in Set and for detecting duplicates while TreeSet uses compareTo() method for same purpose. if equals() and compareTo() are not consistent, i.e. for two equal object equals should return true while compareTo() should return zero, than it will break contract of Set interface and will allow duplicates in Set implementations like TreeSet.

5) Now most important difference between HashSet and TreeSet is ordering. HashSet doesn't guaranteed any order while TreeSet maintains objects in Sorted order defined by either Comparable or Comparator method in Java.

6) TreeSet does not allow to insert Heterogeneous objects. It will throw classCastException at Runtime if trying to add hetrogeneous objects, whereas HashSet allows hetrogeneous objects.

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.

Array | 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 | 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

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.