Java LinkedHashMap and Its’ Difference From HashMap

In this blog post we’ll cover what is Java LinkedHashMap and when to use it. Also, we’ll talk about what is the difference between the LinkedHashMap and HashMap in Java.

It would be better if you already know what a HashMap is before continuing to read this blog post.

What is Java LinkedHashMap?

Java LinkedHashMap is an ordered version of HashMap. Its’ keys remain in the same order as they were inserted into the map. This is possible because LinkedHashMap takes advantage of doubly linked list under the hood by keeping references on the previous and next entry. As LinkedHashMap class extends HashMap, most of their functionality is the same. You can see the full list of available methods in its’ documentation and some example code about HashMap here.

When creating a LinkedHashMap in Java its’ initial capacity is 16 and the load factor is 0.75. Following code is taken from the LinkedHashMap class:

 /**
 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
 * with the default initial capacity (16) and load factor (0.75).
 */
public LinkedHashMap() {
    super();
    accessOrder = false;
}

If you want to, you can also override the load factor and initial capacity by using another constructor:

/**
    * Constructs an empty <tt>LinkedHashMap</tt> instance with the
    * specified initial capacity, load factor and ordering mode.
    *
    * @param  initialCapacity the initial capacity
    * @param  loadFactor      the load factor
    * @param  accessOrder     the ordering mode - <tt>true</tt> for
    *         access-order, <tt>false</tt> for insertion-order
    * @throws IllegalArgumentException if the initial capacity is negative
    *         or the load factor is nonpositive
    */
   public LinkedHashMap(int initialCapacity,
                        float loadFactor,
                        boolean accessOrder) {
       super(initialCapacity, loadFactor);
       this.accessOrder = accessOrder;
   }

To point out, LinkedHashMap is not synchronized. To achieve a thread safe map you can wrap it with Collections.synchronizedMap method:

Map<Integer, String> map = 
        Collections.synchronizedMap(new LinkedHashMap<>());

LinkedHashMap has been available since JDK 1.4.

Access ordered LinkedHashMap

You might wonder what the accessOrder parameter is you saw in the LinkedHashMap constructor definition. This is another feature of LinkedHashMap that differs from the HashMap. To put it simply, it lets you define a different order for the entries in the map – the order how entries are accessed in the map. When you set accessOrder to true the entries in the map will be ordered from the least-recently accessed to most-recently accessed. This sort of a LinkedHashMap fits great for building LRU (least recently used) caches. We access entries in a map by using methods: put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent and also merge methods.

Next, lets’ take a look at an example to make it more clear what access order is. Note how we set the initial capacity to 16, load factor to 0.75 and accessOrder to true.

// Create new map and set accessOrder to true
LinkedHashMap<Integer, String> numbers = 
        new LinkedHashMap<>(16, 0.75f, true);

// Add keys and values to the map
numbers.put(0, "zero");
numbers.put(1, "one");
numbers.put(2, "two");
numbers.put(3, "three");


// Display the keys
System.out.println("Before: " + numbers.keySet());


// Retrieve 0 from the map
numbers.get(0);

// Display the keys again
System.out.println("After: " + numbers.keySet());

Output:

Before: [0, 1, 2, 3]
After: [1, 2, 3, 0]

As you can see from the example, in the beginning, the keys are in the same order as they were inserted into the map. After we access the key 0 in the map, it moves to the last position. This is how a LinkedHashMap with an access order behaves like. Every time you access an entry, it moves to the last position in the map.

Limiting the maximum size of a LinkedHashMap

Another feature of LinkedHashMap is the possibility to set a maximum size to it. In other words, we can limit how many entries there can be in a map. Luckily it is fairly easy to implement. All we need to do is to override the removeEldestEntry method. So, every time we add an entry to the map and it already holds the maximum number of elements, it removes the “oldest” entry and inserts the new one to the map. For example you can set the maximum map size to 4 and the map will always keep 4 entries in the map.

Now lets’ see how to implement such a feature:

final int maxEntries = 4;

Map<Integer, String> numbers = new LinkedHashMap<Integer, String>(maxEntries) {

    // Overriding the method to set how many entries can be in the map
    protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
        return size() > maxEntries;
    }
};

// Add keys and values to the map
numbers.put(0, "zero");
numbers.put(1, "one");
numbers.put(2, "two");
numbers.put(3, "three");

// Display the keys
System.out.println("Before: " + numbers.keySet());

// Add one more entry to the map
numbers.put(4, "four");

// Display the keys again
System.out.println("After: " + numbers.keySet());

Output:

Before: [0, 1, 2, 3]
After: [1, 2, 3, 4]

In the above example we set the maximum number of entries to 4 and override the removeEldestEntry method for it to work. As you can see, after we added number 4 to the map, number 0 got removed to make room for the new entry. Number 0 was the “oldest” entry in the map.

Difference between LinkedHashMap and HashMap

LinkedHashMap and HashMap are mostly the same:

• They are not synchronized.
• Default initial capacity is 16 and default load factor 0.75.
• They accept null key and null values.
• They don’t accept duplicate keys.
• Both implement hash table data structure.

LinkedHashMap and HashMap are different in the following:

• LinkedHashMap preserves insertion order of its entries. HashMap doesn’t guarantee the order of its’ entries.
• LinkedHashMap requires more memory to maintain the references.
• LinkedHashMap is using doubly linked list to enhance its’ iteration capabilities by keeping a reference on the previous and next entries. This makes it slightly faster when iterating over the map. Their time performance for iteration is O(n). But for LinkedHashMap n is the number of entries in the map. For HashMap n is the number of entires plus its’ capacity.
• Adding, removing and searching have the time complexity O(1) but for LinkedHashMap it might be slightly worse. This is due to the fact that it needs to maintain the references on the previous and next entries.

When to use Java LinkedHashMap?

You can use LinkedHashMap when you need a map that keeps the insertion or access order of its’ entries. For example to implement a LRU cache.

Otherwise, you can go for a HashMap when the order really doesn’t matter. Or, when you need the elements to be sorted in some way, pick a TreeMap.