Unveiling HashMap & LinkedHashMap: Internals, Resizing, and LRU Implementation

1. HashMap Overview

HashMap is the most commonly used implementation of the Map interface in the Java Collection Framework. It stores entries as Node objects that contain a hash value, key, value, and a reference to the next node.

Key methods include four constructors (default, with capacity, with capacity and load factor, and copy from another map) and the static method tableSizeFor(int cap) which returns the smallest power of two greater than or equal to the requested capacity.

1.1 HashMap Node Structure

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

1.2 Insertion (put) Logic

The public put(K key, V value) method delegates to putVal. It computes the hash, finds the bucket index with (n‑1) & hash, and then:

If the bucket is empty, a new node is inserted.

If a node with the same key exists, its value is replaced.

If a collision occurs, the chain is traversed; when the chain length exceeds TREEIFY_THRESHOLD (8) and the table size is at least 64, the chain is transformed into a red‑black tree.

After insertion, size is incremented and, if it exceeds threshold, the map is resized.

1.3 Retrieval (get) Logic

get(Object key)

computes the hash, locates the bucket, checks the first node, and then traverses the linked list or tree until the matching key is found.

1.4 Resizing

When size > threshold, resize() creates a new table with double the capacity (still a power of two). Because the new capacity is exactly twice the old one, each entry either stays in its original index or moves to oldIndex + oldCap, eliminating the need to recompute the full hash.

1.5 Thread‑Safety Issues

HashMap is not synchronized. In a multithreaded environment, concurrent put operations can cause data loss, overwriting, or infinite loops during resizing because the size counter and node insertion are not atomic.

2. LinkedHashMap Overview

LinkedHashMap extends HashMap and adds a doubly linked list that preserves insertion order (default) or access order (when accessOrder is true). It introduces an inner class Entry that extends Node and adds before and after pointers.

public class LinkedHashMap<K,V> extends HashMap<K,V> {
    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);
        }
    }
    transient Entry<K,V> head;
    transient Entry<K,V> tail;
    final boolean accessOrder;
    ...
}

Five constructors are provided; the one with the boolean accessOrder parameter enables LRU‑style ordering.

2.1 Maintaining Order

After each insertion, afterNodeInsertion can remove the eldest entry if removeEldestEntry returns true. After each access, afterNodeAccess moves the accessed entry to the tail when accessOrder is true.

2.2 LRU Cache Example

By creating a subclass of LinkedHashMap with accessOrder = true and overriding removeEldestEntry to return size() > cacheSize, a simple LRU cache is obtained.

public class LRU<K,V> extends LinkedHashMap<K,V> {
    private final int cacheSize;
    public LRU(int cacheSize) {
        super(cacheSize, 0.75f, true);
        this.cacheSize = cacheSize;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > cacheSize;
    }
}

This cache automatically evicts the least‑recently‑used entry when the maximum size is exceeded.