Thursday, August 31, 2017

HashSet vs. TreeSet vs. LinkedHashSet

HashSet vs. TreeSet vs. LinkedHashSet
HashSet is Implemented using a hash table. Elements are not ordered. The addremove, and contains methods have constant time complexity O(1).
TreeSet is implemented using a tree structure(red-black tree in algorithm book). The elements in a set are sorted, but the addremove, and contains methods has time complexity of O(log (n)). It offers several methods to deal with the ordered set like first(), last(), headSet(), tailSet(), etc.
LinkedHashSet is between HashSet and TreeSet. It is implemented as a hash table with a linked list running through it, so it provides the order of insertion. The time complexity of basic methods is O(1).
TreeSet Example
TreeSet<Integer> tree = new TreeSet<Integer>();
tree.add(12);
tree.add(63);
tree.add(34);
tree.add(45);
 
Iterator<Integer> iterator = tree.iterator();
System.out.print("Tree set data: ");
while (iterator.hasNext()) {
    System.out.print(iterator.next() + " ");
}
Output is sorted as follows:
Tree set data: 12 34 45 63 
Now let's define a Dog class as follows:
class Dog {
 int size;
 
 public Dog(int s) {
  size = s;
 }
 
 public String toString() {
  return size + "";
 }
}
Let's add some dogs to TreeSet like the following:
import java.util.Iterator;
import java.util.TreeSet;
 
public class TestTreeSet {
 public static void main(String[] args) {
  TreeSet<Dog> dset = new TreeSet<Dog>();
  dset.add(new Dog(2));
  dset.add(new Dog(1));
  dset.add(new Dog(3));
 
  Iterator<Dog> iterator = dset.iterator();
 
  while (iterator.hasNext()) {
   System.out.print(iterator.next() + " ");
  }
 }
}
Compile ok, but run-time error occurs:
Exception in thread "main" java.lang.ClassCastException: collection.Dog cannot be cast to java.lang.Comparable
 at java.util.TreeMap.put(Unknown Source)
 at java.util.TreeSet.add(Unknown Source)
 at collection.TestTreeSet.main(TestTreeSet.java:22)
Because TreeSet is sorted, the Dog object need to implement java.lang.Comparable's compareTo() method like the following:
class Dog implements Comparable<Dog>{
 int size;
 
 public Dog(int s) {
  size = s;
 }
 
 public String toString() {
  return size + "";
 }
 
 @Override
 public int compareTo(Dog o) {
         return size - o.size;
 }
}
References
https://www.programcreek.com/2013/03/hashset-vs-treeset-vs-linkedhashset/
The output is:
1 2 3 

ArrayList vs. LinkedList vs. Vector


COLLECTION HIERARCHY



Performance of ArrayList vs. LinkedList
The time complexity comparison is as follows:
arraylist-vs-linkedlist-complexity
arraylist-vs-linkedlist
The difference of their performance is obvious. LinkedList is faster in add and remove, but slower in get. Based on the complexity table and testing results, we can figure out when to use ArrayList or LinkedList. In brief, LinkedList should be preferred if:
  • there are no large number of random access of element
  • there are a large number of add/remove operations
References

https://www.programcreek.com/2013/03/arraylist-vs-linkedlist-vs-vector/

Arrays.asList() in java

Modifying a List returned by Arrays.asList(array)

asList() convert a fixed array into a fixed size list on which no modification can take place. If try to modify, it gives UnsupportedOperationException 

public class ListModified {
   public static void main(String[] args) {
      Integer[] values = { 1, 3, 7 };
      /*
       * Returns a fixed-size list backed by
         the specified array.
       */
      List<Integer> list = Arrays.asList(values);
      System.out.println("List size is " + list.size()
      + " List is " + list);

      /*
       * When trying to modify the list, It gives
       * UnsupportedOperationException
       */
      list.add(10);
      System.out.println(list);
   }
}

Summary

When we use Arrays.asList the size of the returned list is fixed because the list returned is not java.util.ArrayList, but a private static class defined inside java.util.Arrays. So if we add or remove elements from the returned list, an UnsupportedOperationException will be thrown.

Even if I try to remove an element from the list , it would give us UnsupportedOperationException 

Sunday, August 27, 2017

Compare Objects using Comparator

Compare Students based on there score. If score is equal , then sort those students based on there name.

import java.util.Arrays;
import java.util.Comparator;

class Student {
   String name;
   int score;
   public Student(String name, int score) {
      super();
      this.name = name;
      this.score = score;
   }
   public String getName() {
      return name;
   }
   public void setName(String name) {
      this.name = name;
   }
   public int getScore() {
      return score;
   }
   public void setScore(int score) {
      this.score = score;
   }
}

public class SortStudents implements Comparator<Student> {
   public static void main(String[] args) {
      Student[] students = new Student[5];
      students[0] = new Student("Paras", 100);
      students[1] = new Student("Varun", 200);
      students[2] = new Student("Rahul", 300);
      students[3] = new Student("Parul", 400);
      students[4] = new Student("Shubham", 100);
      Arrays.sort(students, new SortStudents());
      printArray(students);
   }
  
   static void printArray(Student[] students){
      for(Student s: students){
         System.out.println("Name: "+ s.getName()
         +" Score: "+ s.getScore());
      }
   }
  
   /*Sort students based on score and if score equals
    *then sort using names
    **/
   public int compare(Student s1, Student s2) {
      if(s1.getScore()==s2.getScore())
         return s2.getName().compareTo(s1.getName());
      else
         return s2.getScore()-s1.getScore();
   }
}

Output
Name: Parul   Score: 400
Name: Rahul   Score: 300
Name: Varun   Score: 200
Name: Shubham Score: 100
Name: Paras   Score: 100

Monday, August 21, 2017

Implementation of Own BlockingQueue using LinkedList

In previous article BlockingQueue , we've seen famous Producer-Consumer problem being solved by using by default BlockingQueue provided by JDK.

What if we need to implement our own BlockingQueue ?
Below code snippet is self-explanatory and gives clear picture what needs to be done for own BlockingQueue implementation.

package com.concurrent.jdk5;

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

/* Own Implementation of BlockingQueue using LinkedList */
public class OwnBlockingQueue {

    public List<Message> queue;
    public int limit;

    public OwnBlockingQueue(int limit) {
         this.limit = limit;
         queue = new LinkedList<>();
    }

    public synchronized void put(Message message) throws InterruptedException {
         while (this.queue.size() == this.limit) {
             System.out.println(Thread.currentThread().getName() +"Waiting");
             wait();
         }
         if (this.queue.size() == 0) {
             System.out.println(Thread.currentThread()
          .getName()+"Notified to all waiting threads");
             notifyAll();
         }
         this.queue.add(message);
    }

    public synchronized Message take() throws InterruptedException {
         while (this.queue.size() == 0) {
             System.out.println(Thread.currentThread()
             .getName() +"Waiting");
             wait();
         }
         if (this.queue.size() == this.limit) {
             System.out.println(Thread.currentThread()
          .getName() +"Notified to all waiting threads");
             notifyAll();
         }
         return this.queue.remove(0);
    }

    public static void main(String[] args) throws InterruptedException {
         OwnBlockingQueue blockingQueue = new OwnBlockingQueue(10);

         /* PRODUCER THREAD */
         Thread producer = new Thread(new Runnable() {
             @Override
             public void run() {
                 for (int i = 0; i < 100; i++) {
                      Message message = new Message("" + i);
                      try {
                          blockingQueue.put(message);
                          Thread.sleep(10);
                         sysout("Produced message"+mes);
                      } catch (InterruptedException e) {
                          e.printStackTrace();
                      }
                 }
                 /* Putting last Message */
                 Message message = new Message("EXIT");
                 try {
                      blockingQueue.put(message);
                 } catch (InterruptedException e) {
                      e.printStackTrace();
                 }
                 System.out.println("Produced LAST Message "+message.getMessage());
             }
         });

         /* CONSUMER THREAD */
         Thread consumer = new Thread(new Runnable() {
             public void run() {
                 Message message;
                 try {
                      while (!((message = blockingQueue.take()).getMessage().equals("EXIT"))){
                          Thread.sleep(10);
                          System.out.println("Message Consumed " + message.getMessage());
                      }
                 } catch (InterruptedException e) {
                      e.printStackTrace();
                 }
                 System.out.println("All Messages Produced , Consumed and Finished");
             }
         });
        
         producer.setName("producer");
         consumer.setName("consumer");
         producer.start();
         consumer.start();
         producer.join();
         consumer.join();
    }
}

Output

consumerWaiting
producerNotified to all waiting threads
Message Consumed 0
Produced Message 0
consumerWaiting
producerNotified to all waiting threads
Message Consumed 1
consumerWaiting
Produced Message 1
producerNotified to all waiting threads
Message Consumed 2
---
---
---
consumerWaiting
Produced Message 97
producerNotified to all waiting threads
Message Consumed 97
Produced Message 98
producerNotified to all waiting threads
Message Consumed 98
Produced Message 99
producerNotified to all waiting threads
Produced LAST Message EXIT
Message Consumed 99
All Messages Produced , Consumed and Finished