Wednesday, 2 August 2017

Collection



Best Question Of COLLECTIONS :-

LinkedList
How LinkedList internally store  value and how they mentain the insertion order?

public class LinkedTest
{
       public static void main(String args[])
       {     
             LinkedList<String> ls = new LinkedList<String>();
             ls.add("X");
             ls.add("Y");
             ls.add("Z");
             ls.add("A");
             ls.add("D");
            
             for (String string : ls) {
                    System.out.println(string);
             }      }
}

Note:-

  • LinkedList Store starting value in “first” and Ending value in “last” node.
  • It can store duplicate elements
  • First Node contain “value” in “item” and as well as “next” and “prev” node contain value of next and previous node
  • By using prev and next node it will maintain insertion order
  • First node contain prev as null because of it is the first node.
  • Last node contain next as null because of it is last node.


LINKEDHASHSET

  • contains unique elements only like HashSet. It extends HashSet class and implements Set interface.
  • maintains insertion order.
How LinkedHashSet internally store  value if they have hashing mechanism and how they maintain the insertion order ?

public class LinkedTest
{
       public static void main(String args[])
       {     
             LinkedHashSet<String> list = new LinkedHashSet<String>();
             list.add("Akshay");
             list.add("Karan");
             list.add("Sandy");
             list.add("Priya");
             list.add("Shikha");
              for (String string : list) {
                    System.out.println(string);
             }      }
}

Note:-
  • LinkedHashSet Store starting first value in “head” and Ending value in “tail” node.
  • Head Node contain “value” in “Key” and as well as “after” and “before” node contain value of “next” and “previous” node
  • By using “after” and “before” node it will maintain insertion order
  • First node contain “before” as null because of it is the first node.
  • Last node contain “next” as null because of it is last node.
  • Set internally use map. So LinkedHashSet internally use LinkedHashMap
  • Set or LinkedHashSet can not insert duplicate element.
  • It internally maintain one table in which they store value based on hashing mechanism


LINKEDHASHMAP
  • A LinkedHashMap contains values based on the key. It implements the Map interface and extends HashMap class.
  • It contains only unique elements.
  • It may have one null key and multiple null values.
  • It is same as HashMap instead maintains insertion order.
 How LinkedHashMap internally store  value if they have hashing mechanism and how they mentain the insertion order ?

public class LinkedTest
{
    public static void main(String args[])
    { 
LinkedHashMap<String, Integer> linkedMap =new LinkedHashMap<String,Integer>();
       linkedMap.put("Akshay", 1);
       linkedMap.put("Karan", 10);
       linkedMap.put("Sahil", 12);
       linkedMap.put("Prem", 32);
       linkedMap.put("Karan", 45);            
       for (Entry<String,Integer> entry : linkedMap.entrySet()) {
             System.out.println(entry.getKey() + " : " + entry.getValue());
       }
   }
}

Note:-
  • LinkedHashMap Store starting first value in “head” and Ending value in “tail” node.
  • Head Node contain “value” in “Key” and as well as “after” and “before” node contain value of “next” and “previous” node
  • By using “after” and “before” node it will maintain insertion order
  • First node contain “before” as null because of it is the first node.
  • Last node contain “next” as null because of it is last node.
  • Set or LinkedHashMap will override if we insert same key value after checking its hashcode and equality.
  • It internally maintain one table in which they store value based on hashing mechanism





4):- How LinkedHashMap internally store  value if they have hashing mechanism and how they maintain the insertion order and What happened in LinkedHashMap if the Object is used as key

class Employee {
       public int Id;
       public String Name;

       public Employee (int id, String name) {
             this.Id = id;
             this.Name = name;
       }
      
       @Override
       public int hashCode() {
             return this.Id;
       }
      
       @Override
       public boolean equals(Object obj) {
             Employee emp = (Employee)obj;
             return this.Name.equals(emp.Name);
       }
}

public class LinkedTest
{
    public static void main(String args[])
    { 
             LinkedHashMap<Employee, String> linkedHashMap = new
                                                  LinkedHashMap<Employee, String>();
             linkedHashMap.put(new Employee (809, "Akshay"), "Akshay");
             linkedHashMap.put(new Employee (801, "Karan"), "Karan");
             linkedHashMap.put(new Employee (805, "sahil"), "Sahil");
             linkedHashMap.put(new Employee (809, "Guru"), "Guru");

             for (Entry<Employee, String> entry : linkedHashMap.entrySet()) {
                    System.out.println(((Employee)entry.getKey()).Id + " " + ((Employee)entry.getKey()).Name  + " : " + entry.getValue());
             }   }
}

Note:-
  • If we use Object as key in Map then if we are not override hashCode and equals methods then will not return same hashCode for everyObject which have same property. So its better to provide hashCode so that you can return hashCode based on your requirement and check equality based on your requirement .


Hash Set
  • contains unique elements only.
  • Can contain null value (but only one null value) 
  • It internally store element based on hashCode.It maintain table internally to store element. 
  •  It internally maintain HashMap. 
  • It does not contain duplicate element. And it check duplicity by using hashCode and equal.



Tree Set
  • It doesnot allow duplicate. 
  • contains unique elements only like HashSet. The TreeSet class implements NavigableSet interface that extends the SortedSet interface.
  • maintains ascending order. 
  • It check duplicity by using the compare/compareTo method. If it return 0 then It will not allow element to add into treeSet



package com.akshay.CollebraProgramms;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.TreeMap;
import java.util.TreeSet;

class Customer implements Comparable<Customer> {
       public int Id;
       public String Name;
       public String Department;

       public Customer(int id, String name, String department) {
             this.Id = id;
             this.Name = name;
             this.Department = department;
       }

       @Override
       public int hashCode() {
             return this.Id;
       }

       @Override
       public boolean equals(Object obj) {
             Customer emp = (Customer) obj;
             return this.Name.equals(emp.Name);
       }

      
       @Override
       public int compareTo(Customer emp) {
             return this.Id == emp.Id ? 0 : this.Id > emp.Id ? 1 : -1;
       }

}

public class TreeTest {
       public static void main(String args[]) {
             TreeSet<Customer> treeSet = new TreeSet<Customer>();
             treeSet.add(new Customer(809, "Akshay", "IT"));
             treeSet.add(new Customer(801, "Karan", "CS"));
             treeSet.add(new Customer(805, "sahil", "EC"));
             treeSet.add(new Customer(809, "Rahul", "ME"));    //Not allowed
             treeSet.add(new Customer(801, "Karan", "PK"));    // Not allowed
             for (Customer Customer : treeSet) {
                    System.out.println(Customer.Id + " " + Customer.Name+ " " + Customer.Department);
             }
       }
}
Output :-
801 Karan CS
805 sahil EC
809 Akshay IT



MAP :-

·      It’s an interface
·      It store value in key value pair.
·      If you want unique element then you use this interface.
·      Value store in key and value pair
·      Fetch value based on key
Three type :- Hashmap and tree map and LinkedHashMap

a):- Tree Map:- for sorting use tree map

·      A TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.
·      It contains only unique elements.
·      It cannot have null key but can have multiple null values.
·      It is same as HashMap instead maintains ascending order.
·      It uses Left and Right node to store values Based on it return ascending or descending Order.
·      If we use Object as Key then its necessary to implement Comparable or Comparator and override compare method to check the objects less then or Greater then value.
·      If Compare/CompareTo method return 0 then it will override then it will not change the “key” but it override “Value”





package com.akshay.CollebraProgramms;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.TreeMap;
import java.util.TreeSet;


//For TreeSet/TreeMap its mandatory to implement Comparable/Comparator
class Customer implements Comparable<Customer> {
       public int Id;
       public String Name;
       public String Department;

       public Customer(int id, String name, String department) {
             this.Id = id;
             this.Name = name;
             this.Department = department;
       }

       //For TreeSet/TreeMap its mandatory to override Compare/CompareTo method
       @Override
       public int compareTo(Customer emp) {
              return this.Id == emp.Id ? 0 : this.Id > emp.Id ? 1 : -1;
       }

}

public class TreeTest {
       public static void main(String args[]) {
            
             TreeMap<Customer, String> treeMap = new TreeMap<Customer, String>();
             treeMap.put(new Customer(809, "Akshay", "IT"), "Akshay");
             treeMap.put(new Customer(801, "Karan", "CS"), "Karan");
             treeMap.put(new Customer(805, "sahil", "EC"), "Sahil");
             treeMap.put(new Customer(809, "Akshay", "ME"), "Guru");
             treeMap.put(new Customer(805, "SRK", "EC"), "SRK");
            
             for (Entry<Customer, String> entry : treeMap.entrySet()) {
                    System.out.println(((Customer) entry.getKey()).Id + " " + ((Customer) entry.getKey()).Name + " " + ((Customer) entry.getKey()).Department + " : " + entry.getValue());
             }
       }
}




Output:-
801 Karan CS : Karan
805 sahil EC : SRK
809 Akshay IT : Guru
Here 809 is equal for both object [Akshay,ITè Akshay] and [Akshay, MEè Guru] So it made Key value as [Akshay IT è Guru]

 Hash map :-
·      A HashMap contains values based on the key. It implements the Map interface and extends AbstractMap class.
·      It contains only unique elements.
·      It may have one null key and multiple null values.
·      It maintains no order.




Here elimination mean if the keys are same then it will override  previous one and store latest value.
Ex:-
If you are inserting set like:-
Input:-
Key      Value
1             “A”
2              “B”                
3             “C”
4              “D”
4               “E”


Then  4 with “D” will be override  with “E”
And output will be
Output:-

Key      Value
1             “A”
2              “B”                
3             “C”
4               “E”        Latest value.

Note:-
Note:-  It may be key are different but their hashCode value same then this is called collision. It is handled by internally maintain linked list for same type of hash coded values.


·   

Hash Table :-

  • A Hashtable is an array of list.Each list is known as a bucket.The position of bucket is identified by calling the hashcode() method.A Hashtable contains values based on the key. It implements the Map interface and extends Dictionary class.
  • It contains only unique elements.
  • It may have not have any null key or value.
  • It is synchronized.


Example of Hashtable:


import java.util.*;  
class TestCollection16{  
 public static void main(String args[]){  
   
  Hashtable<Integer,String> hm=new Hashtable<Integer,String>();  
  
  hm.put(106,"Rahul");
 hm.put(100,"Amit");
 hm.put(102,"Ravi");
 hm.put(101,"Vijay");
 hm.put(103,"Rahul");
 hm.put(110,"Rahul");  
  for(Map.Entry m:hm.entrySet()){  
   System.out.println(m.getKey()+" "+m.getValue());  
  }  
 }  
}  


Output :-
106 Rahul
103 Rahul
102 Ravi
101 Vijay
100 Amit
110 Rahul

Differences between HashMap and Hashtable?

There are several differences between HashMap and Hashtable in Java:
1.   Hashtable is synchronized, whereas HashMap is not. This makes HashMap better for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones.
2.   Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.
3.   One of HashMap's subclasses is LinkedHashMap, so in the event that you'd want predictable iteration order (which is insertion order by default), you could easily swap out the HashMap for a LinkedHashMap. This wouldn't be as easy if you were using Hashtable.
Since synchronization is not an issue for you, I'd recommend HashMap. If synchronization becomes an issue, you may also look at ConcurrentHashMap.


ConcurrentHashMap

  • You should use ConcurrentHashMap when you need very high concurrency in your 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.