Java Collection

Collections Framework and Generics :

Introduction to java.util.package.
java.util package contains several classes to group/collect homogeneous and heterogeneous objects without size limitation. These classes are usually called collection framework classes.
A collection is an object that represent a group of objects.

What is a framework?
Framework is  semi finished reusable application which provides some common low level services for solving reoccurring problem and that can be customized according to our requirement.

Q. Why collection classes are given when we have Object[] to heterogeneous objects?
Array has below two problems
1) It allows us to store only same types of elements.
2) It is fixed in size.

The first problem can be solved using java.lang.Object[]. Using Object[] array object we can collect all types of objects.
But the second problem can not be solved automatically. We should develop below code to solve this problem:
-> Create array object with initial size and store elements.
-> Once array size is reached its capacity, execute below step to store new elements.
these steps are mandatory because it will not allow us to store new element after its size.
 Step #1: Create another temporary array with required size.
 Step #2: Copy old array values to new.
 Step #3: Add new element to new array at the end of all its elements.
 Step #4: Assign new array object reference to old array referenced variable.

 Example: Array object creation:

class ArrayCreation
{
public static void main(String [] args){
Object[] obj = new Object[4];

//Stroring elements
obj[0] = "50";
obj[1] = "60";
obj[2] = "70";
obj[3] = "80";

//size reached its capacity so further we can not store any more elements.
//1. so create new array object with required size
Object [] tempObj = new Object[10];

//Copy old array elements to new
int oldArraySize = obj.length;
int i =0;
for(i; i < oldArraySize; i++){
tempObj[i] = obj[i];
}
//3. storing new element at the end of new array object.
tempObj[i] = [90];

//4. Assigning new array object reference to old array referenced variable.
obj = tempObj;
}
}

The above array object creation logic should be develpoed in every java project which is threaded as code redundancy.

To solve all above problem SUN decided to implement collection classes common to every java project with high performance.

Advatages of Collection Framework:
-> Reduces programming effort by providing useful data structure and algorithms, so you don't have to write them yourself.
-> Increase performance by providing high-performance implementation of useful data structures and algorithms. because the various implementation of each interface are interchangeable,
programs can be easily tuned by switching implementation.
-> Provides interoperability between unrelated APIs by establishing a common language to pass collection back and forth.
-> Reduces the effort requied to learn API's by eliminating the need of multipe ad-hoc collection API.
-> Faster software reuse by proving a standard interface for collection and algorithms to manipulate them.


Collection: It is used to store/collect homogeneous or heterogeneous object without size limitations. Collection store/collect data in two format first one Array (collection) and second one key-value pair (map).

Collection: A root interface of all collection type object those stores object in array format.

collection: A word represent a group.

Collections: A utility class has all static method object to perform different operation on collection.

Element: A object stored in collection is called element.

Entry: A key-value added to map is called entry.

Homogeneous Object: Same class type of  objects are called homogeneous objects.

Heterogeneous Object: Different type of  objects are called heterogeneous objects.

Unique element: Heterogeneous object and homogeneous objects with different object or reference
                              is called unique elements.

Duplicate element: homogeneous objects with same object or reference is called duplicate elements.


Q. How many ways we can collect objects?
A. We can collect objects in 2 way:
1. in Array format- in this format object does not have identity.
2. in key,value pair format- in this format object has identity.

In Java 1.0 version SUN introduced only two classes Vector and Hashtable to collect object. these classes are called legacy classes.

1. Vector: Vector stores object in array format without identity.
2. Hashtable: It is stores objectin key-value pair format with identity.
In addition to above two classes we have one more class called Stack. It is a subclass of Vector class. It is used to store and retrieve objects in Last In First Out(LIFO) order.

Drawback of Vector and Hashtable classes: These two classes were created as thread-safe classes, means all the methods in these two classes are declared as synchronized. Hence
for every method call on these two Objects either for adding or removing elements. JVM locks and unlock these two Objects. It leads to performance issue in Single model application. in
single thread model application there is no data corruption, because in this model application execution is sequential, so we no need locking.

Hierarchy of Collection:

Interfaces: Iterator, Iterable, Collection, Set, SortedSet, NavigableSet.
Abstract Classes: AbstractCollection, AbstractSet, AbstractList, AbstractSequentialList, AbstractQueue.
Concrete Classes: TreeSet, HashSet, LinkedHashSet, LinkedList, ArrayList, Vector, Stack, PriorityQueue.

Hierarchy of Map: 

Interfaces: Map, SortedMap, NavigableMap.
Abstract Classes: AbstractMap.
Concrete Classes: TreeMap, HashMap, LinkedHashMap, Hashtable, Properties.

Collection Hierarchy: Using Collection classes we can collect unique and duplicate objects. so Collection divide into two categories Set and List.
Set: Set is unique collection, it will not allow duplicate element means same class object with same class state. Set is the super Interface for all unique collection classes.
Set is unordered means it stores element without index.
List: List is duplicate collection, it will allow duplicate element means same class object with same class state. List is the super Interface for duplicate collection classes.
List is ordered, means it stores each element with index.

SortedSet: It is a sub interface of Set that stores elements in sorted order either ascending or descending order based on the objects natural sorting order.
NavigableSet: It is the child Interface of SortedSet. It provides several methods to support navigation in TreeSet.
1. ceiling(e): It returns the lowest element which is ">=e".
2. higher(e): It returns the lowest element which is ">e".
3. floor(e): It returns the highest element which is "<=e".
4. lower(e): It returns the highest element which is "<e".

Queue: It is the child interface of Collection. usually Queue follows the FIFO order, but based on our requirement we can change its order.
-> LinkedList based implementation of Queue always follows FIFO order.

Vector: Vector class stores data in array format without identity. vector is a thread-safe.

Q. How can we store and get data from vector class?
create the vector class object by using available constructor.
-> Call add() method to add elements to vector object.
-> call get() method to retrieve elements from vector object.

We can create vector class in two ways:
1) public vector() -> It create an empty vector object with default capacity 10.
2) public default(int capacity) -> It create an empty vector object with given capacity.

Note: Capacity should not be negative number else it will throws exception java.lang.IllegalArgumentExcption.

Example:

import java.util.*;

class VectorDemo
{
public static void main(String [] args){
Vector v = new Vector();

System.out.println("vector Capacity is : " + v.capacity());
System.out.println("vector size is : " + v.size());
System.out.println(" ===== ");

//Adding elements
v.addElement("1");
v.addElement("2");
v.addElement("3");

//Now check capacity and size
System.out.println("vector Capacity is : " + v.capacity());
System.out.println("vector size is : " + v.size());
System.out.println("vector elements : " + v);
}
}

Output:

vector Capacity is : 10
vector size is : 0
 =====
vector Capacity is : 10
vector size is : 3
vector elements : [1, 2, 3]

addElement(): public void addElement(Object obj) : It adds the elements to vector object at the end of current element.

Note:
-> Vector class can't stores elements with identity. --> Sun introduced Hashtable.
-> Vector class is thread safe so it leads performance issue in single threaded model application. --> Sun introduced ArrayList.
-> Vector class gives less performance in doing insertion and deletion operation in middle because of elements movement. --> Sun introduced LinkedList.
-> Vector class doesn't store elements in sorting order. --> Sun introduced TreeSet.
-> Vector class can't stop adding duplicate elements. --> Sun introduced HashSet.


Hashtable: It allow us to stores elements in key-value pair. By using Hashtable we can store and transport elements with identity.
Key object should be unique but value object can be duplicated. Both key and value should be not null. Default capacity is 11 and load factor .75.

Hashtable object creation:
1. public Hashtable(): It creates empty hashtable with default capacity 11 and load factor .75.
2. public Hashtable(int initialCapacity): It creates empty hashtable with given capacity and load factor(.75).
3. public Hashtable(int initialCapacity, float loadFactor): It creates empty hashtable with given capacity and load factor.
4. public Hashtable(Map m): It creates hashtable with entries available in given map. This constructor given in 1.2.

public object put(Object key, object value): It store entry by mapping value to given key. If key is already exist it replace old value with new passed value and return old value object.

public object get(Object key): It returns value object that mapped with the given key. If key not found it returns null.

Exmple:

import java.util.*;

public class HashtableDemo {
public static void main(String [] args){
Hashtable ht = new Hashtable();

//Adding entry
ht.put("1","Singrauli");
ht.put("2","Bhopal");
ht.put("3","Banglore");
System.out.println("Hashtable entry : " + ht.get("3"));

ht.put("3","Pune");
System.out.println("Hashtable entry : " + ht.get("3"));

}
}

Output:

Hashtable entry : Banglore
Hashtable entry : Pune


Enumeration : Enumeration is an Interface used for retrieving elements from the Collection Object. It is a cursor object.
Enumeration has two methods:
1. public boolean hasMoreElements(): To check elements available or not.
2. public Object nextElement() : To returns that elements.

Rule: nextElement() method should not be called on empty collection object or on empty location. It leads to exception java.util.NoSuchElementException.
Enumeration e = ?    ----> ht.keys().
while(e.hasMoreElements()){
Object obj = e.nextElement();
System.out.println(obj);
}

Enumeration key(): It returns enumeration of the keys in this hastable. It means it return enumeration subclass object with current hashtable object keys.
Enumeration elements() : It returns an enumeration of the values in this hashtable.

Hashtable ht = new Hashtable();
Enumeration e = ht.keys();
OR
Enumeration e = ht.elements();

Example: Write a program to create Hashtable object with same entries for eg employee id and its salary.
-> print all employee ids and their salary.
-> give increment to second employee 1000/- Rs.
-> print again complete list of employee.

import java.util.*;

class EnumerationDemo{

public static void main(String[] args){
Hashtable ht = new Hashtable();
ht.put("7279", new Double(999));
ht.put("7280", new Double(9999));
ht.put("7281", new Double(99999));

//retrieving all entries
Enumeration e = ht.keys();
Object key;
Object value;

while(e.hasMoreElements()){
key = e.nextElement();
value = ht.get(key);
System.out.println(key + " ===== " + value);
}

// Increment 1000 rs to 7280 employee
Object empid = ht.get("7280");
Double salObj = (Double) empid;
Double sal = salObj.doubleValue();

sal = sal + 1000;
ht.put("7280", new Double(sal));

System.out.println(ht.get(7280));

  }
}

Q) In what what order elements are stored?
Vector : Insertion order with index.
Hashtable : Based on hashCode.

Q) How can we removed elements from vector and Hashtable.
Vector: By passing either object or index.
Hashtable: By passing key.

Q) Is null allowed:
Vector: Allowed.
Hashtable: Not Allowed.

Q) How Collection search for given elements in its object for either.
1). Removing.
2. Retrieving.
3. searching.

Explain about equals() and hashCode():

equals(): equals() is predefined method given in java.lang.Object class. It is given for compare two objects. It compare current object with argument based on its implementation
and returns true or false. Its default implementation java.lang.Object class is to compare object with reference.
If we want to compare objects with their state we must override it in subclass.

-> If equals() method returns true the two objects are duplicate.
-> If equals() method returns false the two objects are unique.

Q. Is equals() method checking based on state or reference?
A. It is depending on "equals()" method implementation. If equals() method is overridden in the adding objects class then objects are compared by using state else they
are compared by using reference because in this case equals() methods called from Object class. In Object class it compares object by using reference.

Q. What is the problem if we don't override equals() method in subclass.
A. The added element is not found with its class new object because the passed argument object is compared with Collection element by using reference as equals() called from Object class.

import java.util.*;

class EqualsDemo
{
public static void main(String [] args){
Vector v = new Vector();

v.add("a");
v.add("b");
v.add("a");
v.add(new Interger(10));
v.add(new A());
}
}

In the above case String objects and Integer objects are removed with new objects because they are compared by using state.
A object is not removed with new object because this new object reference is not equals to A objects reference available in Collection as equals() method is calling from object class.

Solution for above problem: We must override equals() method in A class to find A object either with reference or with state.
 Overriding equals() method in A class:
 class A{
  int x = 10;
  int y = 20;

  public boolean equals(Object obj){
    if(this == obj){
return true;
} else if(obj insteadOf A){
A a = (A) obj;
return this.x = a.x && this.y = a.y;
}
  }
  public static void main(String [] args){
A a1 = new A();
A a2 = a1;
System.out.println(a1 == a2);
 }

Contract in overriding equals(): 
1. We should check argument object is current class type and not for returning false instead of throwing ClassCastException, so that Collection add
method internal logic decides this add add method argument object should add or not.
-> For incompatible objects comparison should not throw ClassCastException instead should be return false.
2. Also for null value comparison should return false instead NullPointerException.

Note-> To develop both contract we must use "insteadOf" operator. 

hashCode(): It is a predefined method given in java.lang.Object class.
-> It is given for returning objects hashCode based on implementation.
-> hashCode() default implementation in java.lang.Object is to return an int number by converting its reference to a number.
-> If we want to return hashCode with the objects state we must override it in subclass.
-> hashCode() is 32-bit (int datatype) number used to identity object and for separating one object from another object.
-> hashCode() is used to store and search element in Collection with data Structure hashtable.

Q. What is the problem if we don't override hashCode() method in subclass?
A. At the time of adding entries duplicate key entries are added and also at the time of retrieving entries keys are not found with different reference object or with new
objects of the same key type.
-> In addition to hashCode() method we must override equals() methods else it leads to same above problem.

Example:
class Student
{
int sno;
int whichclass;
String name;

Student(int sno, int whichclass, String name)
{
this.sno = sno;
this.whichclass = whichclass;
this.name = name;
}

public boolean equals(Object obj)
{
System.out.println("In equals");
if (obj instanceof Student)
{
Student s = (Student)obj;
if (this.sno == s.sno && this.whichclass == s.whichclass && this.name.equalsIgnoreCase(s.name))
{
return true;
}
}
return false;
}

public int hashCode()
{
System.out.println("In hashcode");
int size = this.name.length();
int result = 1;

for (int i = 0 ; i < size ; i ++ )
{
result = result + (name.charAt(i) ) ;
}

return  this.sno + this.whichclass + result;
}
public String toString()
{
return sno+ "-"+ whichclass +"-" + name;
}
}

Working functionality of hashtable data Structure:
-> hashtable internally uses the data structure called "bucket". It uses bucket concept for fast searching and retrieving of the key.
-> It creates bucket for every new hashCode key entry and store entry in that bucket.
-> If the bucket is already available with the current key hashCode.
-> If key is same then it replaces that key old value with new value and return old value object.
-> If key is different it stores this entry with new hashCode() in bucket.

To retrieve given key mapped value:
1. It search for bucket with given search key hashCode.
2. If bucket found then it compare that bucket keys with the given search key by using equals() method.
  a. If keys is matched it returns that key mapped value object reference.
b. If key is not matched it returns null.
3. If bucket is not found it directly returns null.

Q. How does bucket concept increase performance?
A. It doesn't compare search key with all keys available in Hashtable instead it compare only with key those are available in search key hashCode matched bucket.

put() method algorithm (internal logic):
1. When we create Hashtable object, internally empty hashtable is created.
2. put() method creates new bucket in this hashtable for every new key and mark that bucket with this key hashcode. For this purpose:
-> It call hashCode() on current add entry key.
-> It search for the bucket with the returned hashCode().
-> If bucket is not found it creates bucket and mark it with that hashCode and stores this entry in this bucket.
-> If bucket found now it calls equals() method on search key by passing current bucket all keys.
-> If any key comparison returns true, then it override old value with new value.
-> If equals() method returns false, then it directly adds the entry.
-> Now bucket has more than one key.

get(), remove(), contains() methods internal logic: 
-> get() method return given key associated value if key is not found it return null.
-> remove() method removes the given key and its associated value and return that value. If key is not found it does nothing and return null.
-> contains() search for the given key. If it is found returns true else returns false.

Above three method internal logic (only contains method):
Inside this method -
-> First hashCode() method is called on the given search key to find object.
-> If bucket not found  it returns false.
-> If bucket is found, internally equals() method is called on search key by passing bucket key for retrieving the key mapped value.
-> If equals() returns true -
     -> The value object return by get() method.
-> The value object removed by remove() method.
-> The value object returns true by contains() method.

-> If equals() returns false -
     -> get() and remove() methods return null.
-> contains() methods return false.


ArrayList:
-> The underlying data structure is resizeable array.
-> Insertion order is preserved .
-> Duplicate objects are allowed.
-> Heterogeneous objects are allowed.
-> null insertion is possible.
->  Random access.
-> Initial capacity of ArrayList is 10.

Example:
import java.util.*;

class ArrayListDemo
{
public static void main(String [] args){
ArrayList al = new ArrayList();

//Adding elements
al.add("A");
al.add("B");
al.add("C");

System.out.println("ArrayList is : " + al);
al.remove(1);
System.out.println("ArrayList after remove : " + al);
}
}

Output:
ArrayList is : [A, B, C]
ArrayList after remove : [A, C]

LinkedList: The underlying data structure is double LinkedList.
-> Insertion order is preserved.
-> Duplicate objects are allowed.
-> Heterogeneous objects are allowed.
-> Implements Serializable,  Clonable but not random access.
-> LinkedList is best suitable if our frequent operation is insertion or deletion in the middle because no shift operations required.
-> It is slow at the time of retrieving.

Stack: It is Child class of Vector. It contains only one constructor.
Stack s = new Stack().

Methods:
object push(Object obj): To add an object into the Stack.
object pop(): To remove and return top of the Stack.
object peak(): To return top of the Stack without removal.
boolean empty(): return true if the Stack is empty.
int search(): return the offset of the element from top of the Stack if it is not available return -1.

TreeSet: The underlying data Structure is balanced tree.
-> Duplicate objects are not allowed.
-> Insertion order is not preserved but all objects are stored in natural sorting order.
-> Heterogeneous objects are not allowed otherwise we will get ClassCastException.
-> null insertion is possible only once.

HashSet: The underlying data structure is hashtable.
-> Insertion order is not preserved and it is based on hashCode() of the objects.
-> Duplicate objects are not allowed if we are trying to add duplicate object we will not get any compile time or run time exception add() method simply returns false.
-> Heterogeneous objects are not allowed.
-> null insertion is possible only once.
-> implements Serializable and Clonable Interface.
->  HashSet is best suitable if our frequent operation is search operation.
-> Initial capacity is 16 and default load factor 0.75.

LinkedHashSet: Introduced in 1.4 version. It is the child class of HashSet.
-> The underlying data structure is combination of Hashtable and LinkedList.
-> Insertion order is preserved.

Iterator Interface: It is introduced in 1.2 version. Iterator is universal cursor and we can apply for any collection object.
-> By using Iterator we can retrieve and remove the object.
-> This interface defined the following methods:
-> public boolean hasNext().
-> public object next().
-> public void remove().

ListIterator: It is a child interface of Iterator while iterating the objects we can perform read, remove, replace and addition of new object also.
-> ListIterator is a bi-directional cursor we can move either to the forward direction (or) to the backward direction.

Map: If we want to represent a group of objects as key-value pairs then we should go for the Map Interface.
-> Both key and value are objects.
-> Duplicate keys are not allowed but value can be duplicated.
-> Each key - value pair is considered as one entry object.

HashMap: The underlying data structure is Hashtable.
-> Insertion order is not preserved and it is based on hashCode of the keys.
-> Duplicate keys are not allowed and value can be duplicated.
-> Heterogeneous objects are allowed for both keys and values.
-> null keys is allowed only once but we can use null for value any number of times.
-> Initial capacity 16 and default load factor "0.75".

Note: We can get Synchronized version of HashMap by using SynchronizedMap() method of Collection class. Collections.SynchronizedMap(Map m).

LinkedHashMap: It is underlying data structure is Hashtable + LinkedList.
-> Insertion order is preserved.

IdentityHashMap(): It is the child class of Map. IdentityHashMap is not child class of HashMap.
-> It is exactly same as HashMap to identify duplicate keys internally equals() method will be used but in the case of IdentityHashMap to check duplicate keys internally "==" operator will be used.

WeakHashMap: Its exactly same as HashMap except the following difference. on the case of HashMap even though object doesn't have any external reference still it is not eligible for gc.garbageCollection().
-> If it is associated with HashMap i.e. HashMap dominates garbage collector, but in the case of WeakHashMap an object is always eligible for garbage collection. If does not have any external reference.
-> Even though it is associated with WeakHashMap i.e. garbage collector always   dominates WeakHashMap.

SortedMap: It is the child Interface of Mp.
-> If we want to represent a set of key-value pars according to some sorting order of keys, then we should go for SortedMap.
-> Sorting should be doe based on the keys but not based on values.

TreeMap: The underlying data Structure is red-black tree.
-> Duplicate keys are not allowed but value can be duplicated.
-> Insertion order is not preserved and it is based on some sorting order of keys.

Note: If we are depending on default natural sorting order, then the keys should be homogeneous and comparable otherwise we will get ClassCastException.

- If we are defining our own sorting order by comparator then the keys need not be homogeneous and comparable. there are no restrictions on values they can be heterogeneous and non-comparable.
-> For the empty TreeMap as the first entry with 'null' keys is allowed but inserting that entry if we are trying to insert any other null entry we will get NullPointerException.

Properties: Properties class is child class of Hashtable. In our program if anything which is going to change frequently like mail-id, contract number, database credential etc. never recommended to hard code inside java code.
-> For every change compulsory we have to re-compile, rebuild and re-deploy is required and sometimes even restart also required. It creates a big business impact to the client.
-> We have to configure such type of values inside properties file if there is change in the properties file just redeployment is enough.
-> In properties compulsory both key and value should be string type only.

PriorityQueue: It is the data structure which can be used to represent a group of individual objects prior to processing according to some priority.(It can be default natural sorting/customized order).
-> Insertion order is not preserved.
-> If we are depending default natural sorting order then the object should be homogeneous and comparable.
-> If we are defining our own customized sorting order by comparator then the object should be need not be homogeneous and comparable.
-> null insertion is not possible even as the first element also otherwise will throw NullPointerException.
-> Duplicate objects are not allowed.

Q. Wwhat is the difference between ArrayList and Vector.

ArrayList	Vector
1.      No Method is Synchronized.         2.      Multiple Threads can access Simultaneously and hence it is not Thread Safe. 3.      Threads are not required to wait to access ArrayList hence performance is high. 4.      Introduced in 1.2 version.	1.      All methods are Synchronized. 2.      Multiple Thread can't access Simultaneously and hence Vector is Thread Safe. 3.      Threads are required to wait to access Vector hence waiting time of the threads increases and effects performance. 4.      Introduced in 1.0 version.

 

Q.  what is the difference between HashSet and LinkedHashSet

HashSet	LinkedHashSet
1.      The underlying data structure is hashtable. 2.      Insertion order is not preserved. 3.      Introduced in 1.2 version	1.      the underlying data Structure is combination of hashtable + LinkedList. 2.      Insertion order is preserved. 3.      Introduced in 1.4 version.

Q. what is the difference between Comparator and Comparable.

Comparator	Comparable
1.      If we want to define our own customized sorting order then we should go for comparator. 2.      It is defined in java.util. 3.      It contains two methods compare() and equals().               4.      No predefined class implements comparator.	1.      If we want to define natural sorting order then we should go for comparable. 2.      It is in java.lang. 3.      It contains one method compareTo(). 4.      All wrapper classes and string classes implements Comparable.

                             

Q.  what is the difference between Enumeration, Iterator and ListIterator.

property	Enumeration	Iterator	ListIterator
1.      Is it legacy 2.      Applicable 3.      Movement 4.      How to get 5.      Accessibility	Yes only for legacy   Single direction (forward). By using elements.   only read.	No Any Collection Single direction (forward). By using Iterator. read and remove.	No Only for List object. bi-direction (forward and backward). By using ListIterator. read, remove, replace and add.

Q. what is the difference between HashMap and Hashtable.

HashMap	Hashtable
1.      No method is Synchronized. 2.      It is not Threadsafe. 3.      Performance is high.        4.      null is allowed for both key and value. 5.      Introduced in 1.2 version and non-legacy.	1.      Every mehods are Synchronized. 2.      It is Threadsafe. 3.      performance is low. 4.      null is not allowed for both key and value else NullPointerException. 5.       Introduced in 1.0 version and legacy.

                                                                                                                        5.            5                           

Q.  what is the difference between HashMap and LinkedHashMap.                                                                      

HashMap	LinkedHashMap
1.      The underlying data structure is hashtable. 2.      Insertion order is not preserved. 3.      Introduced in 1.2 version.	1.      The underlying data structure is hashtable + LinkedList. 2.       Insertion order is preserved 3.      Introduced in 1.4 version.