java-collection: How LinkedHashMap internally works in Java?

LinkedHashmap is combination of both LinkedList and HashMap. In other words, LiknedHashMap maintain a linkedList of elements in order of being inserted or being accessed along with storing elements(key and value) in HashMap.

Internal building blocks of LinkedHashMap is similar to HashMap with extra overhead for maintaining a linkedList(or interconnecting all elements in a particular order). LinkedHashMap uses an array of Entry objects (Entry[] table) to store elements and maintain two references(Entry<K,V> before, after;) to form a doubly linkedList. Please note HashMap also uses Entry objects to store key/value then what makes LinkedHashMap Entry class different. We will walk through the sample code from java.util.LinkedHashMap to find differences:

static class Entry extends HashMap.Entry{
Entry before, after;
Entry(int hash, K key, V value, HashMap.Entry next){
super(hash,key,value,next);
}
}

As we can see the visible difference, above Entry class extends HashMap Entry class and add two references for interconnecting elements to be added in map via put method.

super(hash,key,value,next) is used to instantiate HashMap entry objects. HashMap Entry object looks like this:

static class Entry{
final K key;
V value;
Entry next;
final int hash;
}


So, it has an array of Entry objects. Not exactly! It is an array of Entry object chains. A HashMap.Entry object has a next field allowing the Entry objects to be chained as a linked list.

I was wondering how can an index of this array store multiple Entry objects in case of same hash code but different objects.
Because the Entry objects are chained.

How is this different from LinkedHashMap implementation? Its doubly linked list implementation of map but does it maintain an array like the above and how does it store pointers to the next and previous element?

In the LinkedHashMap implementation, the LinkedHashMap.Entry class extends the HashMap.Entry class, by adding before and after fields. These fields are used to assemble the LinkedHashMap.Entry objects into an independent doubly-linked list that records the insertion order. So, in the LinkedHashMap class, the entry objects are in two distinct chains:

1. a singly linked hash chain that is accessed via the main hash array, and
2. a separate doubly linked list of all entries that is kept in entry insertion order.

We have now fair idea how Entry object is created and stored in Entry[] table. Now question arises how does linkedList is maintained using before and after references ?

For maintaining a doubly linkedList, LinkedHashMap uses a reference head of Entry type and initializes it before any entries are inserted into the map.

private transient Entry header;
//Called by superclass constructors and pseudoconstructors before
//any entries are inserted into the map.Initializes the chain.
void init() {
header = new Entry(-1, null, null, null);
header.before = header.after = header;
}

When we do put operation, call is redirected to a method called addEntry and it add elements at end of the linkedlist and maintains references before/after.Similarly, on remove of an element references are reset and pointed to correct Entry object.

One important point that need special mention is that, by default LinkedHashMap maintains linkedList in insertion order or Linkedlist is iterated in same order how elements were inserted. However, it can be changed by using appropriate constructor. The iteration ordering is controlled by accessOrder(a boolean field maintained by LinkedHashMap).

for access-order ----> accessOrder = true
for insertion-order-----> accessOrder =false

We have two constructor below: first constructor is default one and it supports insertion order. However second constructor uses a argument value for setting accessOrder.(Same shown below)

private final boolean accessOrder;

//First default constructor
public LinkedHashMap(){
super();
accessOrder = false;
}

//second constructor :
public LinkedHashMap(int initialCapacity,
float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}