Set Interface & its implementations

🔹 What is the Set Interface?

The Set interface in Java is a part of the Java Collections Framework. It represents a collection of unique elements, i.e., it does not allow duplicates.

📦 Package: java.util.Set
🔑 Set is an unordered collection by default (order is not guaranteed unless using specific implementations like LinkedHashSet or TreeSet).

✅ Key Properties:

Feature Behavior
Duplicates ❌ Not allowed
Null values ✅ Allowed (only one null value in most implementations)
Order ❌ Not guaranteed (HashSet)
Thread-safe ❌ Not by default

🔧 Common Implementations of Set:

Implementation Description
HashSet Fast, unordered, based on hash table
LinkedHashSet Maintains insertion order
TreeSet Sorted set (natural or custom comparator)

🧰 Common Methods in Set:

Method Description
add(E e) Adds element if it’s not already present
remove(Object o) Removes the specified element
contains(Object o) Checks if element exists
size() Returns number of elements
clear() Removes all elements
isEmpty() Checks if the set is empty

🔍 Example:

import java.util.*;

public class SetExample {
    public static void main(String[] args) {
        Set<String> fruits = new HashSet<>();

        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Apple"); // Duplicate, will be ignored

        System.out.println(fruits); // Output may not be in order
    }
}

📌 When to Use Set?

  • When uniqueness of elements is required
  • When order doesn't matter (use HashSet)
  • When sorted results are needed (use TreeSet)
  • When insertion order matters (use LinkedHashSet)

 

✅ SET Implementations:

🔹 1. HashSet

  • Implements: Set interface
  • Underlying Data Structure: Hash Table
  • Order: ❌ No guaranteed order
  • Duplicates: ❌ Not allowed
  • Nulls: ✅ Allowed (only one)
  • Performance: ✅ Fast (O(1) for add, remove, contains)

✅ Use-case:

When you want unique elements and don’t care about order.

Set<String> set = new HashSet<>();

🔸 2. LinkedHashSet

  • Implements: Set interface
  • Underlying Data Structure: Hash Table + Linked List
  • Order: ✅ Maintains insertion order
  • Duplicates: ❌ Not allowed
  • Nulls: ✅ Allowed
  • Performance: Slightly slower than HashSet

✅ Use-case:

When you want unique elements in the order you added them.

Set<String> set = new HashSet<>();

🔺 3. TreeSet

  • Implements: NavigableSet → SortedSet → Set
  • Underlying Data Structure: Red-Black Tree
  • Order: ✅ Sorted (natural or custom)
  • Duplicates: ❌ Not allowed
  • Nulls: ❌ Not allowed (throws NullPointerException)
  • Performance: O(log n) for add, remove, search

✅ Use-case:

When you need sorted unique elements.

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

📦 Summary Table:

Type Ordered? Sorted? Allows Null? Performance Use-case
HashSet ❌ No ❌ No ✅ One ✅ Fastest (O(1)) Unordered unique elements
LinkedHashSet ✅ Yes (insertion) ❌ No ✅ One ⚠️ Slower than HashSet Maintain insertion order with uniqueness
TreeSet ✅ Yes ✅ Yes ❌ No 🕒 Slower (O log n) Need sorted unique elements


🧪 Example:

Set<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(1);
numbers.add(3);
System.out.println(numbers); // Output: [1, 3, 5]

⚙️ Internal Architecture:

  • HashSet is backed by a HashMap.
  • Every element added to a HashSet is stored as a key in the internal HashMap.
  • A constant dummy value (like PRESENT) is used as the value.

Internal Code (simplified):

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

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

🧠 What Happens When You Add an Element?

Example:

Set<String> set = new HashSet<>();
set.add("Apple");

Internally:

  1. hashCode() of "Apple" is calculated.
  2. The hash is used to find a bucket (index) in the internal array of HashMap.
  3. If no collision → stored directly.
  4. If collision → uses a LinkedList (or Tree in Java 8+) at that bucket.
  5. It checks for equality using .equals() to ensure no duplicates.

📌 Key Points:

Feature Details
Backed by HashMap
Duplicate check Uses .equals() method
Bucket index Calculated using hashCode()
Collision handling Chaining using LinkedList or Tree (if bucket size > threshold)
Order ❌ Not maintained

🚫 Why null is Allowed Once?

  • null can be added because HashMap allows one null key.
  • But only one, because the second null is considered duplicate (same key).

🧪 Performance:

Operation Time Complexity
Add O(1) average
Remove O(1) average
Contains O(1) average

Worst case can be O(n) if too many hash collisions occur.

Back to blog

Leave a comment

Please note, comments need to be approved before they are published.