LinkedHashSet in java

A set in java represents an unordered collection which can contain only unique elements or the elements which are not duplicate.

A java set is represented by Set interface. LinkedHashSet class implements this interface and hence all its methods.

A LinkedHashSet maintains the order of insertion,  elements are retrieved in the same order in which they were inserted. This is because it stores the elements in a doubly linked list with each node containing the reference of next and previous elements.

A LinkedHashSet does not support inserting elements using indexes since a set is not ordered. Also, LinkedHashSet does not provide any methods to retrieve values.

Java LinkedHashSet hierarchy
Below illustration depicts the position of LinkedHashSet class in java collection framework

As can be seen from the above image, LinkedHashSet is the child class of java HashSet class.
Java LinkedHashSet creation
A LinkedHashSet can be created using any of its constructors and new operator.

Following are the different constructors in LinkedHashSet.

1. public LinkedHashSet()
Creates an empty LinkedHashSet with a default capacity of 16.
Example,

// empty hashset implementation 
Set<String> setOne = new LinkedHashSet<>();

2. public LinkedHashSet(Collection)
Creates a LinkedHashSet and populates it with all the elements of the supplied collection.
This collection may be a list or another set or any object that implements java.util.Collection interface.
Example,

// hashset with collection
List<String> list = List.of("A", "B"): 
Set<String> setFour = new LinkedHashSet<>(list);

3. public LinkedHashSet(int capacity, float load)
Creates a HashSet with the supplied capacity and load factor.

• Capacity
  A LinkedHashSet stores elements in buckets. Capacity defines the number of buckets in a LinkedHashSet.
• Load factor
  It is a measure of how full the LinkedHashSet should become when its size should be increased.
  When the number of buckets exceed the product of load factor and capacity, then its capacity is doubled(also called rehashing).
  Default load factor for LinkedHashSet is 0.75. This means that when LinkedHashSet becomes 75% full, it is rehashed.

// hashset with load factor and capacity 
Set<Double> setThree = new LinkedHashSet<>(25, 0.6);

4. public LinkedHashSet(int capacity)
Creates a LinkedHashSet with the supplied capacity. Example,

// linkedhashset with capacity of 25
Set<Integer> setTwo = new LinkedHashSet<>(25);

Java LinkedHashSet features

1. Java LinkedHashSet is an ordered collection. Elements maintain insertion order.
2. Elements of java LinkedHashSet can not be inserted using index.
3. A java LinkedHashSet does not provide any method to get or retrieve its elements.
4. Java LinkedHashSet does not allow duplicate elements.
5. Java LinkedHashSet allows one  null element. You can add multiple null elements but only last one will be present.
6. A java LinkedHashSet instance can be generic. This means that it can hold elements of a particular type.
   This type may be an inbuilt java type such as String, Integer etc., or user defined classes such as Person, Shape etc.
7. LinkedHashSet is not synchronized or not thread safe. This means that if multiple threads are operating on a LinkedHashSet  concurrently, then it should be externally synchronized.
8. LinkedHashSet internally stores values as keys in a LinkedHashMap.

LinkedHashSet internal working
A LinkedHashSet is built on a LinkedHashMap. That is, it uses a LinkedHashMap to store values internally.
So, when a LinkedHashSet is created, following is what happens internally

map = new LinkedHashMap<>();

Elements of LinkedHashSet are added as keys to this LinkedHashMap.

When an element is added to a LinkedHashSet, it calculates its hash code. To determine hash code, hashCode() method is invoked.
hashCode() method is defined in java.lang.Object class.

If the element overrides hashCode() in its class, then it is invoked, else hashCode() of Object will be called.
Hash code defines the position or bucket where the element is placed.

How LinkedHashSet checks for duplicates
It might happen that two different elements have the same hash code, which means, that they should be placed in the same bucket.
This is called hash collision.

In case of a hash collision, the element is compared with the existing element using their equals() method. Again, equals() method is defined in java.lang.Object class.
But, if the class of element overrides equals(), then it will be invoked.

If both the elements are same as per equals(), existing element is replaced with the newer one.
If the elements are not same, then the new element is also placed at the same bucket location, with existing element pointing to the new element.
That is, existing element now contains a reference to the new element.

Now, if a third element with same hash code is added, then the same process is repeated. It replaces an existing element which is same as the new element as per equals() or is added to the same bucket, if it is unique.

Same procedure is performed while removing an element from LinkedHashSet.
Important LinkedHashSet methods
Following are commonly used methods of java.util.LinkedHashSet.

1. add(E)
Adds the element supplied as argument to the set if it is not already present.
That is, there is no element in the set which is same as the argument element according to equals() method.
add() returns true, if the element was added to the set and false otherwise.

This method throws

• ClassCastException, if the type of added element is incompatible with the type of set.
• IllegalArgumentException if some property of the supplied argument does not allow adding it to the set.

2. addAll(Collection)
Adds all the elements of the supplied collection argument to the end of this set.
Throws

• ClassCastException, if the type of added element is incompatible with the type of set.
• IllegalArgumentException if some property of the supplied argument does not allow adding it to the set.

3. contains(Object)
Returns true if any element of LinkedHashSet matches the supplied argument element. Elements are compared and should match as per equals() method.
Throws

• ClassCastException, if the type of added element is incompatible with the type of set.

4. clear()
Removes all elements from LinkedHashSet.

5. isEmpty()
Returns true if LinkedHashSet does not contain any elements.

6. iterator()
Returns an iterator to loop over the elements of the set.

7. remove(E)
Removes the first element from the set which matches the supplied argument element. Elements are compared and should match as per equals() method.
Throws

• ClassCastException, if the type of element removed is incompatible with the type of set.

8. removeAll(c)
It removes all the elements from LinkedHashSet that are present in the collection supplied as argument. Argument collection may be a list, set or a type that implements Collections interface.

Returns true, if any element is removed from the set.
Throws

• ClassCastException, if the type of element removed is incompatible with the type of set.

9. retainAll(c)
Retails all the elements in LinkedHashSet that are present in the collection supplied as argument and removes all others.
This method can be considered as the opposite of removeAll().

Returns true, if any element is removed from the set.
Throws,

• ClassCastException, if the type of added element is incompatible with the type of set.
• IllegalArgumentException, if some property of the supplied argument does not allow adding it to the set.

10. toArray()
Converts LinkedHashSet to a java array. Returns an Object array containing all the elements of the set.

Java HashSet example
Below is a code snippet that uses LinkedHashSet class and shows the usage of its methods described above.

 // create a hashset
Set<String> names = new LinkedHashSet<>();
System.out.println("LinkedHashSet empty? " + names.isEmpty());
// add elements
names.add("Abc");
names.add("Def");
names.add("Ghi");
System.out.println("LinkedHashSet size: " + names.size());
// remove element
names.remove("Abc");
System.out.println("LinkedHashSet size: " + names.size());
// remove non-existent element
names.remove("Xyz");
System.out.println("LinkedHashSet size: " + names.size());
// check if set has value
boolean contains = names.contains("Ghi");
System.out.println("LinkedHashSet contains name: " + contains);
contains = names.contains("Xyz");
System.out.println("LinkedHashSet contains name: " + contains);

Below is the output

Iterating  java LinkedHashSet
A HashSet can be iterated

1. Using an iterator
LinkedHashSet has an iterator() method which returns a java iterator.

This iterator can be used to loop through the LinkedHashSet using its next() and hasNext() methods. Example,

Set<String> names = new LinkedHashSet<>();
// add elements
names.add("Abc");
names.add("Def");
names.add("Ghi");
Iterator<String> iterator = names.iterator();
while(iterator.hasNext()) {
  System.out.println("Next set element: " + iterator.next());
}

Output is

Note that the order in which the elements are retrieved is different from the one in which the elements were added.
This shows that LinkedHashSet is unordered.
2. Using java 8 forEach()
Java 8 introduced a forEach() method, which can be used to iterate through the elements of a LinkedHashSet. Example,

Set<String> names = new LinkedHashSet<>(); 
// add elements 
names.add("Abc"); 
names.add("Def"); 
names.add("Ghi"); 
names.forEach( 
      e -> System.out.println("Next set element: " + e
);

Union of LinkedHashSets
Union means combining two sets.
LinkedHashSet has a method addAll() which accepts another collection as argument and adds all the elements of this collection to it.

So,  if we use addAll() and pass another LinkedHashSet as argument, then this set will contain the elements of both the sets. Example,

Set<String> setOne = new LinkedHashSet<>();
setOne.add("A");
setOne.add("C");
setOne.add("E");
Set<String> setTwo = new LinkedHashSet<>();
setTwo.add("B");
setTwo.add("D");
setTwo.add("F");
setTwo.addAll(setOne);
System.out.println(setTwo.toString());

Output set is

If there are any duplicate elements in both the sets, then they will be overwritten so that the set contains only unique elements.

Intersection of LinkedHashSets
Intersection of two LinkedHashSet objects means determining the common elements between the two sets.
LinkedHashSet has a retainAll() method which removes all the elements from the LinkedHashSet on which it is called, that are not present in the argument collection.

So, if we supply a LinkedHashSet as argument to retailAll(), then the LinkedHashSet calling this method will contain only the elements present in both the sets, or the intersection of sets. Example,

Set<String> setOne = new LinkedHashSet<>();
setOne.add("A");
setOne.add("C");
setOne.add("E");
setOne.add("F");
Set<String> setTwo = new LinkedHashSet<>();
setTwo.add("B");
setTwo.add("C");
setTwo.add("D");
setTwo.add("F");
setTwo.retainAll(setOne);
System.out.println(setTwo);

Output is

These are the common elements of both the sets.
LinkedHashSet vs HashSet
Following are the similarities between LinkedHashSet and HashSet

• LinkedHashSet and HashSet implement Set interface.
• LinkedHashSet and HashSet do not allow duplicate elements.
• Both do not allow elements to be accessed by index.
• Both reside in java.util package.
• Both have same complexity( O(1) ) for addition, removal and retrieval operations.
• Both implement Serializable and Cloneable.

Following are the differences between LinkedHashSet and HashSet

• LinkedHashSet maintains insertion order while HashSet does not maintain it.
• LinkedHashSet uses a LinkedHashMap to store the elements internally while HashSet uses a HashMap.
• LinkedHashSet is slightly slower than HashSet.
• LinkedHashSet extends HashSet or LinkedHashSet is the child class of HashSet.
• LinkedHashSet was introduced in java 1.4 while HashSet in java 1.2.

LinkedHashSet vs TreeSet
Following are the similarities between LinkedHashSet and TreeSet

• LinkedHashSet and TreeSet do not allow duplicate elements.
• Both do not allow elements to be accessed by index.
• Both reside in java.util package.
• Both implement Serializable and Cloneable.

Following are the differences between LinkedHashSet and TreeSet

• LinkedHashSet implements Set interface while TreeSet implements NavigableSet interface.
• LinkedHashSet maintains insertion order while TreeSet does not maintain it.
• LinkedHashSet does not sort elements while TreeSet sorts elements in their natural ordering.
• LinkedHashSet uses a LinkedHashMap to store the elements internally while HashSet uses a HashMap.
• TreeSet is slightly slower than LinkedHashSet.
• LinkedHashSet has a complexity of O(1) for addition, removal and retrieval operations while TreeSet has a complexity of O(log(n)).
• LinkedHashSet was introduced in java 1.4 while TreeSet in java 1.2.

Hope the article was useful.