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. Null element is permitted

  • Elements are compared based on theirs equals and hashCode

  • Unsynchronized implementation. In multi-threading environment with at least one thread modifies the list, it must be synchronized externally

Lets 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 run 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 from 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 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 and linkedHashSet.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);
}

Learn more

Conclusion

In this tutorial, we learned about LinkedHashSet features, class hierarchy and operations. You can find below the full source code