Post
Ask Question

HashSet Class and TreeSet Class in Java Collections

Introduction

The HashSet class and TreeSet class are two important implementations of the Set interface in Java Collections. The HashSet class is backed by a hash table and does not maintain any order of the elements, offering constant time performance for basic operations such as add, remove, and contains, assuming the hash function disperses the elements properly among the buckets. It ensures uniqueness by not allowing duplicate elements and is particularly useful when fast access and retrieval are required. On the other hand, the TreeSet class is backed by a tree structure, specifically a Red-Black tree, and maintains its elements in sorted order according to their natural ordering or a specified comparator. The TreeSet class provides guaranteed log(n) time cost for the basic operations (add, remove, and contain). It is ideal when a sorted set of elements is needed, and one can navigate the set using methods like first(), last(), headSet(), and tailSet(). Both classes do not allow null elements and are unsynchronized, meaning they are not thread-safe without external synchronization.

The HashSet class

The HashSet class extends the AbstractSet class and implements the Set interface, with the AbstractSet class itself extending the AbstractCollection class. The HashSet class is designed to create a collection that stores its elements in a hash table. Each element in the collection is associated with a unique value called a hash code, which serves as an index to store the object in the hash table. This method of storing information is known as hashing.

Constructor for the HashSet class are,

  • HashSet(): Constructs an empty HashSet.
  • HashSet(Collection c): Initializes the HashSet with the elements from collection c.
  • HashSet(int capacity): Initializes the HashSet with a specified capacity.
  • HashSet(int capacity, float fillRatio): Initializes the HashSet with a specified capacity and fill ratio

The fill ratio, ranging from 0.0 to 1.0, determines the initial size of the HashSet. If the number of elements exceeds the set's capacity, the HashSet automatically expands by multiplying its capacity by the fill ratio. The default fill ratio is 0.75.

The HashSet class inherits methods from its parent classes and the implemented Set interface. The following program demonstrates the use of these methods. It is important to note that HashSet does not guarantee any specific order for its elements; they may be stored in any order.

Source Code

import java.util.*;
class HashSetExample {
    public static void main(String[] args) {
        HashSet<String> hs = new HashSet<>();
        hs.add("D");
        hs.add("A");
        hs.add("C");
        hs.add("B");
        hs.add("E");     
        System.out.println("The elements available in the hash set are : " + hs);
    }
}

Output

Output

This code illustrates basic operations with `HashSet` in Java, emphasizing its unordered nature and unique element constraint. It's a straightforward example of using a collection to store elements and retrieve them for output.

The TreeSet Class

The TreeSet class implements the Set interface and stores its sorted elements in a tree structure. This class allows for efficient access and retrieval of elements, providing quicker operations due to the underlying tree structure.

The constructor for the TreeSet class can take the following forms.

  • TreeSet(): Constructs an empty TreeSet, with elements sorted in ascending order.
  • TreeSet(Collection c): Constructs a TreeSet containing the elements from the specified collection.
  • TreeSet(Comparator comp): Constructs a TreeSet based on the specified comparator.
  • TreeSet(SortedSet s): Constructs a TreeSet containing elements in the specified sorted order.

The program illustrates the usage of the TreeSet class.

import java.util.*;
class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<String> ts = new TreeSet<>();
        ts.add("B");
        ts.add("C");
        ts.add("A");
        ts.add("E");
        ts.add("D");   
        System.out.println("The elements available in the Tree set are : " + ts);
    }
}

Output

Command Prompt

Note that the elements are automatically arranged in sorted order.

This code showcases basic operations with `TreeSet` in Java, highlighting its capability to maintain elements in sorted order automatically. It's a straightforward example of using a collection to store elements and retrieve them sorted for output.

Summary

The HashSet and TreeSet classes in Java Collections are both implementations of the Set interface with distinct characteristics. HashSet uses a hash table to store unique elements, ensuring constant-time performance for basic operations like add, remove, and contain. It does not maintain any specific order for its elements, making it efficient for quick access but not ordered traversal. On the other hand, TreeSet stores elements in a Red-Black tree, ensuring elements are sorted either by their natural order or a specified comparator. This allows for efficient sorted operations with logarithmic time complexity for add, remove, and contain operations. TreeSet is ideal for scenarios requiring sorted data traversal and manipulation. Both classes inherit methods from parent classes and the Set interface, providing flexibility and functionality for managing collections of unique elements in Java applications.


Similar Articles