LinkedHashSet is a hash table and doubly linked list data structure implementation of the Set interface, a part of the Java Collections Framework
LinkedHashSet has the following features
Provides insertion-ordered iteration
Provides contains(Object), add(Object) and remove(Object) operations in constant-time performance
Duplicated elements are ignored. A null element is permitted
Elements are compared based on theirs equals and hashCode
LinkedHashSet is not thread-safe as it is an unsynchronized implementation. In multi-threading environment with at least one thread modifies the set, it must be synchronized externally
Internally, LinkedHashSet uses a LinkedHashMap instance to store, retrieve and maintain the insertion ordering of its elements
Let's walk through this tutorial to explore them in more details
The LinkedHashSet class hierarchy
LinkedHashSet implements the Set interface. Set extends from Collection and Iterable interfaces hierarchically
LinkedHashSet also extends the HashSet class which implements the Set interface
LinkedHashSet vs HashSet and TreeSet
LinkedHashSet provides insertion-ordered iteration and runs nearly as fast as HashSet
HashSet has no ordering guarantees and run faster than TreeSet (constant-time vs log-time for most operations)
TreeSet provides value-ordered iteration. TreeSet can be used to sort a HashSet or LinkedHashSet
Declare a LinkedHashSet
As a result of the class hierarchy, a LinkedHashSet can be declared as the following ways
@Test
public void declare() {
Set<Integer> linkedHashSet1 = new LinkedHashSet<>();
assertThat(linkedHashSet1).isInstanceOf(LinkedHashSet.class);
LinkedHashSet<Integer> linkedHashSet2 = new LinkedHashSet<>();
}
Create and Initialize
You can provide either Set.of or List.of methods, since Java 9, to the LinkedHashSet(Collection) constructor to create and init a LinkedHashSet in one line
The iteration order of the created LinkedHashSet will be decided by the iterator of the given collection
In the following example, the iteration order of linkedHashSet1 is unpredictable while linkedHashSet2 is predictable
@Test
public void initInOneLine() {
Set<Integer> linkedHashSet1 = new LinkedHashSet<>(Set.of(1, 2, 3));
assertThat(linkedHashSet1).contains(1, 2, 3);
Set<Integer> linkedHashSet2 = new LinkedHashSet<>(List.of(1, 2, 3));
assertThat(linkedHashSet2).containsExactly(1, 2, 3);
}
- Initialize a LinkedHashSet in one line with a double brace should not be used in practice as it can lead to memory leaks by creating too many anonymous classes
@Test
public void initInOneLineWithDoubleBrace() {
Set<Integer> linkedHashSet = new LinkedHashSet<>(){{
add(1);
add(2);
add(3);
}};
assertThat(linkedHashSet).hasSize(3);
}
- Initialize by using add and addAll methods
@Test
public void initWithAddAndAddAll() {
Set<Integer> linkedHashSet1 = new LinkedHashSet<>(Set.of(1, 2, 3));
Set<Integer> linkedHashSet2 = new LinkedHashSet<>();
linkedHashSet2.add(1);
linkedHashSet2.add(1); // duplicated element will be ignored
linkedHashSet2.add(null); // permits null element
linkedHashSet2.addAll(linkedHashSet1);
assertThat(linkedHashSet2).hasSize(4);
}
Iterate a LinkedHashSet
- You can iterate a LinkedHashSet by using either forEach(Consumer), since Java 8, or for-each and other index-loops (while, do-while, for-index)
@Test
public void iterateWithForEachConsumer() {
Set<Integer> linkedHashSet = new LinkedHashSet<>(Set.of(1, 2, 3));
linkedHashSet.forEach(e -> System.out.printf("%d ", e));
}
- Iterator can also be used to iterate a LinkedHashSet
@Test
public void iterateWithIterator() {
Set<Integer> linkedHashSet = new LinkedHashSet<>(Set.of(1, 2, 3));
Iterator<Integer> iterator = linkedHashSet.iterator();
while (iterator.hasNext()) {
System.out.printf("%d ", iterator.next());
}
}
Retrieve and Filter
LinkedHashSet doesn't provide APIs to retrieve its elements directly. You can either use iterator or Stream API, since Java 8, in a linear-time performance
The following example uses Stream API to get the first element by using findFirst() and filter elements by using filter(Predicate)
@Test
public void retrieve() {
Set<Integer> linkedHashSet = new LinkedHashSet<>(List.of(1, 2, 3));
Integer firstElement = linkedHashSet.stream().findFirst().orElse(null);
assertThat(firstElement).isEqualTo(1);
Integer[] elements = linkedHashSet.stream().filter(e -> e >= 2).toArray(Integer[]::new);
assertThat(elements).contains(2, 3);
}
Examine, Add and Remove
- LinkedHashSet provides contains(Object), add(Object) and remove(Object) methods in a constant-time performance to examine if a LinkedHashSet contains the specified element, to add a new element, and remove an existing element from a LinkedHashSet respectively
@Test
public void containsAddRemoveSingleElement() {
Set<Integer> hashSet = new LinkedHashSet<>(Set.of(1, 2, 3));
Boolean contained = hashSet.contains(3);
assertThat(contained).isTrue();
hashSet.add(4);
hashSet.add(4);
hashSet.add(null);
assertThat(hashSet).contains(1, 2, 3, 4, null);
hashSet.remove(2);
assertThat(hashSet).contains(1, 3, 4, null);
}
- You can also do the above operations in bulk with containsAll, addAll, removeAll, Java 8+ removeIf
@Test
public void containsAddRemoveMultipleElements() {
Set<Integer> linkedHashSet = new LinkedHashSet<>(Set.of(1, 2, 3));
Boolean contained = linkedHashSet.containsAll(Set.of(1, 2));
assertThat(contained).isTrue();
linkedHashSet.addAll(Set.of(3, 4, 5));
assertThat(linkedHashSet).contains(1, 2, 3, 4, 5);
linkedHashSet.removeAll(Set.of(1, 2, 6));
assertThat(linkedHashSet).contains(3, 4, 5);
linkedHashSet.removeIf(e -> e >= 4);
assertThat(linkedHashSet).contains(3);
}
Objects comparing in LinkedHashSet
Internally, LinkedHashSet basic operations such as contains, add and remove work based on comparing element objects which depend on their equals and hashCode implementation
In the following example,
linkedHashSet.contains(new Book(1, "a"))should return true but false,linkedHashSet.add(new Book(1, "a"))should not but success andlinkedHashSet.remove(new Book(1, "a"))should success but not , due to lack of equals and hashCode implementation on the custom class
@Test
public void objectsComparingProblem(){
Set<Book> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add(new Book(1, "a"));
Boolean contained = linkedHashSet.contains(new Book(1, "a"));
assertThat(contained).isFalse();
linkedHashSet.add(new Book(1, "a"));
assertThat(linkedHashSet).hasSize(2);
linkedHashSet.remove(new Book(1, "a"));
assertThat(linkedHashSet).hasSize(2);
}
static class Book {
int id;
String title;
Book(int id, String title) {
this.id = id;
this.title = title;
}
int getId() {
return id;
}
String getTitle() {
return title;
}
}
- You can fix the above problem by overriding equals and hashCode as the below example
@Test
public void objectsComparingFixed(){
Set<BookFixed> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add(new BookFixed(1, "a"));
Boolean contained = linkedHashSet.contains(new BookFixed(1, "a"));
assertThat(contained).isTrue();
linkedHashSet.add(new BookFixed(1, "a"));
assertThat(linkedHashSet).hasSize(1);
linkedHashSet.remove(new BookFixed(1, "a"));
assertThat(linkedHashSet).hasSize(0);
}
static class BookFixed {
int id;
String title;
BookFixed(int id, String title) {
this.id = id;
this.title = title;
}
int getId() {
return id;
}
String getTitle() {
return title;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
BookFixed bookFixed = (BookFixed) o;
return id == bookFixed.id &&
Objects.equals(title, bookFixed.title);
}
@Override
public int hashCode() {
return Objects.hash(id, title);
}
}
Sort a LinkedHashSet
Java doesn't have a direct API to sort a LinkedHashSet, you have to convert it to TreeSet or ArrayList
@Test
public void sort() {
Set<Integer> set = new LinkedHashSet<>(Set.of(3, 1, 2));
NavigableSet<Integer> sortedSet = new TreeSet<>(set);
// Asserts that the set contains the given values in order
assertThat(sortedSet).containsExactly(1, 2, 3);
}
Conclusion
In this tutorial, we learned about LinkedHashSet features, class hierarchy and operations. You can find below the full source code