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.
Below illustration depicts the position of
LinkedHashSet
class in java collection frameworkAs 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
ALinkedHashSet
stores elements in buckets. Capacity defines the number of buckets in aLinkedHashSet
. - Load factor
It is a measure of how full theLinkedHashSet
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 forLinkedHashSet
is 0.75. This means that whenLinkedHashSet
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
- Java
LinkedHashSet
is an ordered collection. Elements maintain insertion order. - Elements of java
LinkedHashSet
can not be inserted using index. - A java
LinkedHashSet
does not provide any method to get or retrieve its elements. - Java
LinkedHashSet
does not allow duplicate elements. - Java
LinkedHashSet
allows onenull
element. You can add multiplenull
elements but only last one will be present. - 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 asString
,Integer
etc., or user defined classes such as Person, Shape etc. LinkedHashSet
is not synchronized or not thread safe. This means that if multiple threads are operating on aLinkedHashSet
concurrently, then it should be externally synchronized.LinkedHashSet
internally stores values as keys in aLinkedHashMap
.
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.
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
LinkedHashSet empty? true
LinkedHashSet size: 3
LinkedHashSet size: 2
LinkedHashSet size: 2
LinkedHashSet contains name: true
LinkedHashSet contains name: false
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
Next set element: Def
Next set element: Ghi
Next set element: Abc
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.
has a method
LinkedHashSetaddAll()
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 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
andHashSet
implement Set interface.LinkedHashSet
andHashSet
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
andCloneable
.
Following are the differences between LinkedHashSet
and HashSet
LinkedHashSet
maintains insertion order whileHashSet
does not maintain it.LinkedHashSet
uses aLinkedHashMap
to store the elements internally whileHashSet
uses aHashMap
.LinkedHashSet
is slightly slower thanHashSet
.LinkedHashSet
extendsHashSet
orLinkedHashSet
is the child class ofHashSet
.LinkedHashSet
was introduced in java 1.4 whileHashSet
in java 1.2.
LinkedHashSet vs TreeSet
Following are the similarities between LinkedHashSet
and TreeSet
LinkedHashSet
andTreeSet
do not allow duplicate elements.- Both do not allow elements to be accessed by index.
- Both reside in
java.util
package. - Both implement
Serializable
andCloneable
.
Following are the differences between LinkedHashSet
and TreeSet
LinkedHashSet
implements Set interface whileTreeSet
implementsNavigableSet
interface.LinkedHashSet
maintains insertion order whileTreeSet
does not maintain it.LinkedHashSet
does not sort elements whileTreeSet
sorts elements in their natural ordering.LinkedHashSet
uses aLinkedHashMap
to store the elements internally whileHashSet
uses aHashMap
.TreeSet
is slightly slower thanLinkedHashSet
.LinkedHashSet
has a complexity of O(1) for addition, removal and retrieval operations whileTreeSet
has a complexity of O(log(n)).LinkedHashSet
was introduced in java 1.4 whileTreeSet
in java 1.2.