Saturday, January 11, 2020

HashSet and TreeSet

Set

Set is a collection of unique items. A Set can not carry duplicate items. Different classes under the collection interface provide different types of Sets. Like HashSet, TreeSet, LinkedHashSet, etc. Set is an Interface which is implemented by all the classes in the class hierarchy of Sets in Collection framework.

HashSet and TreeSet

In the Set class hierarchy in Java's Collections framework,  HashSet and TreeSet are two important classes. HashSet offers much faster performance than TreeSets. HashSet provides constant-time access, while the TreeSets have logarithmic time access for most of the operations like add, remove and contain, etc. HashSet does not offer a guarantee of order, but TreeSets offers the guarantee of ordering. However, duplicated elements are not allowed in any of the sets.

HashSet and TreeSet
Sets


HashSet

HashSets exhibits constant-time performance for the basic operations (add, remove, contains and size).HashSet does not guarantee that the order of elements will remain constant over time. The iteration performance depends on the initial capacity and the load factor of the HashSet. Iterating over this set requires time proportional to the sum of the HashSet instance's size (the number of elements) plus the "capacity" of the backing HashMap instance (the number of buckets). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

Example

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
class Contact{
      int id;
      String fname;
      String lname;
      long mob;
      public Contact(int id, String fname, String lname, long mob) {
            super();
            this.id = id;
            this.fname = fname;
            this.lname = lname;
            this.mob = mob;
      }
     
}

public class SetsDemo {//Sets in Java

      public static void main(String[] args)
      {//HashSet
           
            Set<Contact> contacts=new HashSet<>();
            contacts.add(new Contact(70, "Rohan", "Khanna", 97451287));
            contacts.add(new Contact(12, "Amit", "Sharma", 919782145));
            contacts.add(new Contact(121, "Vinod", "Kumar", 919782145));
            contacts.add(new Contact(74, "Anil", "Gupta", 919782145));
            contacts.add(new Contact(98, "Sourav", "Puri", 919782145));
            contacts.add(new Contact(100, "Vinay", "Verma", 919782145));
            //few contacts are added
            Iterator<Contact> i=contacts.iterator();
            while(i.hasNext())
            {
                  Contact contact=i.next();
                  System.out.println(contact.id+"\t"+contact.fname+"\t"+contact.lname+"\t"+contact.mob);
            }
      }
}
 Output:
121 Vinod Kumar 919782145
100 Vinay Verma 919782145
98 Sourav Puri 919782145
70 Rohan Khanna 97451287
12 Amit Sharma 919782145
74 Anil Gupta 919782145


TreeSet

TreeSets guarantee log(n) time cost for the basic operations (add, remove and contains). TreeSets guarantee that elements of the set will be sorted in ascending, natural, or the one specified by you via its constructor. (by implementing Comparable interface).The elements in a TreeSet are ordered using their natural ordering, or by a Comparator provided at set creation time, counting on which constructor is used to create the object. Note that the ordering maintained by a group (whether or not a particular comparator is provided) must be according to equals if it's to properly implement the Set interface. This is often so because the Set interface is specified in terms of the equals operation, but a TreeSet Object performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal.

Example

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
class Contact implements Comparable<Contact>{
      int id;
      String fname;
      String lname;
      long mob;
      public Contact(int id, String fname, String lname, long mob) {
            super();
            this.id = id;
            this.fname = fname;
            this.lname = lname;
            this.mob = mob;
      }
      @Override
      public int compareTo(Contact o) {
            return this.id-o.id;
      }
     
}

public class SetsDemo {//Sets in Java

      public static void main(String[] args)
      {//Ordered Sets
           
            Set<Contact> contacts=new TreeSet<>();
            contacts.add(new Contact(70, "Rohan", "Khanna", 97451287));
            contacts.add(new Contact(12, "Amit", "Sharma", 919782145));
            contacts.add(new Contact(121, "Vinod", "Kumar", 919782145));
            contacts.add(new Contact(74, "Anil", "Gupta", 919782145));
            contacts.add(new Contact(98, "Sourav", "Puri", 919782145));
            contacts.add(new Contact(100, "Vinay", "Verma", 919782145));
            //few contacts are added
            Iterator<Contact> i=contacts.iterator();
            while(i.hasNext())
            {
                  Contact contact=i.next();
                  System.out.println(contact.id+"\t"+contact.fname+"\t"+contact.lname+"\t"+contact.mob);
            }
      }
}
Output:
12 Amit Sharma 919782145
70 Rohan Khanna 97451287
74 Anil Gupta 919782145
98 Sourav Puri 919782145
100 Vinay Verma 919782145
121 Vinod Kumar 919782145


Video Tutorial