As its name implies, LinkedHashMap is a hash table and linked list implementation of the Map interface, with predictable iteration order. Different with HashMap, it maintains a doubly-linked list running through all of its entries, which also defines the iteration ordering, same as the order in which keys were inserted into the map. This order remains if a key is re-inserted into the map.

Like HashMap, LinkedHashMap provides constant-time performance for the basic operations add, contains and remove, assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list,

Thanks to the linked list, this kind of map is well-suited to building LRU caches. So my questions is how LinkedHashMap preserves the linked list when key changes.

First of all we must get through the data structure.

Data Structure

Three variables in LinkedHashMap includes,

  • head: the head (eldest) of the doubly linked list
  • tail: the tail (youngest) of the doubly linked list.
  • accessOrder: the iteration ordering method for this linked hash map
// LinkedHashMap.java

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    transient LinkedHashMap.Entry<K,V> head;
    transient LinkedHashMap.Entry<K,V> tail;
    final boolean accessOrder;
}

As to LinkedHashMap.Entry<K,V>, a nested class in LinkedHashMap, we can see,

// LinkedHashMap.java

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);
    }
}

get

As the subclass of HashMap, LinkedHashMap get value from the table of base class.

// LinkedHashMap.java

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

It is advisable to keep this array for fast read, after which afterNodeAccess is called to update the linked list, moving the node just accessed to last of the list. You can see the details from comments in the code.

// LinkedHashMap.java

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;

        // if p is the old head
        if (b == null)
            head = a; // update head
        else
            b.after = a; // kick p out

        // if p is not the tail    
        if (a != null)
            a.before = b; // kick p out
        else
            last = b; // make b the tail

        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

put

There is no put method in LinkedHashMap which means the one from base class is not overwritten. But it overwrite the newNode called from put.

newNode

// LinkedHashMap.java

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;
}

It’s reasonable to infer newNode do some maintain work with the help of linkNodeLast.

// LinkedHashMap.java

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;

    // empty list
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

Since the code is so succinct that we can discover it link the new node at the end of list.

afterNodeInsertion

Another method called from put and overwritten by LinkedHashMap is afterNodeInsertion.

// LinkedHashMap.java

void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

afterNodeInsertion possibly removes eldest node from the list. Since removeEldestEntry always return false, so afterNodeInsertion does not modify the map in any way. removeNode is also in HashMap and keep intact, which will be discussed in the next section.

remove

Being left out by last post, remove removes the mapping for the specified key from this map if present.

// HashMap.java

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

Despite the nested if-else, removeNode does the following steps:

  • locate the key to be deleted
  • update table and link key’s previous node and next node
  • do some other work with afterNodeRemoval

For afterNodeRemoval, it unlink the node from linked list.

// LinkedHashMap.java

void afterNodeRemoval(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // isolate the node    
    p.before = p.after = null;

    // if it is head
    if (b == null)
        head = a;
    else
        b.after = a;

    // if it is tail    
    if (a == null)
        tail = b;
    else
        a.before = b;
}