Enhancing Hash Tables with Linked Lists (LinkedHashMap)

Before reading this article, you should first study:

Core principles of hash tables

The earlier article on hash table principles explained why you cannot rely on the order in which keys are traversed—hash table keys are inherently unordered.

Yet practical programming experience may leave you with some questions.

Readers familiar with Java, for example, know that the standard library’s LinkedHashMap supports traversal in the order of key insertion. Consider this short snippet:

import java.util.LinkedHashMap;

public class Main {
    public static void main(String[] args) {
        LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
        map.put("a", 1);
        map.put("b", 2);
        map.put("c", 3);
        System.out.println(map.keySet()); // [a, b, c]

        map.put("y", 4);
        System.out.println(map.keySet()); // [a, b, c, y]

        map.put("d", 5);
        System.out.println(map.keySet()); // [a, b, c, y, d]
    }
}

No matter how many keys you insert, the set returned by keySet always appears in insertion order, almost as if elements were being appended to the end of an array. How is that possible?

If you know Go, you will notice an even more surprising behavior. Take this test:

package main

import (
	"fmt"
)

func main() {
	// Initialize the map
	myMap := map[string]int{
		"1": 1,
		"2": 2,
		"3": 3,
		"4": 4,
		"5": 5,
	}

	// Function that prints the keys of a map
	printMapKeys := func(m map[string]int) {
		for key := range m {
			fmt.Print(key, " ")
		}
		fmt.Println()
	}

	// Traverse the map several times and observe key order
	printMapKeys(myMap)
	printMapKeys(myMap)
	printMapKeys(myMap)
	printMapKeys(myMap)
}

// Observed output on one run:
// 1 2 3 4 5
// 5 1 2 3 4
// 2 3 4 5 1
// 1 2 3 4 5

Each traversal yields a different order. According to the hash-table principles discussed earlier, keys are unordered, yet performing no mutations should leave the traversal order stable. Why does a Go map produce a new order every time? It seems almost absurd.

Try to reason about the cause yourself; the explanation follows.

Implementation Idea for a Hash-Linked List (LinkedHashMap)

Let’s first state the problem clearly.

In a conventional hash table the keys reside unordered inside the underlying table array:

Looking at that diagram alone, you cannot tell the insertion sequence of the keys, and any resize will scramble their positions again.

We want to visit every key in the order it was inserted, without altering the complexity of the usual hash-table operations and without being affected by resizing.

The most straightforward approach is to thread the key-value pairs together with a structure resembling linked-list nodes, while keeping references to a head and a tail. Whenever a new key is placed into the table array, the same key is also appended at the end of this auxiliary list.

Consequently, walking from the head node yields the keys in exact insertion order:

It is immediately visible that the insertion sequence was k2, k4, k5, k3, k1.

Think abstractly—do not get lost in details

Some readers will now feel confused: the chaining method for hash collisions already uses lists, so are we nesting yet another list on top of those lists? How would that even work?

This is precisely why the opening of the site stresses the importance of abstraction. Every data structure is ultimately just arrays and lists decorated with extra logic; add a few more layers and the picture becomes dizzying.

If that doubt arises, it is because your mind is still filled with the concrete chaining or linear-probing implementations from earlier chapters and has become trapped in those low-level details. Is that accurate?

Step back from the details and look at the abstractions: a hash table is simply a key-to-value mapping, while a linked list is simply a container that stores elements in sequence. The goal is to make the keys of that mapping appear in insertion order—how do we combine the two structures?

Here is the answer:

Assume both keys and values are strings. A normal hash table looks like this:

HashMap<String, String> map = new HashMap<>();

// Insert a key-value pair
String key = "k1";
String value = "v1";

map.put(key, value);

Now we wrap the value type of the hash table inside a doubly-linked-list node:

// Doubly-linked-list node
class Node {
    String key;
    String value;
    Node prev;
    Node next;

    Node(String key, String value) {
        this.key = key;
        this.value = value;
    }
}

HashMap<String, Node> map = new HashMap<>();

// Insert a key-value pair
String key = "k1";
String value = "v1";

map.put(key, new Node(key, value));

// Simplified: real code must also splice the new node into the list

This produces the desired hash-linked-list structure:

A key still locates its corresponding doubly-linked node (and therefore its value) in (O(1)) expected time.

A new key-value pair can be inserted in (O(1)) expected time, because both the hash-table insertion and the append at either end of a doubly-linked list are (O(1)).

A given key-value pair can be removed in (O(1)) expected time, because both the hash-table deletion and the unlinking of a known doubly-linked node are (O(1)).

Because the nodes stay in insertion order, simply walking the list from the head yields every key in that order.

In short, we obtain ordered access to the keys while leaving the asymptotic cost of the ordinary hash-table operations unchanged.

Is list deletion really (O(1))?

Readers who recall the earlier list-principles article may object: “You said list deletion costs (O(n)), yet now you claim (O(1)).”

The claim here is precise: deleting a given doubly-linked node costs (O(1)).

When we previously implemented lists by hand, we deleted a node at a specified index; that indeed requires (O(n)) time because the node must first be located by walking the list.

No such walk occurs here—the node is obtained directly from the hash-table mapping, which takes expected (O(1)) time.

A doubly-linked node can then unlink itself with a constant number of pointer assignments:

// Remove a known doubly-linked node
Node target;

// Unlink target from the list
target.prev.next = target.next;
target.next.prev = target.prev;
target.prev = null;
target.next = null;

Hence the overall deletion complexity of the hash-linked list remains expected (O(1)).

Note that only a doubly-linked node possesses both predecessor and successor pointers, enabling true (O(1)) removal. A singly-linked node has only a successor pointer and cannot be unlinked in constant time without a predecessor. Consequently the hash-linked-list design must employ a doubly-linked list.

Code Implementation

Once the idea is clear, the concrete code is straightforward:

class MyLinkedHashMap:
    class Node:
        def __init__(self, key, val):
            self.key = key
            self.val = val
            self.next = None
            self.prev = None

    def __init__(self):
        self.head = self.Node(None, None)
        self.tail = self.Node(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.map = dict()

    def get(self, key):
        if key not in self.map:
            return None
        return self.map[key].val

    def put(self, key, val):
        # Brand-new key: insert into both the list and the map
        if key not in self.map:
            node = self.Node(key, val)
            self.add_last_node(node)
            self.map[key] = node
            return
        # Existing key: simply overwrite the stored value
        self.map[key].val = val

    def remove(self, key):
        # Missing key: nothing to do
        if key not in self.map:
            return
        # Present key: delete from both the map and the list
        node = self.map[key]
        del self.map[key]
        self.remove_node(node)

    def contains_key(self, key):
        return key in self.map

    def keys(self):
        key_list = []
        p = self.head.next
        while p != self.tail:
            key_list.append(p.key)
            p = p.next
        return key_list

    def add_last_node(self, x):
        temp = self.tail.prev
        # temp <-> tail

        x.next = self.tail
        x.prev = temp
        # temp <- x -> tail

        temp.next = x
        self.tail.prev = x
        # temp <-> x <-> tail

    def remove_node(self, x):
        prev = x.prev
        next = x.next
        # prev <-> x <-> next

        prev.next = next
        next.prev = prev

        x.next = x.prev = None


if __name__ == '__main__':
    map = MyLinkedHashMap()
    map.put("a", 1)
    map.put("b", 2)
    map.put("c", 3)
    map.put("d", 4)
    map.put("e", 5)

    print(map.keys())  # ['a', 'b', 'c', 'd', 'e']
    map.remove("c")
    print(map.keys())  # ['a', 'b', 'd', 'e']

Realizing LinkedHashSet

A LinkedHashSet is simply a hash set that remembers insertion order.

The earlier article on hash-set principles noted that a hash set is essentially a thin wrapper around a hash map.

Therefore a LinkedHashSet can be obtained by wrapping the MyLinkedHashMap shown above; the construction is trivial and the code is omitted here.