Use Linked List to Enhance Hash Table (LinkedHashMap)

labuladongOriginalAbout 3299 words

Prerequisite Knowledge

Before reading this article, you need to learn:

Core Principles of Hash Tables

The previous article Principles of Hash Tables analyzed that you cannot rely on the order of keys in a hash table, meaning the keys are unordered.

However, based on practical programming experience, you may have some questions.

For instance, readers familiar with Python might know that starting from Python 3.7, the standard library's hash table dict explicitly tells you that the iteration order of dict keys is the same as the insertion order. For example, consider this simple code:

d = dict()

d['a'] = 1
d['b'] = 2
d['c'] = 3
print(list(d.keys()))  # ['a', 'b', 'c']

d['y'] = 4
print(list(d.keys()))  # ['a', 'b', 'c', 'y']

d['d'] = 5
print(list(d.keys()))  # ['a', 'b', 'c', 'y', 'd']

No matter how many keys you insert, the keys method returns all keys in the order they were inserted, as if you were appending elements to the end of an array. How is this possible?

If you are familiar with Golang, you will notice an even more intriguing phenomenon. For example, consider the following test code:

package main

import (
	"fmt"
)

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

	// define a function to iterate through the map
	printMapKeys := func(m map[string]int) {
		for key := range m {
			fmt.Print(key, " ")
		}
		fmt.Println()
	}

	// iterate through the map multiple times to observe the order of keys
	printMapKeys(myMap)
	printMapKeys(myMap)
	printMapKeys(myMap)
	printMapKeys(myMap)
}

// my output is as follows:
// 1 2 3 4 5
// 5 1 2 3 4
// 2 3 4 5 1
// 1 2 3 4 5

In essence, the order in which it traverses is random each time. However, according to the earlier article Principles of Hash Tables, while the keys in a hash table are unordered, the traversal result should remain consistent if no operations are performed on the hash table. So why does the order of traversal in Golang's map differ each time? Isn't this quite puzzling?

You can first think about the reason yourself; I'll provide the answer below.

Click to view the answer

Let's talk about Golang first. The reason the traversal is unordered each time is that it's intentional.

This reason is somewhat amusing. Golang deliberately returns a different order each time to prevent developers from relying on the traversal order of hash tables. This thoughtful approach indeed highlights that many developers might not understand the basic principles of hash tables.

Let's think further about how it disrupts the order. Is it truly random?

Actually, it's not. If you look closely, there is a pattern to this unordered sequence. Does it remind you of the Circular Array we discussed earlier?

| 1 2 3 4 5
5 | 1 2 3 4
2 3 4 5 | 1
| 1 2 3 4 5

Can you see it? If resizing is not triggered, the traversal order is essentially fixed. It just doesn't always start from the beginning of the underlying table array; instead, it begins at a random position and uses the circular array technique to traverse the entire table array. This ensures that the order seems random across multiple traversals.

Now, regarding Python, it can have all keys arranged in insertion order because it combines a standard hash table with a linked list to form a new data structure: a hash-linked list.

Other programming languages have similar implementations, like Java's LinkedHashMap. This data structure maintains the $O(1)$ efficiency of hash tables for insertions, deletions, and lookups, while also preserving the insertion order of keys like an array or linked list.

How does it achieve this? I will explain in detail below.

Use Linked List to Enhance Hash Table (LinkedHashMap)

Implementation Concept of Hash Linked List (LinkedHashMap)

Code Implementation

Implementation of `LinkedHashSet`