Collection FrameWork

COLLECTION FRAMEWORK

Abstract:

The Collection Framework provides a well-designed set of interface and classes for sorting and manipulating groups of data as a single unit.
The Collection Framework provides a standard programming interface to many of the most common abstractions, without burdening the programmer with too many procedures and interfaces.
It defines several classes & interfaces, which can be used a group of object as single entity

They are 9 Key interfaces of collection framework

1. Collection

2. List

3. Set

4. SortedSet

5. NavigableSet

6. Queue

7. Map

8. SortedMap

9. NavigableMap

1. Collection(Interface):

àGroup of individual objects as a single entity, then we should go for Collection.

àThere is no concrete class which implements collection (Interface).

2. List (Interface):

àChild Interface of collection.

àGroup of individual objects as a single entity where insertion order is preserved and duplicate objects are allowed. Then we should go for List.

àWe can differentiate duplicate objects and make an insertion order by using index. Hence index place is very important role in list.

àIn 1.2 version, Vector and stack classes are reengineer.

ArrayList(Class) àà List (Interface):

The underlying Data structure is Resizable Array or Growable Array.

Insertion order is preserved.

Duplicate objects are allowed.

Heterogeneous objects are allowed.

Null Insertion is possible.

LinkedList(Class) àà List (Interface):

The underlying Data structure is double Linked List.

Insertion order is preserved.

Duplicate objects are allowed.

Heterogeneous objects are allowed.

Null Insertion is possible.

Implements serializable & clonable interfaces but not Random Access.

LinkedList is best choose if our frequent operation is Insertion/Deletion in the middle.

LinkedList is worst choose if our frequent operation is retrieval operation.
Example:
http://www.sanfoundry.com/java-program-implement-singly-linked-list/

Vector(Class) àà List (Interface):

The underlying Data structure is Resizable Array or Growable Array.

Insertion order is preserved.

Duplicate objects are allowed.

Null Insertion is possible.

Implements seriablizable, Clonable & RandomAccessInterface.

Every method present in vector is synchronized &  Hence vector object is thread safe.

Best ssuitable, if our frequent ooperation is retrival.

Worst choose, if our frequent operation is intertion / deletion in the middle.

Stack(Class):

It is child class of vector.

If we want to represent objects according to LastInFirstOut, then we should go for stack.

LastInFirstOut order is applicable only for removal .

3. Set (Interface):

àChild Interface of collection.

àIf we want to represent a group of individual objects where duplicates are not allowed and insertion order not preserved.

HashSet(Class) àà Set (Interface):

àThe underlying datastructure is Hashtable.
àInsertion order not preserved and it is based on HashCode of the objects.
àDuplicate objects are not allowed
àIf we are trying to insert duplicate objects, we won’t ger any compile time / run time Exception. Simply add() retuns false.
àHetrogenous objects are allowed.
ànull insertion is possible.
àIf our frequent operations is search operation, then HashSet is the best choose.
àCreates an empty HashSet object with default initial capacity 16 & default fillRatio (LoadFactor) is 0.75

LinkedHashSet(Class) àà Set (Interface):

It is the child class of HashSet.
It is exactly same as HashSet(Including constructor methods) except the following difference.

HashSet	LinkedHashSet
1.It is underlying data structure is Hashtable	1.Underlying data structure is Hashtable+LinkedList.
2.Insertion order is not preserved	2.Insertion order is preserved.
3.Introducted in 1.2 version.	3.Introduced in 1.4 version.

TreeSet(Class) àà Set (Interface):

àUnderlying Data Structure is balanced tree.
àDuplicate objects are not allowed.
àInsertion order is not preserved & it is based on sorting order.
ànull insertion is possible(only once).
àHeterogeneous objects are not allowed, by mistake if we are trying to insert Heterogeneous objects we will get RunTimeException saying ClassCastException.
àFor Non-Empty TreeSet, if we are trying to insert null, we will get NullPointerException.
àFor the Empty TreeSet, as the first elementà null insertion is possible. But after inserting null, if we are trying to insert anyother element we will get NullPointerException.

4.  SortedSet(Interface) àà Set (Interface):

àIt is the child Interface of Set.
àRepresent a group of individual objects according to some sorting order without duplicates.
àGroup of objects according to same sorting order without duplicates.

5. NavigableSet:

àChild Interface of Set(Interface).

àIt define several methods which can be used for navigable purpose.

6. Queue:

àChild Interface of Collection.

àGroup of individual objects prior to processing.

All the above Interfaces (ie., Collection, List, Set, SortedSet, NavigableSet, Queue) is  mend for representing individual objects.

If we want to represent a group of Objects as a key-value pair then we should go for Map(Interface).

7. Map:

àIt is not child Interface of Collection Interface.

àIf we want to represent a group of objects as key-value pair then we should go for Map.

àDuplicate keys are not allowed where as duplicate values are allowed.

HashMap(Class) àà Map (Interface):

àUnderlying Data Structure is Hashtable.
àInsertion order is not preserved and it is based on Hash code of the key.
àDuplicate keys are not allowed but values can be duplicated.
àHeterogeneous objects are allowed for both keys and values.
ànull keys allowed for key(only once) & values(any nubmers of times)

LinkedHashMap(Class) àà Map (Interface):

It is exactly same as HashMap except the following difference.

HashMap	LinkedHashMap
Underlying Data Structure is Hashtable	Underlying DataStructure is combination of Hashtable + LinkedList
Insertion order is not preserved	Insertion order is preserved
Introduced in 1.2 version	Introduced in 1.4 version

TreeMap(Class) àà Map (Interface):

àUnderlying data structure is RED-BLACK Tree.
àDuplicate keys are not allowed but values to be duplicated
àInsertion order is not preserved and all entries will be inserted according to some sorting order of keys.
àIf we are depending on default natural sorting order, compulsory keys should be homogenous & comparable otherwise we will get classCasException.

http://www.csanimated.com/animation.php?t=Red-black_tree

8. SortedMap:

àIt is a child Interface of Map.

àIf we want to represent a group of key-value pairs according to some sorting order of keys.

9. NavigableMap:

àIt is a child Interface of SortedMap.

àIt defines several methods for navigation purpose we have to choose NavigableMap.

Utility Classes:
1. Arrays
2. Collections

Cursors:
1.  Enumeration
2.Iteratior
3.ListIterator

Sorting:
1.Comparable Interfaceàdefault
2.Comparator InterfaceàCustomise

Comparable	Comparator
Default natural sorting order	Customizing sorting order
Java.lang package	Java.util package
It defines only one method compareTo()	It defines two methods 1.compare() 2.equals()
String class, all wrapper classes implements Comparable Interface.	Only implement classes of Comparator Interface are 1. Collator 2.Rule Based Colletor

Because of below reasons, collections framework is best suitable

àIn Arrays, it is fixed in size where as in collections it is growable in nature.
àIn Arrays, Homogeneous Data Elements, where as in collections, Homo and Hetrogeneous Data Elements.
àwith respective to memory, Arrays concept is not recommended to use where as in collections it is recommended to use.
àNot implemented based on some data structure, Hence readymade method support is not available where as in collections implemented based on some data structure, Hence it is readymade method support is available.
àArrays can hold both primitive & object type where as collections can holds only object type not primitive.
àIf our frequent operation is search operation,the HashSet is the best choose.
àUsually we can use LinkedHashSet & LinkedHashMap for implementing cache applications where duplicates are not allowed & insertion order must be preserved.

Comparable Vs Comparator

àFor predefined comparable classes (like String) defaultNatural sorting order is already available.
If we are not satisfy with that natural sorting order we can define our own sorting by comparator objects.

àFor predefined non comparable classes(Like StringBuffer), default natural sorting order is already available, we can define our own sorting by Comparator object.

àFor our own classes (Like Employee), the person who is writing the class, he can define default natural sorting order by implementing Comparable Interface.
The person who is using our own classes, if he is not satisfied with default sorting order then he can define his own sorting by using Comparator object.


Concurrent HashMap:
1.Synchronized
2.ThreadSafe
3.FileSafe
4.1.5 version
5.Performance is low
6.Uses a multitude of locks, each lock controls one segment of the map. When setting data in a particular segment, the lock for that segment is obtained. So essentially update operations are synchronized.

How to get synchronized version of ArrayList,Hashset,HashMap?

ArrayList al=new ArrayList();
HashSet hs=new HashSet();
HashMap hm=new HashMap();

List l=Collections.synchronizedList(al);
Set s=Collections.synchronizedSet(hs);
Map m=Collections.synchronizedMap(hm);

ConcurrentHashMap

• Should use ConcurrentHashMap when we need very high concurrency in our project.
• It is thread safe without synchronizing the whole map.
• Reads can happen very fast while write is done with a lock.
• There is no locking at the object level.
• The locking is at a much finer granularity at a hashmap bucket level.
• ConcurrentHashMap doesn’t throw a ConcurrentModificationException if one thread tries to modify it while another is iterating over it.
• ConcurrentHashMap uses multitude of locks.

SynchronizedHashMap

• Synchronization at Object level.
• Every read/write operation needs to acquire lock.
• Locking the entire collection is a performance overhead.
• This essentially gives access to only one thread to the entire map & blocks all the other threads.
• It may cause contention.
• SynchronizedHashMap returns Iterator, which fails-fast on concurrent modification.

Fail Fast vs Fail Safe

List<String> someList = new ArrayList<String>()
// add "monkey", "donkey", "skeleton key" to someList

for(String item : someList ){
   System.out.println(item);
}

for(Iterator<String> i = someList.iterator(); i.hasNext(); ) {
    String item = i.next();
    System.out.println(item);
}




Reference document:

http://java.sun.com/developer/onlineTraining/collections/Collection.html
http://www.allapplabs.com/java/java_collection_framework.htm
http://www.javabeginner.com/java-collections/java-collections-framework
http://howtodoinjava.com/2012/10/09/how-hashmap-works-in-java/
http://www.corejavainterviewquestions.com/java-collections-data-structures-interview-questions/