Java LinkedHashSet

The Java LinkedHashSet Class

The LinkedHashSet class is a Set implementation that combines the features of a HashSet and a LinkedList.

It is a hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion order).

Key Characteristics of LinkedHashSet

• No Duplicates: Like all Set implementations, it does not allow duplicate elements.
• Maintains Insertion Order: When you iterate over a LinkedHashSet, the elements will appear in the order they were added. This is its main advantage over HashSet.
• Fast Performance: It provides constant time performance (O(1)) for the basic operations (add, remove, contains), just like HashSet. This performance is likely to be slightly below that of HashSet, due to the added expense of maintaining the linked list.
• Allows null: A LinkedHashSet can contain one null element.

How LinkedHashSet Works

A LinkedHashSet uses a hash table for storage, just like a HashSet, which gives it the fast O(1) performance. In addition, it embeds a doubly-linked list that connects all the elements in the order they were inserted.

When an element is added, it's added to the hash table for fast lookups and also added to the end of the linked list to maintain the insertion order.

When to Use LinkedHashSet

LinkedHashSet is the perfect choice when you need a collection that:

1. Guarantees uniqueness of elements.
2. Requires the elements to be stored in the order they were inserted.
3. Requires high-speed access, insertion, and deletion.

It's a great middle-ground between the unordered, high-performance HashSet and the sorted, slower TreeSet.

LinkedHashSet Example

Here is an example demonstrating the insertion-order behavior of a LinkedHashSet.

import java.util.LinkedHashSet;

public class Main {
  public static void main(String[] args) {
    LinkedHashSet<String> days = new LinkedHashSet<>();
    // Add items
    days.add("Wednesday");
    days.add("Monday");
    days.add("Tuesday");
    days.add("Monday"); // This will be ignored
    // The elements are iterated in the order they were inserted
    System.out.println("LinkedHashSet: " + days);
    // Remove an item
    days.remove("Monday");
    System.out.println("After removing Monday: " + days);
    // Loop through the set
    System.out.println("--- Looping through days ---");
    for (String day : days) {
      System.out.println(day);
    }
  }
}