Tags: HashMap , Interview , J2SE , LinkedHashMap , Map

LinkedHashMap implemented using the HashMap. So before we begin to understand How LinkedHashMap works you should first read How HashMap works internally in Java?

We will understand part of code that defers from HashMap and supports LinkedHashMap implementation.

LinkedHasMap#Entry
Entry class in LinkedHashMap extends Node class of HashMap and contains two more variable before and after to hold the before and after references of Entry object.

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

Now when you put(key, value) pair in LinkedHashMap, it creates new node object by calling newNode(..) method. In newNode(..) method linkNodeLast(LinkedHashMap.Entry<K,V> p) method is called which is responsible for pointing head and tail element in LinkedHashMap and also set reference of before and after objects.

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

Following image shows graphical representation of How LinkedHashMap works internally.


Lets understand LinkedHashMap implementation using real Java Program to make everything clear.

Source code (LinkedHashMapExample.java)
Note: Check value of before, after and next to understand example.

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * LinkedHashMap Example.
 * @author javaQuery
 * @date 2019-11-29
 * @Github: https://github.com/javaquery/Examples
 */
public class LinkedHashMapExample {
    public static void main(String[] args) {
        Map<String, String> map = new LinkedHashMap<>();

        /* Check value of before, after and next to understand example */
        map.put("AaAaAa", "JJJ");
        /**
         * Current bucket data visualization
         *
         * bucket-index: 2
         * EntryObject1 [before = null, hash = 123, key = AaAaAa, value = JJJ, next = null, after = null]
         */

        map.put("xyz", "KKK");
        /**
         * Current bucket data visualization
         *
         * bucket-index: 2
         * EntryObject1 [before = null, hash = 123, key = AaAaAa, value = JJJ, next = null, after = EntryObject2]
         *
         * bucket-index: 11
         * EntryObject2 [before = EntryObject1, hash = 456, key = xyz, value = KKK, next = null, after = null]
         */

        /* since hashcode of 'AaAaBB' is same as 'AaAaAa' so it be added at 2nd index in bucket */
        map.put("AaAaBB", "LLL");
        /**
         * Current bucket data visualization
         *
         * bucket-index: 2
         * [
         *  EntryObject1 [before = null, hash = 123, key = AaAaAa, value = JJJ, next = EntryObject3, after = EntryObject2]
         *  EntryObject3 [before = EntryObject2, hash = 123, key = AaAaBB, value = LLL, next = null, after = null]
         * ]
         *
         * bucket-index: 11
         * EntryObject2 [before = EntryObject1, hash = 456, key = xyz, value = KKK, next = null, after = EntryObject3]
         */
    }
}

Above program can be graphically represented as follows.


References
How HashMap works internally in Java?
Popular Map interview questions in Java

Tags: HashMap , Interview , J2SE , LinkedHashMap , Map