Monday, July 13, 2015

Java Collection Framework - Internal walk through -1


                                                      In this tutorial I’m going to discuss about Java Collection Framework in a different way.Which means I’m going to discuss how the component works in this framework.Main forces of this tutorial is knowing which collection class suitable for which situation.
So.., let’s begin

Basic interfaces in Collection framework
Set: - collection of unique element
List: - collection of elements (might have duplicates)
Map: - collection of key, value pairs
Queue:-ordered collection of elements 

Concrete classes in collection framework
Maps : HashMap,HashTable,TreeMap
Sets   : HashSet,LinkHashSet,TreeSet
Lists  : ArrayList,Vector,LinkedList
Queues : PriorityQueue
Utilities : Collections,Arrays

List
List maintain the order which they are added.

ArrayList

                                                           ArrayList based on the principle of creating array and add data in to that.In ArrayList class has member variable call Object[] elementData.When we crerating new arraylist like this ,

List l=new ArrayList();

                                                           elementData array should initialize with size 10 . Using add(Element e) we can add one by one element to the ArrayList , After all the 10 locations are filled with elements ArrayList creating new different size(size>10) of array and coping old array to new one using Array.copyOf . That “different size” depend on the algorithm below.

    newSize=((oldSize*3)/2)+1;

                                                         On adding a element at a particular index in ArrayList using add(index i,Element e), ArrayList checks if a element is already present at that index. If no than the element passed in add() is added at that index, otherwise a new array is created with the index kept vacant and the remaining element shifted to right.
So, ArrayList is most suitable for frequently fetching and one time adding scenarios 

LinkList
                                                       Actulally the LinkList not using any primitives like arrays, etc. . . . It’s a collection object linked together using reference (Doubly Link List).
 LinkList has Entry class member variable called header. It’s the start element of LinkList.
                                                       Every time we calling add(element) new instance of Entry class created and attached it end of the list.
                                                      Calling add(element,position) means add a new element to specific position of the list.to do that operation shift the current element of that position and subsequent elements to the right add the new element to current position.
                                                      Invoking get(position) is more time consuming than ArryList  , because need to travers from the start node every time.
So, LinkLst is suitable for frequently adding and removing, not suitable for frequently fetching

Map
                                                     Map is special collection in collection framework which can frequently add and fetch easily. It’s not just adding elements to the list, Map allow you to add element as a key and other as a value.
 HashMap

                                                       HashMap is an implementation of the Map interface. It’s completely based on hashing principle. It store the values in form of key,vaule  pair. Use key to access to value.to get the efficient use of HashMap need to override the equal() and hashcode() methods in key element. equal()  method helps to compare the content of two object(not the memory location) and hashcode() return unique identifier to each object it helps to arranged the HashMap elements to separate buckets.So the elements in same hashcode put together in to a same bucket. Beacuse it’s support to when fetching elements using get(key) . First it identify the hash bucket then after uses equal() method to identify the actual object present in the bucket.
For the frequent access to the value HashMap using “Singly Linked List” .Number of buckets are depends on number of different hashcodes .To hold the set of buckets together use a array with initial size 12.Size will be change when different hashcode added.

newSize=oldSize*(3/2)

No comments:

Post a Comment