LinkedHashMap with Example

LinkedHashMap is a sub-class of Java HashMap with capabilities to keep keys ordered either in insertion order or access order. LinkedHashMap is the dictionary/table implementation of choice whenever you want best performance and predictable key ordering at the same time. It achieves this magical feat by maintaining a doubly linked list apart from the usual implementation of HashMap. The doubly-linked list is used to record the insertion-order or the order of access of entries. Performance-wise this map is slightly worse than HashMap, although asymptotic complexity of all major operations is the same for both data structures. Choose LinkedHashMap over HashMap if and only if your program depends on relative predictable ordering of keys but you don’t want to pay the price of keeping all keys sorted.

Constructors of LinkedHashMap

The constructors follow the Java Map constructors convention of having no-args and copy constructors. In addition, there are three other constructors to specify load factor, initial capacity and ordering of elements. If you have not already read about the constructors of HashMap, now would be a good time to do so.

1. Default, no-args constructor -> takes no argument, allows you to create a new Map using default values of 16 for initial capacity and 0.75f for load factor.
2. LinkedHashMap(Map<? extends K,? extends V> m) -> Copy constructor.
3.  LinkedHashMap(int initialCapacity) -> overrides the default initial capacity value
4. LinkedHashMap(int initialCapacity, float loadFactor)
5. LinkedHashMap(int initialCapacity, float loadFactor, boolean order) -> same as the previous constructor. The additional boolean flag specifies whether we need to insertion-order or access-order. A value false signifies insertion-order storage and true implies access-order.
   Access order implies storing keys by their last access times. The most recently accessed key moves to the back of the doubly linked list. This can be used to implement a ‘fair’ cache where least recently used entries move towards the beginning of the linked list.
   Insertion order on the other hand implies arrival order and is a static order in the sense that it does not vary with usage patterns.

Internal Implementation of LinkedHashMap

To understand the inner workings of LinkedHashMap, you should understand inner workings of HashMap. Since LinkedHashMap is a sub-class of HashMap, every thing described in the lesson on implementing HashMap applies.

The only twist in the tale is presence of a doubly linked list to maintain a relative order. This order may either be insertion order or access order.

The keys are always read/iterated from the doubly linked list and their value is gathered from the HashMap. This gives you a predictable iteration order and nearly same performance as that of HashMap.

Note that unlike TreeMap, the keys are not sorted. They are only kept in a fixed order.

Important Methods of LinkedHashMap

Apart from all the methods that are expected of a Java Map, there is one other method that demand some perusal –

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) -> checks if the method should remove the eldest entry upon put or putAll.

Salient Features of LinkedHashMap

Before we move on demonstrate the usage with an example, let’s recap the important points. LinkedHashMap

1. Is a concrete implementation of Java Map. Is a sub-class of HashMap.
2. Has time complexity of the add, remove and contains operations is constant time i.e O(1). This is optimal and it is impossible to achieve a better asymptotic complexity.
3. Is designed to be used in single-threaded environments.
4. Can be used in multi-threaded environments by using locking constructs such as synchronized keyword.
5. Has iterators that are fail-fast.
6. Maintains a predictable order of the keys. This spares the clients from chaotic and totally unpredictable key ordering of HashMap.
7. Uses a doubly-linked list internally to impose either insertion order or access order on the keys.

LinkedHashMap Example

In this toned down example of a real life situation, we demonstrate how to print/iterate a map in a predictable order, immaterial of the iterators.

The task in this example is to model a company and store a mapping of job designations to their respective job descriptions. We want to always iterate the jobs in the order of seniority. For example, we should always print the all-powerful Manager before the lowly-employ developer.

The code below demonstrates this modeling –

The output of the above code is –

Having looked at the constructors, methods and an example of LinkedHashMap, we will next demonstrate its usage as a LRU cache.