HashSet in Java | LinkedHashSet | SortedSet | TreeSet – Part 3

We are finally at the third and final part of JCF. Here we are going to learn about Set interface, HashSet in Java, LinkedHashSet class, SortedSet Interface and TreeSet class.

If you are coming here for the first time I advise you to check out Java Collections Framework – List and Queue to keep things in order which are like the part 1 and part 2 of JCF.

Set is like the third important type of collection. It cannot contain duplicate elements. Also, it can have at most one null element. It is the same implementation that you have learned about in Mathematics, about set being finite. So it would be safe to say that it models mathematical set abstraction.

Methods of Set Interface

If you are meaning to use Set interface you can make use of the following methods it has:

1. add(Object e)
2. addAll(Collection c)
3. clear()
4. contains(Object o)
5. containsAll(Collection c)
6. equals(Object o)
7. hashCode()
8. isEmpty()
9. iterator()
10. remove(Object o)
11. removeAll(Collection c)
12. retainAll(Collection c)
13. size()
14. toArray()
15. toArray(T[] a)

Of course since set is an interface we can’t instantiate it, and that’s where we make use of its inheriting class HashSet and LinkedHashSet. We will see HashSet in Java first.

HashSet in Java

HashSet in Java is a class that uses hash table to store its elements. What’s a hash table, you ask?

It is a data structure that entails storage of elements mapping keys to values. It makes use of hash function where the actual computation of indices of arrays happen. Eventually, these are put into buckets or slots. This mechanism of storing data like that is known as hashing. The following diagram explains it better:

When there is a need for quickly looking up the database for something, we make use of hash tables. You just need to have a key that maps it to the element you need.

A Hash Table’s real world usage is evident with HashMap Class which we are going to see at a later juncture.

There are no duplicate elements here either. HashSet in Java does not pay attention to the order of the elements.

HashSet extends the Class AbstractSet and implements the Set interface. Here the diagram would make it much clearer.

Constructors and Methods of HashSet in Java

Here are the constructor variants of HashSet in Java you could use whilst instantiating:

• HashSet()
• HashSet(Collection c)
• HashSet(int initialCapacity)
• HashSet(int initialCapacity, float loadFactor)

Now let’s take a look at the methods of HashSet that we could use:

1. add(Object e)
2. clear()
3. clone()
4. contains(Object o)
5. isEmpty()
6. iterator()
7. remove(Object o)
8. size()

Putting some in an example will help get some perspective:

HashSet<Integer>h = new HashSet<Integer>(); 

h.add(2); 
h.add(1); 
h.add(7); 
h.add(7);                                   //Trying a duplicate
System.out.println(h);
System.out.println(h.size()); 
Object k[] = h.toArray();                   //converting the set into an array
System.out.println(Arrays.toString(k));     //displaying that array
System.out.println(k[1]);                   //displaying an element
h.remove(1);                                //removing an element
System.out.println(h);

If you run the above program you will get:

[1, 2, 7]
3
[1, 2, 7]
2
[2, 7]

The duplicate has been completely ignored as if it didn’t exist there. The order has not been paid attention to. Rest of the things are pretty comprehensible.

LinkedHashSet Class

Another important class that implements the Set interface is the LinkedHashSet class. It rakes in the benefits of both Hash Table and Linked List. Hence, the name. It maintains a doubly-linked list.

It also extends the HashSet class. The good stuff from HashSet in Java shines on it as well. Here’s the hierarchy that will help you understand its placement:

LinkedHashSet being a set does not entertain duplicates. It pays attention to the order of the elements though.

Constructors and Methods of LinkedHashSet

Here are the constructors and methods of LinkedHashSet that you could use:

• LinkedHashSet()
• LinkedHashSet(Collection c)
• LinkedHashSet(int initialCapacity)
• LinkedHashSet(int initialCapacity, float loadFactor)

These are the methods of HashSet in Java that will come in handy:

1. add(Object e)
2. clear()
3. clone()
4. contains(Object o)
5. isEmpty()
6. iterator()
7. remove(Object o)
8. size()
9. equals(Object o)
10. hashCode()
11. removeAll(Collection c)
12. addAll(Collection c)
13. containsAll(Collection c)
14. retainAll(Collection c)
15. toArray()
16. toArray(T[] a)
17. toString()

Here’s an example to show how it works:

LinkedHashSet<Integer>h = new LinkedHashSet<Integer>(); 
h.add(3); 
h.add(6); 
h.add(8); 
h.add(9); 
h.add(8); 
System.out.println(h); 
System.out.println(h.size()); 
h.remove(8); 
System.out.println(h);

If you run the program above you will get this:

[3, 6, 8, 9]
4
[3, 6, 9]

Moving on to the next Interface on our JCF hierarchy. As you can see the way the elements were entered have been displayed in the same order.

SortedSet interface in Java

The SortedSet interface extends the Set interface and is useful when you wish to sort your set internally. SortedSet takes care of your stuff by arranging them in ascending order by default. Since there are no sorting methods provided for Sets, SortedSet comes to the rescue.

Elements that are sorted here are as per their natural ordering or if you have provided a Comparator to inscribe that logic beforehand with the constructor.

The following methods are used by SortedSet interface in Java:

1. comparator()
2. first()
3. headSet(Object toElement)
4. last()
5. spliterator()
6. subset(Object fromElement, Object toElement)
7. tailSet(Object fromElement)

Since SortedSet is an interface we will see a class that inherits it as it will be helpful to instantiate.

TreeSet Class in Java

TreeSet is a class that uses a data structure of a tree for storage. A tree is nothing but a data type that simulates an actual tree when it comes to storing data. There is one root value with countless subtrees having numerous children. Each joining vertex is called a node.

TreeSet extends NavigableSet which in turn extends SortedSet. SortedSet implements Set.

You can see that in the diagram below:

TreeSet elements get stored in ascending order and maintains it throughout. No duplicates are allowed. Its access and retrieval times are also super-fast.

Constructors and Methods of TreeSet Class Java

You can use the following constructors for the creation of a TreeSet:

• TreeSet()
• TreeSet(Collection c)
• TreeSet(Comparator comparator)
• TreeSet(SortedSet s)

Following methods come in handy too:

1. add(Object e)
2. addAll(Collection c)
3. ceiling(Object e)
4. clear()
5. clone()
6. comparator()
7. contains(Object o)
8. descendingIterator()
9. descendingSet()
10. first()
11. floor(Object e)
12. headSet(Object toElement)
13. headSet(Object toElement, boolean inclusive)
14. higher(Object e)
15. isEmpty()
16. iterator()
17. last()
18. lower(Object e)
19. pollFirst()
20. pollLast()
21. remove(Object o)
22. size()
23. spliterator()
24. subSet(Object fromElement, boolean fromInclusive, Object toElement, boolean toInclusive)
25. subSet(Object fromElement, Object toElement)
26. tailSet(Object fromElement)
27. tailSet(Object fromElement, boolean inclusive)

Rest of the methods are all inherited from its superclasses and interfaces so haven’t mentioned them all.

Let’s see an example to check some of the rare methods that we are coming across for the first time.

But first let’s check whether our set is automatically being adjusted as per ascending order or not:

TreeSet<Integer>h = new TreeSet<Integer>(); 
h.add(20); 
h.add(6); 
h.add(84); 
h.add(9); 
h.add(8); 
System.out.println(h);

If you run the above program you will get this:

[6, 8, 9, 20, 84]

As you can see all these numbers have been automatically put in ascending order.

ceiling() and floor() Method

If you want the least element that’s greater than or equal to the element specified, you can do so using ceiling() method.

Augment the following code:

System.out.println(h.ceiling(9));

What are the numbers that are greater than or equal to 9 in our example? 9, 20 and 84 right?

It will take the least element meaning 9 and give you the result as:

9

The opposite holds true for floor() method. It gives you the greatest element less than or equal to the element specified.

Augment this now:

System.out.println(h.floor(9));

The result is once again going to be 9 numbers less than or equal to 9 are 6, 8 and 9. The greatest of them all is:

9

higher() and lower() Methods

You could use higher() and lower() methods provided by TreeSet Class that returns the least element greater than given element:

System.out.println(h.higher(9));

The above will give you by the logic that numbers greater than 9 are 20 and 84, out of which 20 is the least.

20

In a similar manner if you were to grab the greatest element less than a given element use lower() method:

System.out.println(h.lower(9));

The above will go with the logic what are numbers less than 9? 6 and 8 right? So 8 is the greatest of the two:

8

headSet() and tailSet() Methods

But what if you wanted all the numbers that were less than a particular number or greater than your preferred number? That’s where headSet() and tailSet() methods come into picture.

If you use the following code in the example above it will give you numbers that are less than or equal to your preferred number:

System.out.println(h.headSet(9)); 
System.out.println(h.headSet(9,true));

Here the second line has true as the second parameter for “inclusive“. If you specify true there, it will include your number as well. Hence the result you will get for the above will be:

[6, 8]
[6, 8, 9]

If you use the following code in the example above it will give you numbers that are greater than or equal to your preferred number:

System.out.println(h.tailSet(9)); 
System.out.println(h.tailSet(9,true));

Here both method variants will give you the same result since the first line includes your number as well. If you run the above you will get:

[9, 20, 84]
[9, 20, 84]

descendingSet() Method

If you want the elements displayed in the reverse order you could simply use the descendingSet() method. Since TreeSet makes all of the numbers ascending by default it is quite natural the reverse order would be in descending order.

For descending order, descendingIterator() could be also used but that would give you the result in the form of an iterator.

Here’s an example. Just augment the following code and check it out for yourself:

System.out.println(h.descendingSet());

If you run the program now you will get:

[6, 8, 9, 20, 84]
[84, 20, 9, 8, 6]

where the latter is the calling of descendingSet() method’s result.

subSet() method

If you were to extract some elements from the set, you could do so using subSet() method.

System.out.println(h.subSet(8, 84));

If you run the above you will get all those elements that are shoehorned between 8 and 84 with 8 included. The second parameter will be exclusive. Hence the result:

[8, 9, 20]

You have another variant of subSet() method where you can specify if or not you would like to include both the fromElement and toElement:

System.out.println(h.subSet(8,false, 84,false));

If you run the above you will get:

[9, 20]

False means they have been excluded. You can try true yourself.

splitIterator() method

That takes us to the final elusive method of the day. What does the splitIterator() method do?

splitIterator implies that you are basically “splitting the iterator”.

It returns SplitIterator interface just as iterator() returned an Iterator interface. SplitIterator has the following methods that you could use:

1. characteristics()
2. estimateSize()
3. forEachRemaining(Consumer action)
4. getComparator()
5. getExactSizeIfKnown()
6. hasCharacteristics(int characteristics)
7. tryAdvance(Consumer action)
8. trySplit()

Will just put one example to show how to put it inside the code:

Spliterator si = h.spliterator(); 
System.out.println(si.estimateSize());

If you run the above you will get the estimated size of your set.

5

It was introduced in Java 8, and as of now, you should not worry about it.

That concludes our Collections Framework once and for all. Although there is the concept of HashMaps and Maps however they don’t fall under the collections interface category.

We will see that next.

Till then enjoy the glory of conquering Collections.