HelloKoding

Practical coding guides

LinkedHashSet in Java

Java LinkedHashSet is a hash table and doubly linked list data structure implementation of the Set interface, a part of the Java Collections Framework

Java LinkedHashSet Hierarchy

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

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 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);
}

Conclusion

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

LinkedHashSetTest.java

package com.hellokoding.java.collections;

import org.junit.Test;

import java.util.*;

import static org.assertj.core.api.Assertions.assertThat;

public class LinkedHashSetTest {
    @Test
    public void declare() {
        Set<Integer> linkedHashSet1 = new LinkedHashSet<>();
        assertThat(linkedHashSet1).isInstanceOf(LinkedHashSet.class);

        LinkedHashSet<Integer> linkedHashSet2 = new LinkedHashSet<>();
    }

    @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);
    }

    @Test
    public void initInOneLineWithDoubleBrace() {
        Set<Integer> linkedHashSet = new LinkedHashSet<>(){{
            add(1);
            add(2);
            add(3);
        }};

        assertThat(linkedHashSet).hasSize(3);
    }

    @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 is ignored
        linkedHashSet2.add(null); // permits null element

        linkedHashSet2.addAll(linkedHashSet1);

        assertThat(linkedHashSet2).hasSize(4);
    }

    @Test
    public void iterateWithForEachConsumer() {
        Set<Integer> linkedHashSet = new LinkedHashSet<>(Set.of(1, 2, 3));
        linkedHashSet.forEach(e -> System.out.printf("%d ", e));
    }

    @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());
        }
    }

    @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);
    }

    @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);
    }

    @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);
    }

    @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;
        }
    }

    @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);
        }
    }

    @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);
    }
}
Follow HelloKoding