HelloKoding

Practical coding guides

LinkedHashMap in Java

Java LinkedHashMap is a hash table (key-value pairs, dictionary) and doubly linked list data structure implementation of the Map interface, a part of the Java Collections framework

Map implementations in Java Collections Framework

LinkedHashMap has the following features

  • Provides insertion-ordered iteration
  • No duplicate keys. Permits one null key and multiple null values
  • Offers constant time performance for basic operations such as get, containsKey, containsValue, put, remove
  • Keys and values are compared based on theirs equals and hashCode implementation
  • LinkedHashMap is not thread-safe as it is an unsynchronized implementation. In multi-threading environment with at least one thread modifies the map, it must be synchronized externally
  • Internally, LinkedHashMap uses a hash table data structure to store and retrieve its elements, uses a doubly linked list data structure to maintain the insertion order

Let’s walk through this tutorial to explore them in more details

LinkedHashMap vs HashMap and TreeMap

LinkedHashMap provides insertion-ordered iteration and runs nearly as fast as HashMap

HashMap has no ordering guarantees and run faster than TreeMap (constant-time vs log-time for most operations)

TreeMap provides value-ordered iteration. TreeMap can be used to sort a HashMap or LinkedHashMap

Declare a LinkedHashMap

As a result of the class hierarchy, you can declare a LinkedHashMap with the following ways

@Test
public void declare() {
    Map<String, Integer> linkedHashMap1 = new LinkedHashMap<>();
    assertThat(linkedHashMap1).isInstanceOf(LinkedHashMap.class);

    LinkedHashMap<String, Integer> linkedHashMap2 = new LinkedHashMap<>();
}

Create and Initialize

  • Provide either Map.of or Map.ofEntries factory method, since Java 9, to the LinkedHashMap(Map) constructor to create and init a LinkedHashMap in one line at the creation time
@Test
public void initInOneLineWithFactoryMethods() {
    // create and initialize a LinkedHashMap from Java 9+ Map.of
    Map<String, Integer> linkedHashMap1 = new LinkedHashMap<>((Map.of("k1", 1, "k3", 2, "k2", 3)));
    assertThat(linkedHashMap1).hasSize(3);

    // create and initialize a LinkedHashMap from Java 9+ Map.ofEntries
    Map<String, Integer> linkedHashMap2 = new LinkedHashMap<>(Map.ofEntries(Map.entry("k4", 4), Map.entry("k5", 5)));
    assertThat(linkedHashMap2).hasSize(2);
}
  • You can also initialize a LinkedHashMap after the creation time by using put, Java 8+ putIfAbsent, putAll
@Test
public void initializeWithPutIfAbsent() {
    // Create a new LinkedHashMap
    Map<String, Integer> linkedHashMap = new LinkedHashMap<>();

    // Add elements to LinkedHashMap
    linkedHashMap.putIfAbsent("k1", 1);
    linkedHashMap.putIfAbsent("k2", 2);
    linkedHashMap.putIfAbsent("k3", 3);

    // Can add null key and value
    linkedHashMap.putIfAbsent(null, 4);
    linkedHashMap.putIfAbsent("k4", null);

    // Duplicate key will be ignored
    linkedHashMap.putIfAbsent("k1", 10);
    assertThat(linkedHashMap).hasSize(5);

    // The output ordering is predictable as LinkedHashMap is reserved the insertion order
    System.out.println(linkedHashMap);
}

Iterate over a LinkedHashMap

  • You can iterate over LinkedHashMap key-value pairs by using Java 8+ forEach(BiConsumer)
@Test
public void iterateOverKeyValuePairs() {
    Map<String, Integer> linkedHashMap = new LinkedHashMap<>(Map.of("k1", 1, "k2", 2));
    linkedHashMap.forEach((k, v) -> System.out.printf("%s=%d ", k, v));
}
  • Iterate over LinkedHashMap entrySet(), keySet() or values() with Java 8+ forEach(Consumer)
@Test
public void iterateOverEntrySetKeySetAndValues() {
    Map<String, Integer> linkedHashMap = new LinkedHashMap<>(Map.of("k1", 1, "k2", 2));
    linkedHashMap.entrySet().forEach(e -> System.out.printf("%s ", e));
    linkedHashMap.keySet().forEach(k -> System.out.printf("%s ", k));
    linkedHashMap.values().forEach(v -> System.out.printf("%s ", v));
}

Retrieve and Filter

  • Use entrySet(), keySet(), values() to get the set of key-value mapping entries, set of keys and collection of values respectively
@Test
public void retrieve() {
    Map<String, Integer> linkedHashMap = new LinkedHashMap<>(Map.of("k1", 1, "k2", 2));

    Set<Map.Entry<String, Integer>> entrySet = linkedHashMap.entrySet();
    assertThat(entrySet).contains(Map.entry("k1", 1), Map.entry("k2", 2));

    Set<String> keySet = linkedHashMap.keySet();
    assertThat(keySet).contains("k1", "k2");

    Collection<Integer> values = linkedHashMap.values();
    assertThat(values).contains(1, 2);
}
  • Get value by the specified key with get(key)
@Test
public void getValueByKey() {
    Map<String, Integer> linkedHashMap = new LinkedHashMap<>(Map.of("k1", 1, "k2", 2));
    int value = linkedHashMap.get("k1");

    assertThat(value).isEqualTo(1);
}
  • Filter LinkedHashMap keys or values by using Java 8+ Stream API
@Test
public void filter() {
    Map<String, Integer> linkedHashMap = new LinkedHashMap<>(Map.of("k1", 1, "k2", 2));
    Integer[] arr = linkedHashMap.values().stream().filter(v -> v > 1).toArray(Integer[]::new);
    assertThat(arr).contains(2);
}

Examine, Add, Update and Remove

LinkedHashMap provides containsKey(key), containsValue(value), put(key, value), replace(key, value), and remove(key) methods to examine if a LinkedHashMap contains the specified key or value, to add a new key-value pair, update a value by key, remove an entry by key respectively

@Test
public void containsPutReplaceRemove() {
    Map<String, Integer> linkedHashMap = new LinkedHashMap<>(Map.of("k1", 1, "k2", 2));

    boolean containedKey = linkedHashMap.containsKey("k1");
    assertThat(containedKey).isTrue();

    boolean containedValue = linkedHashMap.containsValue(2);
    assertThat(containedValue).isTrue();

    linkedHashMap.put("k3", 3);
    assertThat(linkedHashMap).hasSize(3);

    linkedHashMap.replace("k1", 10);
    assertThat(linkedHashMap).contains(Map.entry("k1", 10), Map.entry("k2", 2), Map.entry("k3", 3));

    linkedHashMap.remove("k3");
    assertThat(linkedHashMap).contains(Map.entry("k1", 10), Map.entry("k2", 2));
}

Objects comparing in LinkedHashMap

  • Internally, LinkedHashMap basic operations such as containsKey, containsValue, put, putIfAbsent, replace and remove work based on comparing element objects which depend on their equals and hashCode implementation

    In the following example, the expected results don’t happen due to lack of equals and hashCode implementation on the user defined objects

    • linkedHashMap.containsKey(new Category(1, "c1")) and linkedHashMap.containsValue(new Book(1, "a")) should return true but false
    • linkedHashMap.put(new Category(1, "c1"), new Book(1, "a")) should not but success
    • linkedHashMap.replace(new Category(1, "c1"), new Book(2, "a")) and linkedHashMap.remove(new Category(1, "c1")) should success but not
@Test
public void objectsComparingProblem(){
    Map<Category, Book> linkedHashMap = new LinkedHashMap<>();

    linkedHashMap.put(new Category(1, "c1"), new Book(1, "b1"));

    boolean containedKey = linkedHashMap.containsKey(new Category(1, "c1"));
    assertThat(containedKey).isFalse();

    boolean containedValue = linkedHashMap.containsValue(new Book(1, "b1"));
    assertThat(containedValue).isFalse();

    linkedHashMap.put(new Category(1, "c1"), new Book(1, "b1"));
    assertThat(linkedHashMap).hasSize(2);

    Book previousValue = linkedHashMap.replace(new Category(1, "c1"), new Book(2, "b1"));
    assertThat(previousValue).isNull();

    linkedHashMap.remove(new Category(1, "c1"));
    assertThat(linkedHashMap).hasSize(2);
}

static class Category {
    int id;
    String name;

    Category(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

static class Book {
    int id;
    String title;

    Book(int id, String title) {
        this.id = id;
        this.title = title;
    }
}
  • You can fix the above problem by overriding equals and hashCode as the below example
@Test
public void objectsComparingFixed(){
    Map<CategoryFixed, BookFixed> linkedHashMap = new LinkedHashMap<>();

    linkedHashMap.put(new CategoryFixed(1, "c1"), new BookFixed(1, "b1"));

    boolean containedKey = linkedHashMap.containsKey(new CategoryFixed(1, "c1"));
    assertThat(containedKey).isTrue();

    boolean containedValue = linkedHashMap.containsValue(new BookFixed(1, "b1"));
    assertThat(containedValue).isTrue();

    linkedHashMap.put(new CategoryFixed(1, "c1"), new BookFixed(1, "b1"));
    assertThat(linkedHashMap).hasSize(1);

    BookFixed previousValue = linkedHashMap.replace(new CategoryFixed(1, "c1"), new BookFixed(2, "b1"));
    assertThat(previousValue).isNotNull();

    linkedHashMap.remove(new CategoryFixed(1, "c1"));
    assertThat(linkedHashMap).hasSize(0);
}

static class CategoryFixed {
    int id;
    String name;

    CategoryFixed(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        CategoryFixed that = (CategoryFixed) o;
        return id == that.id &&
                Objects.equals(name, that.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}

static class BookFixed {
    int id;
    String title;

    BookFixed(int id, String title) {
        this.id = id;
        this.title = 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 LinkedHashMap

Java doesn’t have a direct API to sort a LinkedHashMap. However, you can do it via TreeMap, TreeSet, and ArrayList in conjunction with Comparable and Comparator

The following example uses comparingByKey(Comparator) and comparingByValue(Comparator) static methods of Map.Entry to sort an ArrayList by keys and by values respectively. That ArrayList is created and initialized from entrySet() of a LinkedHashMap

@Test
public void sortByKeysAndByValues_WithArrayListAndComparator() {
    Map.Entry<String, Integer> e1 = Map.entry("k1", 1);
    Map.Entry<String, Integer> e2 = Map.entry("k2", 20);
    Map.Entry<String, Integer> e3 = Map.entry("k3", 3);

    Map<String, Integer> linkedHashMap = new LinkedHashMap<>(Map.ofEntries(e3, e1, e2));

    List<Map.Entry<String, Integer>> arrayList1 = new ArrayList<>(linkedHashMap.entrySet());
    arrayList1.sort(comparingByKey(Comparator.naturalOrder()));
    assertThat(arrayList1).containsExactly(e1, e2, e3);

    List<Map.Entry<String, Integer>> arrayList2 = new ArrayList<>(linkedHashMap.entrySet());
    arrayList2.sort(comparingByValue(Comparator.reverseOrder()));
    assertThat(arrayList2).containsExactly(e2, e3, e1);
}

Conclusion

In this tutorial, we had a quick overview of LinkedHashMap hierarchy, features, and operations. You can find below the full example source code

LinkedHashMapTest.java

package com.hellokoding.java.collections;

import org.junit.Test;

import java.util.*;

import static java.util.Map.Entry.comparingByKey;
import static java.util.Map.Entry.comparingByValue;
import static org.assertj.core.api.Assertions.assertThat;

public class LinkedHashMapTest {
    @Test
    public void declare() {
        Map<String, Integer> linkedHashMap1 = new LinkedHashMap<>();
        assertThat(linkedHashMap1).isInstanceOf(LinkedHashMap.class);

        LinkedHashMap<String, Integer> linkedHashMap2 = new LinkedHashMap<>();
    }

    @Test
    public void initInOneLineWithFactoryMethods() {
        // create and initialize a LinkedHashMap from Java 9+ Map.of
        Map<String, Integer> linkedHashMap1 = new LinkedHashMap<>((Map.of("k1", 1, "k3", 2, "k2", 3)));
        assertThat(linkedHashMap1).hasSize(3);

        // create and initialize a LinkedHashMap from Java 9+ Map.ofEntries
        Map<String, Integer> linkedHashMap2 = new LinkedHashMap<>(Map.ofEntries(Map.entry("k4", 4), Map.entry("k5", 5)));
        assertThat(linkedHashMap2).hasSize(2);
    }

    @Test
    public void initializeWithPutIfAbsent() {
        // Create a new LinkedHashMap
        Map<String, Integer> linkedHashMap = new LinkedHashMap<>();

        // Add elements to LinkedHashMap
        linkedHashMap.putIfAbsent("k1", 1);
        linkedHashMap.putIfAbsent("k2", 2);
        linkedHashMap.putIfAbsent("k3", 3);

        // Can add null key and value
        linkedHashMap.putIfAbsent(null, 4);
        linkedHashMap.putIfAbsent("k4", null);

        // Duplicate key will be ignored
        linkedHashMap.putIfAbsent("k1", 10);
        assertThat(linkedHashMap).hasSize(5);

        // The output ordering is predictable as LinkedHashMap is reserved the insertion order
        System.out.println(linkedHashMap);
    }

    @Test
    public void iterateOverKeyValuePairs() {
        Map<String, Integer> linkedHashMap = new LinkedHashMap<>(Map.of("k1", 1, "k2", 2));
        linkedHashMap.forEach((k, v) -> System.out.printf("%s=%d ", k, v));
    }

    @Test
    public void iterateOverEntrySetKeySetAndValues() {
        Map<String, Integer> linkedHashMap = new LinkedHashMap<>(Map.of("k1", 1, "k2", 2));
        linkedHashMap.entrySet().forEach(e -> System.out.printf("%s ", e));
        linkedHashMap.keySet().forEach(k -> System.out.printf("%s ", k));
        linkedHashMap.values().forEach(v -> System.out.printf("%s ", v));
    }

    @Test
    public void retrieve() {
        Map<String, Integer> linkedHashMap = new LinkedHashMap<>(Map.of("k1", 1, "k2", 2));

        Set<Map.Entry<String, Integer>> entrySet = linkedHashMap.entrySet();
        assertThat(entrySet).contains(Map.entry("k1", 1), Map.entry("k2", 2));

        Set<String> keySet = linkedHashMap.keySet();
        assertThat(keySet).contains("k1", "k2");

        Collection<Integer> values = linkedHashMap.values();
        assertThat(values).contains(1, 2);
    }

    @Test
    public void getValueByKey() {
        Map<String, Integer> linkedHashMap = new LinkedHashMap<>(Map.of("k1", 1, "k2", 2));
        int value = linkedHashMap.get("k1");

        assertThat(value).isEqualTo(1);
    }

    @Test
    public void filter() {
        Map<String, Integer> linkedHashMap = new LinkedHashMap<>(Map.of("k1", 1, "k2", 2));
        Integer[] arr = linkedHashMap.values().stream().filter(v -> v > 1).toArray(Integer[]::new);
        assertThat(arr).contains(2);
    }

    @Test
    public void containsPutReplaceRemove() {
        Map<String, Integer> linkedHashMap = new LinkedHashMap<>(Map.of("k1", 1, "k2", 2));

        boolean containedKey = linkedHashMap.containsKey("k1");
        assertThat(containedKey).isTrue();

        boolean containedValue = linkedHashMap.containsValue(2);
        assertThat(containedValue).isTrue();

        linkedHashMap.put("k3", 3);
        assertThat(linkedHashMap).hasSize(3);

        linkedHashMap.replace("k1", 10);
        assertThat(linkedHashMap).contains(Map.entry("k1", 10), Map.entry("k2", 2), Map.entry("k3", 3));

        linkedHashMap.remove("k3");
        assertThat(linkedHashMap).contains(Map.entry("k1", 10), Map.entry("k2", 2));
    }

    @Test
    public void objectsComparingProblem(){
        Map<Category, Book> linkedHashMap = new LinkedHashMap<>();

        linkedHashMap.put(new Category(1, "c1"), new Book(1, "b1"));

        boolean containedKey = linkedHashMap.containsKey(new Category(1, "c1"));
        assertThat(containedKey).isFalse();

        boolean containedValue = linkedHashMap.containsValue(new Book(1, "b1"));
        assertThat(containedValue).isFalse();

        linkedHashMap.put(new Category(1, "c1"), new Book(1, "b1"));
        assertThat(linkedHashMap).hasSize(2);

        Book previousValue = linkedHashMap.replace(new Category(1, "c1"), new Book(2, "b1"));
        assertThat(previousValue).isNull();

        linkedHashMap.remove(new Category(1, "c1"));
        assertThat(linkedHashMap).hasSize(2);
    }

    static class Category {
        int id;
        String name;

        Category(int id, String name) {
            this.id = id;
            this.name = name;
        }
    }

    static class Book {
        int id;
        String title;

        Book(int id, String title) {
            this.id = id;
            this.title = title;
        }
    }

    @Test
    public void objectsComparingFixed(){
        Map<CategoryFixed, BookFixed> linkedHashMap = new LinkedHashMap<>();

        linkedHashMap.put(new CategoryFixed(1, "c1"), new BookFixed(1, "b1"));

        boolean containedKey = linkedHashMap.containsKey(new CategoryFixed(1, "c1"));
        assertThat(containedKey).isTrue();

        boolean containedValue = linkedHashMap.containsValue(new BookFixed(1, "b1"));
        assertThat(containedValue).isTrue();

        linkedHashMap.put(new CategoryFixed(1, "c1"), new BookFixed(1, "b1"));
        assertThat(linkedHashMap).hasSize(1);

        BookFixed previousValue = linkedHashMap.replace(new CategoryFixed(1, "c1"), new BookFixed(2, "b1"));
        assertThat(previousValue).isNotNull();

        linkedHashMap.remove(new CategoryFixed(1, "c1"));
        assertThat(linkedHashMap).hasSize(0);
    }

    static class CategoryFixed {
        int id;
        String name;

        CategoryFixed(int id, String name) {
            this.id = id;
            this.name = name;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            CategoryFixed that = (CategoryFixed) o;
            return id == that.id &&
                    Objects.equals(name, that.name);
        }

        @Override
        public int hashCode() {
            return Objects.hash(id, name);
        }
    }

    static class BookFixed {
        int id;
        String title;

        BookFixed(int id, String title) {
            this.id = id;
            this.title = 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 sortByKeysAndByValues_WithArrayListAndComparator() {
        Map.Entry<String, Integer> e1 = Map.entry("k1", 1);
        Map.Entry<String, Integer> e2 = Map.entry("k2", 20);
        Map.Entry<String, Integer> e3 = Map.entry("k3", 3);

        Map<String, Integer> linkedHashMap = new LinkedHashMap<>(Map.ofEntries(e3, e1, e2));

        List<Map.Entry<String, Integer>> arrayList1 = new ArrayList<>(linkedHashMap.entrySet());
        arrayList1.sort(comparingByKey(Comparator.naturalOrder()));
        assertThat(arrayList1).containsExactly(e1, e2, e3);

        List<Map.Entry<String, Integer>> arrayList2 = new ArrayList<>(linkedHashMap.entrySet());
        arrayList2.sort(comparingByValue(Comparator.reverseOrder()));
        assertThat(arrayList2).containsExactly(e2, e3, e1);
    }
}
Follow HelloKoding