#Collections: How LinkedHashMap works internally in Java?

ALSO CHECK: Java Collections Interview Questions and Answers

Java LinkedHashMap class is Hashtable and Linked list implementation of the Map interface. LinkedHashMap is like HashMap with an additional feature of maintaining an order of elements inserted into it.



HashMap provided the advantage of quick insertion, search, and deletion but it does not track and order the insertion which the LinkedHashMap provides where the elements can be accessed in their insertion order.

• Java LinkedHashMap contains values based on the key.
• Java LinkedHashMap contains unique elements.
• Java LinkedHashMap may have one null key and multiple null values.
• Java LinkedHashMap is non synchronized.
• Java LinkedHashMap maintains insertion order.
• The initial default capacity of Java HashMap class is 16 with a load factor of 0.75.

How insertion order is maintained in LinkedHashMap?

HashMap does not maintain the order of insertion, because while iterating over the Hashmap starting from the 0th index to the nth index of the array table, at every index we are iterating over the linked list at that index.

To maintain the order of insertion we need 2 more pointers at every Node(besides the next pointer required for LinkedList functionality). Apart from this linkedList, another doubly-linked-list is also maintained in the hashmap which is used to handle the insertion order.



We have a total of 6 fields now:-

• before: points to the node inserted before this node
• after: points to the node inserted after this node
• key: key as provided
• value: value as provided
• next: points to the next node in the same bucket of array table(like in HashMap)
• hash: hashcode to calculate the index of this node, and check for equality.

Also, there are head and tail fields in the LinkedHashMap, which point to the head and tail of our doublyLinkedList.

ALSO CHECK:  Implement Least Recently Used Cache using LinkedHashMap

Whenever we put(key, value) pair in LinkedHashMap, it creates a new node object by calling newNode() method. In newNode() method linkNodeLast(LinkedHashMap.Entry p) method is called which is responsible for pointing the head and tail element in LinkedHashMap and also setting reference of before and after objects.



-K Himaanshu Shuklaa..