Java LinkedHashSet and Its’ Difference from HashSet

In this blog post we’ll cover what is Java LinkedHashSet, when and how to use it. In addition to that we’ll also talk about how it is different from the HashSet.

What is Java LinkedHashSet?

Java LinkedHashSet is an implementation of a hash table and a doubly linked list.  LinkedHashSet doesn’t allow duplicates and keeps the insertion ordering of its’ elements. In other words, when iterating over a LinkedHashSet the elements are always going to be in the order they were inserted into the set.

LinkedHashSet extends the HashSet class and uses LinkedHashMap to hold its’ elements. Even more, it doesn’t define any methods on its’ own. All of the methods we can use are inherited from other classes (like its’ parent class HashSet) and interfaces it extends or implements. The only method it overrides is a spliterator.

However, LinkedHashSet does offer 3 different constructors to choose from:

public LinkedHashSet() {
    super(16, .75f, true);
}

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

As you can see all the constructors call the parent constructors in the HashSet class (by using the keyword super). These accept 3 different parameters: initialCapacity, loadFactor and a boolean parameter set to true. The initialCapacity holds a default value of 16 and the loadFactor is 0.75. Capacity defines how many elements fit into the set. Load factor defines how full the set can get before it needs to grow its’ size to fit more elements into it. When LinkedHashSet reaches the maximum load capacity, it doubles its’ size. The third boolean parameter is actually just a “dummy” that is always ignored. It is a way to distinguish LinkedHashSet constructors from the other ones.

It is also important to know that LinkedHashSet is not synchronized. To make it thread safe we can wrap it using the Collections.synchronizedSet method:

Set<Integer> synchronizedSet = 
        Collections.synchronizedSet(new LinkedHashSet<>());

As a final note, LinkedHashSet has the time cost of O(1) for its’ basic operations add, remove and contains. Iterating over the set has O(n) time complexity where n is the size of the set.

When to use Java LinkedHashSet?

Whenever you need to have unique elements (no duplicates) in a collection that keeps their insertion ordering. If you don’t care about the ordering of the elements, use a HashSet instead. Or, if it’s alright to have duplicates but need to keep the insertion ordering in a collection, you could consider using an ArrayList or a LinkedList.

LinkedHashSet vs HashSet

LinkedHashSet and HashSet have a lot of things in common:

• They don’t allow duplicate elements.
• Their default initial capacity is 16 and default load factor 0.75.
• Both are using hash table.
• Both have O(1) time cost for their basic operations (add, remove, contains). LinkedHashSet might be slightly more expensive when inserting elements as it also needs to add references on the previous and next elements.
• Both have O(n) time cost for iterating over the elements. HashSet might be slightly worse as n here is the capacity. For LinkedHashSet n is just the size of it.

Following is how they are different from each other:

• LinkedHashSet keeps the insertion ordering of its’ elements. HashSet doesn’t guarantee any ordering of its’ elements.
• LinkedHashSet uses a LinkedHashMap to keep its’ elements. In contrast, HashSet uses a HashMap.
• LinkedHashSet uses doubly-linked list in addition to the hash table.
• LinkedHashSet has been available since JDK 1.4, HashSet since JDK 1.2.

How to use LinkedHashSet?

LinkedHashSet in Java is simple to use. Lets’ take a look at some examples of how to create a LinkedHashSet and show some possible usages of it.

To start with, lets create an empty LinkedHashSet and populate it with some letters. Then, we’ll print out all of the letters it contains.

// Creating an empty set of letters
Set<String> letters = new LinkedHashSet<>();
letters.add("A");
letters.add("B");
letters.add("C");
letters.add("D");
letters.add("E");


// Display all letters
System.out.println(letters);

Output:

[A, B, C, D, E]

Lets also print out the size of the set:

// Display how many letters we have in the set
System.out.println("Number of letters in the set: " + letters.size());

Output:

Number of letters in the set: 5

We can also create a new LinkedHashSet otherLetters out of another collection and add these letters to our already existing letters set:

// Create new set by populating it with a list of letters
Set<String> otherLetters = new LinkedHashSet<>(
        Arrays.asList("X", "Y")
);

// Add otherLetters set to the letters set and display it
letters.addAll(otherLetters);
System.out.println(letters);

The output:

[A, B, C, D, E, X, Y]

As you remember LinkedHashSet doesn’t allow duplicates. Lets see this in action:

// Trying to add letter X that already exists in the set.
// Should return false because HashSet ignores duplicates
System.out.println("Added letter X: " + letters.add("X"));

The output:

Added letter X: false

As a final example lets remove the letter X from the set:

// Check if set contains letter X
System.out.println(
        "(Before remove) Set contains X: " + letters.contains("X")
);

letters.remove("X");

// Check if set contains a letter
System.out.println(
        "(After remove) Set contains X: " + letters.contains("X")
);

The output:

(Before remove) Set contains X: true
(After remove) Set contains X: false

Conclusion

LinkedHashSet is an implementation of a hash table and a doubly linked list. It keeps the insertion ordering of its’ elements. In addition, it is not thread safe and doesn’t allow duplicate elements. You should use it instead of a HashSet when the ordering of the elements is important.