Java collections: Set

  1. Set is an unordered collection of objects wherein user has no control over the insertion order.
  2. Duplicate values cannot be stored in Set, that means an element can only exist once in a Set.
  3. The Set interface contains only methods inherited from Collection and adds the restriction that duplicate elements are prohibited.
Sets are further classified into the following:
  1. HashSet
  2. LinkedHashSet
  3. TreeSet
Let’s go into detail on each one of them:

 1) HashSet:
  1. Java HashSet class is used to create a collection that uses a hash table for storage.
  2. It inherits the AbstractSet class and implements Set interface.
  3. HashSet stores the elements by using a mechanism called hashing.
  4. HashSet class does not maintains insertion order.
  5. HashSet contains unique elements only.

HashSet Examples:
1) Add element and traverse through Hashset.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.HashSet;
import java.util.Iterator;

public class HashSetDemo {

 public static void main(String[] args) {
  HashSet<String> set = new HashSet<String>();
  HashSet<String> set1 = new HashSet<String>();
  
  //Adding elements
  set.add("Ravi");
  set.add("Vijay");
  set.add("Ravi");
  set.add("Yusuf");
  set.add("Vivek");
  set1.add("Pranav");
  set1.add("Rajesh");

  System.out.println(set.size());
  System.out.println(set.isEmpty());
  set1.addAll(set);

  // Traversing elements via Iterator
  Iterator<String> itr = set1.iterator();
  while (itr.hasNext()) {
   System.out.println(itr.next());
  }

  // Traversing elements via foreach loop
  for (String s : set1) {
   System.out.println(s);
  }
 }
}

2) User-defined class objects in Java HashSet

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public class Book {

 String name, author, publisher;
 int id, quantity;

 public Book(int id, String name, String author, String publisher, int quantity) {

  this.id = id;
  this.name = name;
  this.author = author;
  this.publisher = publisher;
  this.quantity = quantity;
 }
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.HashSet;

public class HashSetDemo {

 public static void main(String[] args) {
  HashSet<Book> bookset = new HashSet<Book>();

  // Creating Books
  Book b1 = new Book(101, "Let us C", "Yashwant Kanetkar", "BPB", 8);
  Book b2 = new Book(102, "Data Communications & Networking", "Forouzan", "Mc Graw Hill", 4);
  Book b3 = new Book(103, "Operating System", "Galvin", "Wiley", 6);

  // Adding Books to HashSet
  bookset.add(b1);
  bookset.add(b2);
  bookset.add(b3);

  // Traversing HashSet
  for (Book b : bookset) {
   System.out.println(b.id + " " + b.name + " " + b.author + b.publisher + " " + b.quantity);
  }
 }
}

How HashSet internally works?
Whenever we create a HashSet, it internally creates a HashMap and if we insert an element into this HashSet using add() method, it actually call put() method on internally created HashMap object with element you have specified as it’s key and constant Object called “PRESENT” as it’s value.

As we know in a HashMap each key is unique and when we call put(Key, Value) method, it returns the previous value associated with key, or null if there was no mapping for key. So in add() method we check the return value of map.put(key, value) method with null value.

1) If map.put(key, value) returns null, then the statement “map.put(e, PRESENT) == null” will return true and element is added to the HashSet(internally HashMap).
2) If map.put(key, value) returns old value of the key, then the statement “map.put(e, PRESENT) == null” will return false and element is not added to the HashSet(internally HashMap).

2) LinkedHashSet:
  1. LinkedHashSet class is a Hash table and Linked list implementation of the set interface.
  2. It inherits HashSet class and implements Set interface.
  3. Contains unique elements only like HashSet.
  4. LinkedHashSet class maintains insertion order.


LinkedHashSet Examples:
1) Add element and traverse through LinkedHashset.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Iterator;
import java.util.LinkedHashSet;

public class LinkedHashSetDemo {

 public static void main(String[] args) {

  LinkedHashSet<String> lhs = new LinkedHashSet<String>();

  //Adding objects
  lhs.add("Ravi");
  lhs.add("Vijay");
  lhs.add("Ravi");
  lhs.add("Sanjay");
  lhs.add("Rajesh");

  Iterator<String> itr = lhs.iterator();

  while (itr.hasNext()) {
   System.out.println(itr.next());
  }

  for (String s : lhs) {
   System.out.println(s);
  }
 }
}

2) User-defined class objects in Java LinkedHashSet.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public class Book {

 String name, author, publisher;
 int id, quantity;

 public Book(int id, String name, String author, String publisher, int quantity) {

  this.id = id;
  this.name = name;
  this.author = author;
  this.publisher = publisher;
  this.quantity = quantity;
 }
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Iterator;
import java.util.LinkedHashSet;

public class LinkedHashSetDemo {

 public static void main(String[] args) {

  LinkedHashSet<Book> hs = new LinkedHashSet<Book>();

  // Creating Books
  Book b1 = new Book(101, "Let us C", "Yashwant Kanetkar", "BPB", 8);
  Book b2 = new Book(102, "Data Communications & Networking", "Forouzan", "Mc Graw Hill", 4);
  Book b3 = new Book(103, "Operating System", "Galvin", "Wiley", 6);

  // Adding Books to hash table
  hs.add(b1);
  hs.add(b2);
  hs.add(b3);

  // Traversing hash table
  for (Book b : hs) {
   System.out.println(b.id + " " + b.name + " " + b.author + " " + b.publisher + " " + b.quantity);
  }
 }
}

Question: How LinkedHashSet Maintains Unique Elements?
As we know in LinkedHashMap each key is unique . So what we do in the LinkedHashSet is that we pass the argument in the add(Elemene E) that is E as a key in the LinkedHashMap . 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 LinkedHashSet like  linkedhashset.add(5)   what java does internally is that it will put that element E here 5 as a key in the LinkedHashMap(created during LinkedHashSet object creation) and some dummy value that is Object's object is passed as a value to the key .

 Since LinkedHashMap put(Key k , Value v ) method does not have its own implementation . LinkedHashMap put(Key k , Value v ) method uses HashMap put(Key k , Value v ) method.

 Now if you see the code of the HashMap 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 map
2.  Old Value of the key , if key is duplicate

 So , in LinkedHashSet add() method ,  we check the return value of map.put(key,value) method with null value
i.e.

 public boolean add(E e) {
            return map.put(e, PRESENT)==null;
  }

 So , if map.put(key,value) returns null ,then
map.put(e, PRESENT)==null      will return true and element is added to the LinkedHashSet.

So , if map.put(key,value) returns old value of the key ,then

map.put(e, PRESENT)==null      will return false and element is  not added to the LinkedHashSet .

3) TreeSet:
  1. TreeSet class implements the Set interface that uses a tree for storage.
  2. It inherits AbstractSet class and implements NavigableSet interface.
  3. Contains unique elements only like HashSet.
  4. TreeSet class stores elements in sorted order.

TreeSet Example:
1) Add element and traverse through TreeSet.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Iterator;
import java.util.TreeSet;

public class TreeSetDemo {

 public static void main(String[] args) {

  TreeSet<String> ts = new TreeSet<String>();

  ts.add("33");
  ts.add("44");
  ts.add("22");
  ts.add("11");

  // Traversing elements
  Iterator<String> itr = ts.iterator();

  while (itr.hasNext()) {
   System.out.println(itr.next());
  }
 }
}

output: 11 22 33 44

 2) User-defined class objects in Java TreeSet.

In this example we see a TreeSet where we are adding books to set and printing all the books. The elements in TreeSet must be of Comparable type as tree set stores elements in sorted order. String and Wrapper classes are Comparable by default. To add user-defined objects in TreeSet, you need to implement Comparable interface to print them in sorted manner.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Book implements Comparable<Book> {

 String name, author, publisher;
 int id, quantity;

 public Book(int id, String name, String author, String publisher, int quantity) {

  this.id = id;
  this.name = name;
  this.author = author;
  this.publisher = publisher;
  this.quantity = quantity;
 }

 @Override
 public int compareTo(Book b) {
  if (id > b.id) {
   return 1;
  } else if (id < b.id) {
   return -1;
  } else {
   return 0;
  }
 }
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Set;
import java.util.TreeSet;

public class TreeSetDemo {

 public static void main(String[] args) {

  Set<Book> set = new TreeSet<Book>();

  // Creating Books
  Book b1 = new Book(121, "Let us C", "Yashwant Kanetkar", "BPB", 8);
  Book b2 = new Book(233, "Operating System", "Galvin", "Wiley", 6);
  Book b3 = new Book(101, "Data Communications & Networking", "Forouzan", "Mc Graw Hill", 4);

  // Adding Books to TreeSet
  set.add(b1);
  set.add(b2);
  set.add(b3);

  // Traversing TreeSet
  for (Book b : set) {
   System.out.println(b.id + " " + b.name + " " + b.author + " " + b.publisher + " " + b.quantity);
  }
 }
}
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 map
2.  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 value
i.e.

public boolean add(E e) {
     return map.put(e, PRESENT)==null;
}

So , if map.put(key,value) returns null ,then
map.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 ,then map.put(e, PRESENT)==null      will return false and element is  not added to the TreeSet.

 Difference Java HashSet, LinkedHashSet and TreeSet


<-- Previous || Next -->

No comments:

Post a Comment

Subscribe to: Posts (Atom)