IdentityHashMap in Java

IdentityHashMap in Java

IdentityHashMap  

IdentityHashMap implements Map interface as same as HashMap class. This class has been added from Java 1.4 and used very minimal across the programmers. Basically IdentityHashMap holds special implementation of Map interface which won't override equals() and hashcode() methods for object comparison. Instead it uses "==" operator to compare each objects of key and value. 
So lets see the difference between HashMap and IdentityHashMap in Java,

• HashMap overrides equals() and hashcode() methods to compare objects, where as IdentityHashMap used only "==" operator to compare key and value. IdentityHashMap wont use object.hashCode() but uses System.identityHashCode(object) because we can use IdentityHashMap for mutable objects for whose hash code changes during the "in map" time frame.
• For example when we use HashMap the object values can be directly changed which leads to strange behavior while IdentityHashMap works fine.
• Next for using large maps which uses equals() and hashcode() will lead to expensive and in those cases we can switch to IdentityHashMap because both methods are not overridden in this class. Important using IdentityHashMap also specific to application. 

These are major difference between HashMap and IdentityHashMap in Java. Now lets see simple example with both HashMap and IdentityHashMap implementation classes.

import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Map;

public class IdentityHashMapTest {

 public static void main(String[] args) {
  
  Map<String, String> hm = new HashMap<String, String>();
  Map<String, String> ihm = new IdentityHashMap<String, String>();
  
  hm.put("java", "111");
  hm.put(new String("java"), "222");
  hm.put("java", "333");
  
  ihm.put("java", "111");
  ihm.put(new String("java"), "222");
  ihm.put("java", "333");
  
  System.out.println("HashMap Size         : "+hm.size());
  System.out.println("IdentityHashMap Size : "+ihm.size());
  
  System.out.println("HashMap Values         : "+hm);
  System.out.println("IdentityHashMap Values : "+ihm);
 }
}

OUTPUT:

HashMap Size         : 1
IdentityHashMap Size : 2
HashMap Values         : {java=333}
IdentityHashMap Values : {java=333, java=222}

In above example if we see the size of both HashMap and IdentityHashMap is 1 and 2. Since HashMap overrides equals() and hashcode() methods it will compare object level of key and replaces for 1st 2 key and value which are trying to put in HashMap and remains only 1 key in Map.
Next when we see IdentityHashMap the size is 2, because "java" and new String("java") are considered as 2 different Objects. So it holds 2nd and 3rd value in Map.  

PriorityBlockingQueue in Java

PriorityBlockingQueue in Java

Queue  

In our last tutorial we have see about PriorityQueue and how its used in Java with simple example. In this tutorial we will see about PriorityBlockingQueue and it works and also the difference between PriorityQueue and PriorityBlockingQueue. 

• PriorityBlockingQueue uses same unbounded blocking queue that uses the same ordering rules as PriorityQueue and supplies blocking retrieval operations. 
• PriorityBlockingQueue does not allow null values to be added.
• PriorityBlockingQueue also uses natural sorting order and will not permit non-comparable objects to be insert which will result in ClassCastException exception.
• PriorityBlockingQueue uses methods as same as PriorityQueue class except drainTo() and remainingCapacity() methods. 
• drainTo(Collection<? super E> c) method used remove all available elements from the queue and adds them to the given collection.
• drainTo(Collection<? super E> c, int maxElements) method used to remove at most the given number of available elements from the queue and adds them to the given collection.
• remainingCapacity() method used to return Integer.MAX_VALUE because a PriorityBlockingQueue is not capacity constrained.
• Method iterator() is not guaranteed to traverse the elements of PriorityBlockingQueue in any particular order. We can see this in below example. 

Difference Between PriorityBlockingQueue and PriorityQueue:

• PriorityQueue is not thread safe, where as PriorityBlockingQueue is thread safe. 
• PriorityBlockingQueue introduced in JDK 5 which added with concurrent package. 

Now lets see simple example for PriorityBlockingQueue and how its working under multi-threading.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.PriorityBlockingQueue;

public class PriorityBlockingQueueTest {
 
 PriorityBlockingQueue<String> priBlockQ = new PriorityBlockingQueue<String>();
 
 public PriorityBlockingQueueTest(){
  priBlockQ.add("300");
  priBlockQ.add("400");
  priBlockQ.add("100");
  priBlockQ.add("500");
  priBlockQ.add("200");  
 }
 
 public void performTask() {
  // traversing order not guaranteed
  System.out.println("\nQueue iterator() : ");
  Iterator<String> itr = priBlockQ.iterator();
  while (itr.hasNext()) {
   String string = (String) itr.next();
   System.out.print(string+", ");
  }
  
  System.out.println("\n\nList iterator() : ");
  List<String> list = new ArrayList<String>();
  priBlockQ.drainTo(list);
  itr = list.iterator();
  while (itr.hasNext()) {
   String string = (String) itr.next();
   System.out.print(string+", ");
  }
  
  System.out.println("\n\ncontains() : "+priBlockQ.contains("400"));
  System.out.println("\nremainingCapacity() : "+priBlockQ.remainingCapacity());
 }
 
 public static void main(String[] args) {
  new PriorityBlockingQueueTest().performTask();
 }
}

OUTPUT:

Queue iterator() : 
100, 200, 300, 500, 400, 

List iterator() : 
100, 200, 300, 400, 500, 

contains() : false

remainingCapacity() : 2147483647

PriorityQueue in Java

PriorityQueue in Java

Queue  

PriorityQueue is unbounded priority queue based on priority heap. 

• Basically PriorityQueue are ordered according to natural ordering or by a Comparator provided at queue construction time, depending on which constructor is used. 
• Another important that PriorityQueue won't take null value as input. 
• Since PriorityQueue reply on natural ordering it won't take non-comparable object as input which will throw ClassCastException. 
• Internally memory size will be managed automatically as and when elements added to the PriorityQueue.
• By using Iterator interface its not guaranteed to traverse the elements of the PriorityQueue in any particular order. For ordered traversal need to use Arrays.sort(pq.toArray()). 
• By implementation PriorityQueue is not synchronized and non-thread safe. Suppose if we need synchronized/thread-safe Queue then we need to go for PriorityBlockingQueue class instead of PriorityQueue.

Lets see list of constructors and methods in PriorityQueue class.

Constructors:

PriorityQueue()
          Default constructor which orders the elements in natural ordering.

PriorityQueue(Collection<? extends E> c)
          PriorityQueue will be created containing the elements in the specified collection.
 
PriorityQueue(int initialCapacity)
 PriorityQueue will be created with the initial size specified and orders its elements according to their natural ordering.

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
 PriorityQueue will be created with the initial size specified and orders its elements according to the specified comparator

PriorityQueue(PriorityQueue<? extends E> c)
          PriorityQueue will be created with containing the elements in the specified priority queue.

PriorityQueue(SortedSet<? extends E> c)
          PriorityQueue will be created with containing the elements in the specified sorted set.


Methods:

boolean add(E e) 
Inserts the Element into PriorityQueue.

void clear()
Removes all elements from PriorityQueue.

Comparator<? super E> comparator()
Return Comparator used to order the elements in queue, or returns null if its ordered the queue in natural ordering. 

boolean contains(Object o) 
Return true if particular Object present in the queue else false.

Iterator<E> iterator() 
Used to iterate over the elements in the queue.

boolean offer(E e) 
Its same as add() method inserts the Elements into PriorityQueue.

Element peek()
Retrieves the Element from the head of queue else return null if queue is empty.

Element poll()
Retrieves and removes the Element from the head of queue else return null if queue is empty.

boolean remove() 
Retrieves and removes head of this queue.

boolean remove(Object o) 
Removes given Object from the queue if its present in the queue.

int size()
Returns the queue size. 

Object[] toArray()
Returns Object array containing all of the elements in this queue.

 <T> T[] toArray(T[] a)
Returns an array containing all of the elements in this queue; the run-time type of the returned array is that of the specified array and returned array elements are in no particular order.



Now lets see simple program using PriorityQueue class

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueTest {

 public static void main(String[] args) {
  
  Queue<String> pq = new PriorityQueue<String>();
  
  pq.add("java");
  pq.add("servlet");
  pq.add("hibernate");
  
  pq.offer(".net");
  pq.offer("c");
  pq.offer("Pascal");
  
  System.out.println("\nPriorityQueue size() : "+pq.size());
  
  System.out.println("\nPriorityQueue peek() : "+pq.peek());
  
  System.out.println("\nIerating Queue Elements : ");
  Iterator<String> itr = pq.iterator();
  while (itr.hasNext()) {
   String string = (String) itr.next();
   System.out.print(string+", ");
  }
  
  System.out.println("\n\nPriorityQueue poll() : "+pq.poll());
  
  System.out.println("\nPriorityQueue size() : "+pq.size());
  
  System.out.println("\nPriorityQueue remove() : "+pq.remove());
  
  System.out.println("\nPriorityQueue remove(\".net\") : "+pq.remove(".net"));
  
  System.out.println("\nPriorityQueue contains() : "+pq.contains("java"));
  
  System.out.println("\nPriorityQueue toArray() : ");
  Object[] array = pq.toArray();
  for (Object object : array) {
   System.out.print(object.toString()+", ");
  }
 }
}

OUTPUT:

PriorityQueue size() : 6

PriorityQueue peek() : .net

Ierating Queue Elements : 
.net, c, Pascal, servlet, hibernate, java, 

PriorityQueue poll() : .net

PriorityQueue size() : 5

PriorityQueue remove() : Pascal

PriorityQueue remove(".net") : false

PriorityQueue contains() : true

PriorityQueue toArray() : 
c, hibernate, java, servlet, 

Reverse LinkedList

Reverse LinkedList

Reverse LinkedList  

This is one of the interview question which asked in recent interview like need to create a LinkedList and need to reverse those values in same linkedList without using addition list. We can make use of List implementation class LinkedList to achieve this. There are couple of ways we can achieve this in java by using Collection utility function reverse() and without reverse() function also. 
Lets see both the implementation in below examples. First lets see how to reverse LinkedList by using reverse() function. 

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class LinkedListReverse {

 public static void main(String[] args) {
  
  List<Integer> list = new LinkedList<Integer>();
  list.add(3);
  list.add(6);
  list.add(7);
  list.add(0);
  list.add(1);
  list.add(4);
  list.add(9);
  list.add(5);
  
  System.out.println("Before Reverse : "+list.toString());
  
  Collections.reverse(list);
  
  System.out.println("After Reverse : "+list.toString());  
 }
}

OUTPUT:

Before Reverse : [3, 6, 7, 0, 1, 4, 9, 5]
After Reverse : [5, 9, 4, 1, 0, 7, 6, 3]

Next we will see how to reverse linkedlist without using reverse() function.

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class LinkedListReverse {

 public static void main(String[] args) {
  
  List<Integer> list = new LinkedList<Integer>();
  list.add(3);
  list.add(6);
  list.add(7);
  list.add(0);
  list.add(1);
  list.add(4);
  list.add(9);
  list.add(5);
  
  System.out.println("Before Reverse : "+list.toString());
  
  ListIterator<Integer> itrFirst = list.listIterator();
  ListIterator<Integer> itrLast = list.listIterator();
  
  while (itrLast.hasNext()) {
   itrLast.next();   
  }
  
  for(int i = (list.size()/2)-1;itrFirst.hasNext() && itrLast.hasPrevious() && i>=0;i--){
   int first = itrFirst.next();
   int last = itrLast.previous();
   itrFirst.set(last);
   itrLast.set(first);
  }
  
  System.out.println("After Reverse : "+list.toString());  
 }
}

OUTPUT:

Before Reverse : [3, 6, 7, 0, 1, 4, 9, 5]
After Reverse : [5, 9, 4, 1, 0, 7, 6, 3]

TreeSet

TreeSet

TreeSet  

In our earlier tutorials we have seen about LinkedHashMap and LinkedHashSet with simple examples. Now lets see about TreeSet and its difference between HashSet and also how its works. First lets discuss about the main properties of TreeSet class.

• TreeSet always holds unique values as same as HashSet.
• TreeSet implements NavigableSet interface which extends the SortedSet interface. 
• Values stored in TreeSet will be in ascending order by default, hence its won't maintain insertion order as like LinkedHashSet. 
• If we need to order the values in descending order then we need to use Collections.reverseOrder() as like in below example. 

Now lets see simple example code which shows how it use TreeSet.

import java.util.Collections;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

public class TreeSetTest {

 public static void main(String[] args) {
  
  // By default value will be sorted in ascending order
  Set<String> tsAsc = new TreeSet<String>();

  // To sort values in descending order 
  Set<String> tsDesc = new TreeSet<String>(Collections.reverseOrder());
  
  tsAsc.add("Daniel");
  tsAsc.add("Chris");
  tsAsc.add("Amit");
  tsAsc.add("Bob");
  
  tsDesc.add("Daniel");
  tsDesc.add("Chris");
  tsDesc.add("Amit");
  tsDesc.add("Bob");
  
  // Printing TreeSet values in Ascending order .
  System.out.println("TreeSet values in Ascending order :::::::::::::::");
  Iterator<String> itr1 = tsAsc.iterator();
  while(itr1.hasNext()){
   System.out.println(itr1.next());
  }
  
  // Printing TreeSet values in Descending order .
  System.out.println("TreeSet values in Descending order :::::::::::::::");
  Iterator<String> itr2 = tsDesc.iterator();
  while(itr2.hasNext()){
   System.out.println(itr2.next());
  }
 }
}

OUTPUT:

TreeSet values in Ascending order :::::::::::::::
Amit
Bob
Chris
Daniel

TreeSet values in Descending order :::::::::::::::
Daniel
Chris
Bob
Amit

LinkedHashSet

LinkedHashSet

LinkedHashSet  

In our previous tutorial we have discussed about LinkedHashMap and how its works. In this tutorial we will see about LinkedHashSet and what is the difference between HashMap and how its works. Lets list out the properites of LinkedHashSet

• LinkedHashSet contains only unique values.
• LinkedHashSet implements Set interface and extends HashSet class. So it acquires all properites of HashSet class.
• The only difference between HashSet and LinkedHashSet is insertion order. HashSet won't maintain insertion order, were as LinkedHashSet always maintains the insertion order. 

Now lets see simple example which show how to use LinkedHashSet and difference between HashSet.

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetTest {
 
 public static void main(String[] args) {
  
  Set<String> hs = new HashSet<String>();
  Set<String> lhs = new LinkedHashSet<String>();
  
  hs.add("one");
  hs.add("two");
  hs.add("three");
  hs.add("three");
  hs.add("four");
  
  lhs.add("one");
  lhs.add("two");
  lhs.add("three");
  lhs.add("three");
  lhs.add("four");
  
  // Printing HashSet values.
  System.out.println("HashSet values :::::::::::::::");
  Iterator<String> itr = hs.iterator();
  while(itr.hasNext()){
   System.out.println(itr.next());
  }
  
  // Printing LinkedHashSet values.
  System.out.println("LinkedHashSet values :::::::::::::::");
  Iterator<String> itr1 = lhs.iterator();
  while(itr1.hasNext()){
   System.out.println(itr1.next());
  }
 }
}

OUTPUT:

HashSet values :::::::::::::::
two
one
three
four

LinkedHashSet values :::::::::::::::
one
two
three
four

In above program we have added 5 values in HashSet and LinkedHashSet with 1 duplicate value "three". Since Set won't allow duplicate value we can see only once "three" has printed. Next if we see the difference between HashSet and LinkedHashSet, insertion order has not followed in HashSet. But LinkedHashSet maintains the insertion order.