ArrayListLinkedList
1) ArrayList internally uses a dynamic array to store the elements.LinkedList internally uses a doubly linked list to store the elements.
2) Manipulation with ArrayList is slow because it internally uses an array. If any element is removed from the array, all the bits are shifted in memory.Manipulation with LinkedList is faster than ArrayList because it uses a doubly linked list, so no bit shifting is required in memory.
3) An ArrayList class can act as a list only because it implements List only.LinkedList class can act as a list and queue both because it implements List and Deque interfaces.
4) ArrayList is better for storing and accessing data.LinkedList is better for manipulating data.

Deque interface in Java with Example

The java.util.Deque interface is a subtype of the java.util.Queue interface. The Deque is related to the double-ended queue that supports addition or removal of elements from either end of the data structure, it can be used as a queue (first-in-first-out/FIFO) or as a stack (last-in-first-out/LIFO). These are faster than Stack and LinkedList.
This is the hierarchy of Deque interface in Java:

Few important features of Deque are:

  • It provides the support of resizable array and helps in restriction-free capacity, so to grow the array according to the usage.
  • Array deques prohibit the use of Null elements and do not accept any such elements.
  • Any concurrent access by multiple threads is not supported.
  • In the absence of external synchronization, Deque is not thread-safe.

Java LinkedList class

Java LinkedList class uses a doubly linked list to store the elements. It provides a linked-list data structure. It inherits the AbstractList class and implements List and Deque interfaces.The important points about Java LinkedList are:

  • Java LinkedList class can contain duplicate elements.
  • Java LinkedList class maintains insertion order.
  • Java LinkedList class is non synchronized.
  • In Java LinkedList class, manipulation is fast because no shifting needs to occur.
  • Java LinkedList class can be used as a list, stack or queue.

LinkedList class declaration

Let’s see the declaration for java.util.LinkedList class.

  1. public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable  

Java ArrayList class

Java ArrayList class uses a dynamic array for storing the elements. It inherits AbstractList class and implements List interface.The important points about Java ArrayList class are:

  • Java ArrayList class can contain duplicate elements.
  • Java ArrayList class maintains insertion order.
  • Java ArrayList class is non synchronized.
  • Java ArrayList allows random access because array works at the index basis.
  • In Java ArrayList class, manipulation is slow because a lot of shifting needs to occur if any element is removed from the array list.

Hierarchy of ArrayList class

As shown in the above diagram, Java ArrayList class extends AbstractList class which implements List interface. The List interface extends Collection and Iterable interfaces in hierarchical order.

ArrayList class declaration

Let’s see the declaration for java.util.ArrayList class.

  1. public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable  

Java HashSet

Java HashSet class is used to create a collection that uses a hash table for storage. It inherits the AbstractSet class and implements Set interface.The important points about Java HashSet class are:

  • HashSet stores the elements by using a mechanism called hashing.
  • HashSet contains unique elements only.
  • HashSet allows null value.
  • HashSet class is non synchronized.
  • HashSet doesn’t maintain the insertion order. Here, elements are inserted on the basis of their hashcode.
  • HashSet is the best approach for search operations.
  • The initial default capacity of HashSet is 16, and the load factor is 0.75.

Internal working of a HashSetThe underlying data structure for HashSet is hashtable.All the classes of Set interface internally backed up by Map. HashSet uses HashMap for storing its object internally. You must be wondering that to enter a value in HashMap we need a key-value pair, but in HashSet we are passing only one value.Storage in HashMapActually the value we insert in HashSet acts as key to the map Object and for its value java uses a constant variable. So in key-value pair all the keys will have same value.Implementation of HashSet in java doc:private transient HashMap map;
// Constructor – 1// All the constructors are internally creating HashMap Object.public HashSet(){    // Creating internally backing HashMap object    map = new HashMap();}
// Constructor – 2public HashSet(int initialCapacity){    // Creating internally backing HashMap object    map = new HashMap(initialCapacity);}
// Dummy value to associate with an Object in Mapprivate static final Object PRESENT = new Object();
If we look at add() method of HashSet class:public boolean add(E e){   return map.put(e, PRESENT) == null;}
We can notice that, add() method of HashSet class internally calls put() method of backing HashMap object by passing the element you have specified as a key and constant “PRESENT” as its value.remove() method also works in the same manner. It internally calls remove method of Map interface.public boolean remove(Object o){  return map.remove(o) == PRESENT;}
Time Complexity of HashSet Operations: The underlying data structure for HashSet is hashtable. So amortize (average or usual case) time complexity for add, remove and look-up (contains method) operation of HashSet takes O(1) time.

Difference between List and Set

A list can contain duplicate elements whereas Set contains unique elements only.

Hierarchy of HashSet class

The HashSet class extends AbstractSet class which implements Set interface. The Set interface inherits Collection and Iterable interfaces in hierarchical order.

HashSet class declaration

Let’s see the declaration for java.util.HashSet class.

  1. public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable   

Java LinkedHashSet class

Java LinkedHashSet class is a Hashtable and Linked list implementation of the set interface. It inherits HashSet class and implements Set interface.The important points about Java LinkedHashSet class are:

  • Java LinkedHashSet class contains unique elements only like HashSet.
  • Java LinkedHashSet class provides all optional set operation and permits null elements.
  • Java LinkedHashSet class is non synchronized.
  • Java LinkedHashSet class maintains insertion order.

Hierarchy of LinkedHashSet class

The LinkedHashSet class extends HashSet class which implements Set interface. The Set interface inherits Collection and Iterable interfaces in hierarchical order.

How LinkedHashSet Maintains Insertion Order?

LinkedHashSet uses LinkedHashMap object to store it’s elements. The elements you insert in the LinkedHashSet are stored as keys of this LinkedHashMap object. Each key, value pair in the LinkedHashMap are instances of it’s static inner class called Entry<K, V>. This Entry<K, V> class extends HashMap.Entry class. The insertion order of elements into LinkedHashMap are maintained by adding two new fields to this class. They are beforeand after. These two fields hold the references to previous and next elements. These two fields make LinkedHashMap to function as a doubly linked list.

123456789private static class Entry<K,V> extends HashMap.Entry<K,V> {        // These fields comprise the doubly linked list used for iteration.        Entry<K,V> before, after;         Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {             super(hash, key, value, next);        }}

The first two fields of above inner class of LinkedHashMap – before and after are responsible for maintaining the insertion order of the LinkedHashSet. The header field of LinkedHashMap stores the head of this doubly linked list. It is declared like below,

1private transient Entry<K,V> header;        //Stores the head of the doubly linked list

In LinkedHashMap, the same set of Entry objects (rather references to Entry objects) are arranged in two different manner. One is the HashMap and another one is Doubly linked list. The Entry objects just sit on heap memory, unaware of that they are part of two different data structures.Let’s see one example of LinkedHashSet to know how it works internally.

12345678910111213141516171819public class LinkedHashSetExample {    public static void main(String[] args)     {        //Creating LinkedHashSet         LinkedHashSet<String> set = new LinkedHashSet<String>();          //Adding elements to LinkedHashSet         set.add(“BLUE”);         set.add(“RED”);         set.add(“GREEN”);            set.add(“BLACK”);    }}

Look at the below image to see how above program works.

next →← prevJava TreeSet classJava TreeSet class implements the Set interface that uses a tree for storage. It inherits AbstractSet class and implements the NavigableSet interface. The objects of the TreeSet class are stored in ascending order.The important points about Java TreeSet class are:Java TreeSet class contains unique elements only like HashSet.Java TreeSet class access and retrieval times are quiet fast.Java TreeSet class doesn’t allow null element.Java TreeSet class is non synchronized.Java TreeSet class maintains ascending order.Hierarchy of TreeSet classAs shown in the above diagram, Java TreeSet class implements the NavigableSet interface. The NavigableSet interface extends SortedSet, Set, Collection and Iterable interfaces in hierarchical order.

Java HashMap class

Java HashMap class implements the map interface by using a hash table. It inherits AbstractMap class and implements Map interface.

Points to remember

  • Java HashMap class contains values based on the key.
  • Java HashMap class contains only unique keys.
  • Java HashMap class may have one null key and multiple null values.
  • Java HashMap class is non synchronized.
  • Java HashMap class maintains no order.
  • The initial default capacity of Java HashMap class is 16 with a load factor of 0.75.

Hierarchy of HashMap class

As shown in the above figure, HashMap class extends AbstractMap class and implements Map interface.

HashMap class declaration

Let’s see the declaration for java.util.HashMap class.

  1. public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable  

HashMap class Parameters

Let’s see the Parameters for java.util.HashMap class.

  • K: It is the type of keys maintained by this map.
  • V: It is the type of mapped values.
HashSet hs= new HashSet(); hs.add(“c”);hs.add(null);System.out.println(hs);hs.add(“a”);hs.add(null);System.out.println(hs);hs.add(“b”);System.out.println(hs);HashMap hm= new HashMap(); hm.put(null, “j”); System.out.println(“hm :”+hm);hm.put(“A”, “A”); System.out.println(“hm :”+hm);hm.put(null, “k”); System.out.println(“hm :”+hm);TreeSet s= new TreeSet(); s.add(“treee”);System.out.println(“s :”+s);s.add(null);System.out.println(“s :”+s);

OUTPUT
[null, c] [null, a, c] [null, a, b, c] hm :{null=j} hm :{null=j, A=A} hm :{null=k, A=A} s :[treee] Exception in thread “main” java.lang.NullPointerException

Working of HashMap in Java


What is Hashing

It is the process of converting an object into an integer value. The integer value helps in indexing and faster searches.

What is HashMap

HashMap is a part of the Java collection framework. It uses a technique called Hashing. It implements the map interface. It stores the data in the pair of Key and Value. HashMap contains an array of the nodes, and the node is represented as a class. It uses an array and LinkedList data structure internally for storing Key and Value. There are four fields in HashMap.

Before understanding the internal working of HashMap, you must be aware of hashCode() and equals() method.

  • equals(): It checks the equality of two objects. It compares the Key, whether they are equal or not. It is a method of the Object class. It can be overridden. If you override the equals() method, then it is mandatory to override the hashCode() method.
  • hashCode(): This is the method of the object class. It returns the memory reference of the object in integer form. The value received from the method is used as the bucket number. The bucket number is the address of the element inside the map. Hash code of null Key is 0.
  • Buckets: Array of the node is called buckets. Each node has a data structure like a LinkedList. More than one node can share the same bucket. It may be different in capacity.

Insert Key, Value pair in HashMap

We use put() method to insert the Key and Value pair in the HashMap. The default size of HashMap is 16 (0 to 15).

Example

In the following example, we want to insert three (Key, Value) pair in the HashMap.

  1. HashMap<String, Integer> map = new HashMap<>();  
  2. map.put(“Aman”, 19);  
  3. map.put(“Sunny”, 29);  
  4. map.put(“Ritesh”, 39);  

Let’s see at which index the Key, value pair will be saved into HashMap. When we call the put() method, then it calculates the hash code of the Key “Aman.” Suppose the hash code of “Aman” is 2657860. To store the Key in memory, we have to calculate the index.

Calculating Index

Index minimizes the size of the array. The Formula for calculating the index is:

  1. Index = hashcode(Key) & (n-1)  

Where n is the size of the array. Hence the index value for “Aman” is:

  1. Index = 2657860 & (16-1) = 4  

The value 4 is the computed index value where the Key and value will store in HashMap.

Hash Collision

This is the case when the calculated index value is the same for two or more Keys. Let’s calculate the hash code for another Key “Sunny.” Suppose the hash code for “Sunny” is 63281940. To store the Key in the memory, we have to calculate index by using the index formula.

  1. Index=63281940 & (16-1) = 4  

The value 4 is the computed index value where the Key will be stored in HashMap. In this case, equals() method check that both Keys are equal or not. If Keys are same, replace the value with the current value. Otherwise, connect this node object to the existing node object through the LinkedList. Hence both Keys will be stored at index 4.

Similarly, we will store the Key “Ritesh.” Suppose hash code for the Key is 2349873. The index value will be 1. Hence this Key will be stored at index 1.

get() method in HashMap

get() method is used to get the value by its Key. It will not fetch the value if you don’t know the Key. When get(K Key) method is called, it calculates the hash code of the Key.Suppose we have to fetch the Key “Aman.” The following method will be called.

  1. map.get(new Key(“Aman”));  

It generates the hash code as 2657860. Now calculate the index value of 2657860 by using index formula. The index value will be 4, as we have calculated above. get() method search for the index value 4. It compares the first element Key with the given Key. If both keys are equal, then it returns the value else check for the next element in the node if it exists. In our scenario, it is found as the first element of the node and return the value 19.Let’s fetch another Key “Sunny.”The hash code of the Key “Sunny” is 63281940. The calculated index value of 63281940 is 4, as we have calculated for put() method. Go to index 4 of the array and compare the first element’s Key with the given Key. It also compares Keys. In our scenario, the given Key is the second element, and the next of the node is null. It compares the second element Key with the specified Key and returns the value 29. It returns null if the next of the node is null.

next →← prevJava LinkedHashMap classJava LinkedHashMap class is Hashtable and Linked list implementation of the Map interface, with predictable iteration order. It inherits HashMap class and implements the Map interface.Points to rememberJava LinkedHashMap contains values based on the key.Java LinkedHashMap contains unique elements.Java LinkedHashMap may have one null key and multiple null values.Java LinkedHashMap is non synchronized.Java LinkedHashMap maintains insertion order.The initial default capacity of Java HashMap class is 16 with a load factor of 0.75.LinkedHashMap class declarationLet’s see the declaration for java.util.LinkedHashMap class.public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>  LinkedHashMap class ParametersLet’s see the Parameters for java.util.LinkedHashMap class.K: It is the type of keys maintained by this map.V: It is the type of mapped values.
next →← prevJava TreeMap classJava TreeMap class is a red-black tree based implementation. It provides an efficient means of storing key-value pairs in sorted order.The important points about Java TreeMap class are:Java TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.Java TreeMap contains only unique elements.Java TreeMap cannot have a null key but can have multiple null values.Java TreeMap is non synchronized.Java TreeMap maintains ascending order.TreeMap class declarationLet’s see the declaration for java.util.TreeMap class.public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable  TreeMap class ParametersLet’s see the Parameters for java.util.TreeMap class.K: It is the type of keys maintained by this map.V: It is the type of mapped values.
2. HashSet vs. TreeSet vs. LinkedHashSet HashSet is Implemented using a hash table. Elements are not ordered. The add, remove, and contains methods has 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).   

3. TreeSet ExampleTreeSet tree = new TreeSet();tree.add(12);tree.add(63);tree.add(34);tree.add(45);       Iterator 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 dset = new TreeSet();dset.add(new Dog(2));dset.add(new Dog(1));dset.add(new Dog(3));
Iterator 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.Comparableat 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{int size;
public Dog(int s) {size = s;}
public String toString() {return size + “”;}
@Overridepublic int compareTo(Dog o) {        return size – o.size;}}
The output is: 
1 2 3 

4. HashSet ExampleHashSet dset = new HashSet();dset.add(new Dog(2));dset.add(new Dog(1));dset.add(new Dog(3));dset.add(new Dog(5));dset.add(new Dog(4));Iterator iterator = dset.iterator();while (iterator.hasNext()) {System.out.print(iterator.next() + ” “);}
Output:5 3 2 1 4 

 Note the order is not certain. 5. LinkedHashSet Example

LinkedHashSet dset = new LinkedHashSet();dset.add(new Dog(2));dset.add(new Dog(1));dset.add(new Dog(3));dset.add(new Dog(5));dset.add(new Dog(4));Iterator iterator = dset.iterator();while (iterator.hasNext()) {System.out.print(iterator.next() + ” “);}
The order of the output is certain and it is the insertion order. 
2 1 3 5 4 

6. Performance testingThe following method tests the performance of the three class on add() method. public static void main(String[] args) {Random r = new Random();
HashSet hashSet = new HashSet();TreeSet treeSet = new TreeSet();LinkedHashSet linkedSet = new LinkedHashSet();
// start timelong startTime = System.nanoTime();for (int i = 0; i < 1000; i++) {int x = r.nextInt(1000 – 10) + 10;hashSet.add(new Dog(x));}// end timelong endTime = System.nanoTime();long duration = endTime – startTime;System.out.println(“HashSet: ” + duration);
// start timestartTime = System.nanoTime();for (int i = 0; i < 1000; i++) {int x = r.nextInt(1000 – 10) + 10;treeSet.add(new Dog(x));}// end timeendTime = System.nanoTime();duration = endTime – startTime;System.out.println(“TreeSet: ” + duration);
// start timestartTime = System.nanoTime();for (int i = 0; i < 1000; i++) {int x = r.nextInt(1000 – 10) + 10;linkedSet.add(new Dog(x));}// end timeendTime = System.nanoTime();duration = endTime – startTime;System.out.println(“LinkedHashSet: ” + duration);
}

From the output below, we can clearly wee that HashSet is the fastest one. 
HashSet: 2244768TreeSet: 3549314LinkedHashSet: 2263320


Fail Fast Vs Fail Safe Iterator In Java :
Java Developer Interview QuestionsDifference between Fail fast and fail safe iterator  or  Fail fast vs Fail Safe iterator is one of those questions which are  used to test your knowledge about the topic Concurrency.Before we discuss in detail about fail safe iterator and fail fast iterator in addition to  their comparison , we should understand the term Concurrent Modification .
What is Concurrent Modification ?
When one or more thread is iterating over the collection, in between, one thread changes the structure of the collection (either adding the element to the collection or by deleting the element in the collection or by updating the value at particular position in the collection) is known as Concurrent Modification
Difference between Fail Fast iterator and Fail Safe iterator
Fail fast Iterator
Fail fast iterator while iterating through the collection , instantly throws Concurrent Modification Exception if there is structural modification  of the collection . Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
Fail-fast iterator can throw ConcurrentModificationException in two scenarios :


Single Threaded Environment After the creation of the iterator , structure is modified at any time by any method other than iterator’s own remove method.  Multiple Threaded Environment
 If one thread is modifying the structure of the collection while other thread is iterating over it .

According to  Oracle docs , the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

Interviewer :
How  Fail  Fast Iterator  come to know that the internal structure is modified ?
Iterator read internal data structure (object array) directly .
The internal data structure(i.e object array) should not be modified while iterating through the collection. To ensure this it maintains an internal  flag “mods” .Iterator checks the “mods” flag whenever it gets the next value (using hasNext() method and next() method). Value of mods flag changes whenever there is an structural modification. Thus indicating iterator to throw ConcurrentModificationException.

Fail Safe Iterator :
Fail Safe Iterator makes copy of the internal data structure (object array) and iterates over the copied data structure.Any structural modification done to the iterator affects the copied data structure.  So , original data structure remains  structurally unchanged .Hence , no ConcurrentModificationException throws by the fail safe iterator.
Two  issues associated with Fail Safe Iterator are :
1. Overhead of maintaining the copied data structure i.e memory.
2.  Fail safe iterator does not guarantee that the data being read is the data currently in the original data structure.
According to Oracle docs , fail safe iterator is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don’t want to synchronize traversals, yet need to preclude interference among concurrent threads. The “snapshot” style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException.The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove(), set(), and add()) are not supported. These methods throw UnsupportedOperationException.


Example of Fail Fast Iterator and Fail Safe Iterator

import java.util.HashMap;
import java.util.Iterator; import java.util.Map;
public class FailFastExample {         
public static void main(String[] args)     {        
Map<String,String> premiumPhone = new HashMap<String,String>();         premiumPhone.put(“Apple”, “iPhone”);         premiumPhone.put(“HTC”, “HTC one”);        
premiumPhone.put(“Samsung”,”S5″);              
Iterator iterator = premiumPhone.keySet().iterator();               
while (iterator.hasNext())         {            
System.out.println(premiumPhone.get(iterator.next()));           
premiumPhone.put(“Sony”, “Xperia Z”);         }            }    }

Output :

iPhoneException in thread “main” java.util.ConcurrentModificationException         at java.util.HashMap$HashIterator.nextEntry(Unknown Source)        at java.util.HashMap$KeyIterator.next(Unknown Source)        at FailFastExample.main(FailFastExample.java:20)


Fail Safe Iterator Example :

import java.util.concurrent.ConcurrentHashMap; import java.util.Iterator;

public class FailSafeExample {     
     public static void main(String[] args)     {   
      ConcurrentHashMap<String,String> premiumPhone =                                new ConcurrentHashMap<String,String>();         premiumPhone.put(“Apple”, “iPhone”);     
    premiumPhone.put(“HTC”, “HTC one”);        
premiumPhone.put(“Samsung”,”S5″);           
    Iterator iterator = premiumPhone.keySet().iterator();       
         while (iterator.hasNext())         {           
  System.out.println(premiumPhone.get(iterator.next()));      
      premiumPhone.put(“Sony”, “Xperia Z”);         }            }    }

Output :

S5HTC oneiPhone


Recap : Difference between Fail Fast Iterator and Fail Safe Iterator
Fail Fast IteratorFail Safe Iterator Throw ConcurrentModification ExceptionYesNo Clone objectNoYes Memory OverheadNoYes ExamplesHashMap,Vector,ArrayList,HashSet
CopyOnWriteArrayList,ConcurrentHashMap

Please mention in comments in case you have any queries regarding Fail Fast and Fail Safe Iterators .

How TreeSet Works Internally In Java : TreeSet Interview QuestionsWe have already discussed difference between TreeSet and HashSet in java . The problem with java developers is that they know what TreeSet/TreeMap do but not  how. TreeSet is not frequently used collections framework class . So it is rare to get asked questions about this class  in the interview. Although , you should at least know when to prefer  TreeSet class  over other collection classes.

Read Also :  Difference between Iterator and ListIterator in Java with Example

What is TreeSet ?
TreeSet is like HashSet which contains the unique elements only but in a sorted manner. The major difference is that TreeSet provides a total ordering of the elements. The elements are ordered using their natural ordering, or by a Comparator typically provided at sorted set creation time. The set’s iterator will traverse the set in ascending element order.
How TreeSet works in Java ?
If you look into the TreeSet Api in rt.jar , you will find the following code :


     public class TreeSet<E>               extends AbstractSet<E>               implements NavigableSet<E>, Cloneable, java.io.Serializable
{    private transient NavigableMap<E,Object> map;        // Dummy value to associate with an Object in the backing Map        private static final Object PRESENT = new Object();              public TreeSet() {
        this(new TreeMap<E,Object>());
    }        // SOME CODE ,i.e Other methods in TreeSet           public boolean add(E e) {
        return map.put(e, PRESENT)==null;     }  
    // SOME CODE ,i.e Other methods in TreeSet
}
According to TreeSet Oracle doc :
TreeSet is a NavigableSet implementation backed by TreeMap instance. 

Hence , whenever you are adding element to the TreeSet object , it works just like HashSet , The only difference is that instead of HashMap here we have TreeMap object in the constructor.
As we know in TreeMap each key is unique as it internally uses HashMap . So what we do in the TreeSet is that we pass the argument in the add(Elemene E) that is E as a key in the TreeSet . Now we need to associate some value to the key , so what Java apis developer did is to pass the Dummy  value that is ( new Object () ) which is referred by Object reference PRESENT .
So , actually when you are adding a line in TreeSet like  treeset.add(3)   what java does internally is that it will put that element E here 3 as a key in the TreeMap(created during TreeSet object creation) and some dummy value that is Object’s object is passed as a value to the key .
Now if you see the code of the TreeMap put(Key k,Value V) method , you will find something like this
 public V put(K key, V value) {//Some code}
The main point to notice in above code is that put (key,value) will return
1.  null , if key is unique and added to the map2.  Old Value of the key , if key is duplicate
So , in TreeSet add() method ,  we check the return value of map.put(key,value) method with null valuei.e.
   public boolean add(E e) {            return map.put(e, PRESENT)==null;       }
So , if map.put(key,value) returns null ,thenmap.put(e, PRESENT)==null      will return true and element is added to the TreeSet.


So , if map.put(key,value) returns old value of the key ,thenmap.put(e, PRESENT)==null      will return false and element is  not added to the TreeSet .
How to find the index of  any element in the TreeSet ?
There are many ways to find out the index of element in the TreeSet. Below is the one liner :
set.headSet(element).size()

Note  :  headSet(element) method returns the sub TreeSet(portion of TreeSet) whose values  are less than input element. Then we are calling size() method on the sub TreeSet , which returns the index of the element as sub TreeSet is already sorted.

Why and when we use TreeSet ?
We prefer TreeSet in order  to maintain the unique elements  in the sorted order .
What is the runtime performance of the add() method of the TreeSet and HashSet , where n represents the number of elements?
According to TreeSet Oracle doc :
TreeSet implementation provides guaranteed log(n) time cost for the basic operations (add, removeand contains ) method.
According to HashSet Oracle doc :
HashSet provides constant time performance O(1) for basic operations  (add, remove and contains) method assuming the hash  function disperses the elements properly among the buckets.
One-liner :                TreeSet : O(log(n))  HashSet : O(1)
What is natural ordering in TreeSet ?
“Natural” ordering is the ordering implied by the implementation of Comparable interface by the objects in the TreeSet . Essentially RBTree must be able to tell which object is smaller than other object , and there are two  ways to supply that logic to the RB Tree implementation :
1. We need to implement the Comparable interface in the class(es) used as objects in TreeSet.2. Supply an implementation of the Comparator would do comparing outside the class itself.

Why do we need TreeSet when we already had SortedSet ?
sortedSet is an interface while TreeSet is the class implementing it. As we know, in java, we can not create the objects of the interface. The class implementing the interface must fulfill the contract of interface, i.e , concrete class must implement all the methods present in the interface. TreeSet is such an implementation.
Which data structure you will prefer  in your code : HashSet and TreeSet ?
TreeSet contains the elements in the sorted order while HashSet is faster. Thus , deciding which one to choose depends upon the conditions :
If you want to maintain the order of the elements then TreeSet should be used because the result is alphabetically sorted.
If you do not want to sort the elements and  avoid duplicate elements . Your task involves mainly insert and retrieve operations then prefer HashSet.While iterating HashSet there is no ordering of elements while TreeSet iterates in the natural order.

What happens if the TreeSet is concurrently modified while iterating the elements ?
The iterator’s returned by the TreeSet class iterator method are fail-fast.  fail-fast means if the set is modified at any time after the iterator is created , in any way except the iterator’s own remove method  , the iterator will throw a ConcurrentModificationException. Thus , in the face of concurrent modification , the iterator fails quickly and cleanly . You can find it here  difference between fail-fast and fail-safe iterator in java with example.
Which copy technique (deep or shallow ) is used by TreeSet clone() method ?
According to Oracle docs , clone() method returns the shallow copy of the TreeSet instance.  In shallow copy , Both objects A and B shared the same memory location .

How to convert HashSet to TreeSet object ?
One-liner :   Set    treeObject = new TreeSet( hashSetObject);

What is the difference between HashSet and TreeSet in Java ?
I have already shared the difference between HashSet and TreeSet in Java with Example
Write an example of TreeSet ?


import java.util.TreeSet;

public class TreeSetExample {        public static void main(String[] args) {         TreeSet<String> treesetobj = new TreeSet<String>();         treesetobj.add(“Alive is awesome”);         treesetobj.add(“Love yourself”);         System.out.println(“TreeSet object output :”+ treesetobj); }}



Output : 
TreeSet object output :[Alive is awesome, Love yourself]
Please mention in the comments in case you have any other questions regarding TreeSet class in java.



50% LikesVS
50% Dislikes

Leave a Reply

Your email address will not be published. Required fields are marked *