Java by examples

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

Question: Why Map interface does not extends Collection interface?
Answer: Map is (key, value) pair not a collection of one type of values so it does not extends Collection interface. Collection interface accept single object via add(E e) but Map interface requires key, value pair in method put(K key, V value)

Question: Does Map accept `null` as key?
Answer: HashMap and LinkedHashMap accepts null key but TreeMap will throws NullPointerException. HashMap stores null key at 0th index in bucket.

Question: Does Map accept `null` values?
Answer: You can have n null values.

Question: What is the initial capacity of HashMap?
Answer: 16. DEFAULT_INITIAL_CAPACITY = (1 << 4)

Question: What is the maximum capacity of HashMap?
Answer: 1073741824. MAXIMUM_CAPACITY = ( 1 << 30)

Question: Does HashMap maintain insertion order?
Answer: No

Question: Is HashMap synchronized?
Question: Is HashMap thread-safe?
Answer: No

Question: How to synchronize Map?
Answer: Using Collections.synchronizedMap(map), best practice Map m = Collections.synchronizedMap(new HashMap(...));

Question: How to avoid concurrent modification exception?
Answer: Synchronize Map using Map m = Collections.synchronizedMap(new HashMap(...)); or Map n = new ConcurrentHashMap();

Question: How HashMap works internally in Java?
Answer: To understand How HashMap works internally read the article https://www.javaquery.com/2019/11/how-hashmap-works-internally-in-java.html

Question: What happens when you put same key again in HashMap?
Answer: When you put(existing-key, value) in HashMap, it will replace old value with new value. And returns old value.

Map<String, String&gt; map = new HashMap<&gt;();
map.put("a", "x");
String oldValue = map.put("a", "y");
System.out.println(oldValue);
//output: x

Question: Can we store duplicate key in HashMap?
Answer: No

Question: Can we store duplicate value in HashMap?
Answer: Yes.

Question: What is Hash code/key collision?
Answer: When two same or different hash code of key generates same index of bucket location by performing bitwise AND is called hash code/key collision. In this situation HashMap forms linked list at given bucket location (index).

For example "AaAaAa".hashCode() and "AaAaBB".hashCode() generates same hash code.

Question: How HashMap handles Hash code/key collision?
Question: What will happens if two objects have same hash code?
Answer: It forms linked list at bucket location.

Question: Why String, Integer and other wrapper classes are good choice for HashMap key?
Answer: String, Integer and other wrapper classes are immutable so its best choice to use it as key. Why String is immutable in Java?

Question: Can we use mutable key in HashMap?
Answer: Yes, You can use mutable key but its not good choice because it'll fail to retrieve correct value in get(key).

Question: Can we use our own custom object/class as key in HashMap?
Answer: Yes, You can use your custom object as key in HashMap but its necessary to consider immutability of that object and also implementing hashCode() and equals() method in your class.

Question: How HashMap is improved in Java 8?
Answer: Prior to Java 8, HashMap forms linked list in case of hash collision. Now from Java 8 when hash collision occurs and it hits following threshold TREEIFY_THRESHOLD = 8 and MIN_TREEIFY_CAPACITY = 64 then it uses TreeNode to store Entry object to improve HashMap get performance.
Why HashMap resize when it hits TREEIFY_THRESHOLD value which is not required?

Question: Which tree stucture is used in Java 8 to improve performance of HashMap?
Answer: red-black tree structure is used to improce performance of HashMap.

Question: How LinkedHashMap works internally in Java?
Answer: To understand How LinkedHashMap works internally read the article https://www.javaquery.com/2019/12/how-linkedhashmap-works-internally-in.html