HashSet vs. TreeSet vs. LinkedHashSet

HashSet vs. TreeSet vs. LinkedHashSet

HashSet is Implemented using a hash table. Elements are not ordered. The add, remove, 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 add, remove, 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:

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 

Collections Time Complexity

Big-O Complexity Chart

Horrible

Bad

Fair

Good

Excellent

Java Collections – Performance (Time Complexity)

How to make ArrayList Immutable

By default ArrayList is modifiable, JDK gives a very good method to make it immutable.

/*Class to make ArrayList Immutable*/

public class ImmutableArrayList {

     public static void main(String[] args) {

          List<String> list = new ArrayList<>(Arrays.asList("Paras","Sonal","Richa","Usha"));

          List<String> unModificableList=Collections.unmodifiableList(list);

          unModificableList.add("Abc");

     }   

}

Output

Exception in thread "main" java.lang.UnsupportedOperationException

     at java.util.Collections$UnmodifiableCollection.add(Unknown Source)

     at com.ArrayList.ImmutableArrayList.main(ImmutableArrayList.java:14)

Sort HashMap by Values

When it comes to sorting a hash map by keys, it can be easily implemented using TreeMap as TreeMap by default sorts a map using key.

But when it comes to sort a map by values, we’ve to make use of Comparator which sorts map values by itself.

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.HashMap;

import java.util.LinkedHashMap;

import java.util.List;

import java.util.Map.Entry;

import java.util.Set;

public class HashMapSort {

     public static void main(String[] args) {

           HashMap<String,String> hashMap = new HashMap<>();

          

           /*Entering values in an Array*/

           hashMap.put("Paras","Chawla");

           hashMap.put("Sonal","Gupta");

           hashMap.put("Richa", "Pruthi");

           hashMap.put("Usha","Pahwa");

          

           System.out.println("Unsorted HashMap "+ hashMap);

          

           /*Putting Entry<String,String> into set*/

           Set<Entry<String,String>> set= hashMap.entrySet();

           System.out.println("Unsorted Set "+set);

           /*Creating list using Set*/

           List<Entry<String,String>> list = new ArrayList<>(set);

           System.out.println("Unsorted List "+list);

          

           /*Creating Comparator*/

           Comparator<Entry<String,String>> comparator = new Comparator<Entry<String,String>>() {

                @Override

                public int compare(Entry<String, String> o1, Entry<String, String> o2) {

                     return o1.getValue().compareTo(o2.getValue());

                }

           };

          

           /*Passing list and comparator to Collections.sort()*/

           Collections.sort(list, comparator);

          

           /*Got sorted list from sort()*/

           System.out.println("Sorted List"+list);

          

           /*Since HashMap doesn't maintain order,

            * Adding Entry key and Entry value from List in LHM */

           LinkedHashMap<String,String> linkedHashMap = new LinkedHashMap<>();

          

           /*Adding from List into LinkedHashMap*/

           for(Entry<String,String> entry : list)

                linkedHashMap.put(entry.getKey(),entry.getValue());

               

           /*For printing we need to add LinkedHashMap to Set again */

           Set<Entry<String,String>> sortedSet = linkedHashMap.entrySet();

          

           System.out.println("Sorted Map");

           for(Entry<String,String> entry : sortedSet)

           System.out.println("Key->"+ entry.getKey()+"| Value-->"+ entry.getValue());

     }

}

Output

Unsorted HashMap {Richa=Pruthi, Paras=Chawla, Sonal=Gupta, Usha=Pahwa}

Unsorted Set [Richa=Pruthi, Paras=Chawla, Sonal=Gupta, Usha=Pahwa]

Unsorted List [Richa=Pruthi, Paras=Chawla, Sonal=Gupta, Usha=Pahwa]

Sorted List[Paras=Chawla, Sonal=Gupta, Usha=Pahwa, Richa=Pruthi]

Sorted Map

Key->Paras| Value-->Chawla

Key->Sonal| Value-->Gupta

Key->Usha| Value-->Pahwa

Key->Richa| Value-->Pruthi