用链表加强哈希表（LinkedHashMap）

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

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

For example, readers familiar with Python may know that starting from Python 3.7, the standard library's hash table dict explicitly states that the iteration order of dict keys is the order of their insertion. For instance, consider the following 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 other words, each traversal order is random. However, according to the previous article Hash Table Principles, although the keys in a hash table are unordered, the traversal result should remain the same if no operations are performed on the hash table. So why does the traversal order of Golang's map change every time? Isn't that too strange?

You can think about the reason first, and I'll provide the answer below.

Click to see the answer

First, let's talk about Golang. The reason the traversal order is chaotic each time is that it is 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 approach shows that many developers are unfamiliar with the basic principles of hash tables.

Let's think further: how does it disrupt the order? Is it truly random?

Actually, it's not. If you look closely, there is a pattern to the disorder. Do you remember the Circular Array discussed earlier?

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

Do you see it? If no resizing happens, the traversal order is actually fixed. It just doesn't always start from the beginning of the underlying table array. Instead, it starts from a random position and uses the circular array technique to traverse the entire table array, ensuring the traversal order appears random.

Now, let's talk about Python. It can keep all keys in the order of insertion because it combines a standard hash table with a linked list, forming a new data structure: the hash-linked list.

Other programming languages have similar implementations, such as Java's LinkedHashMap. This data structure combines the O(1) efficiency of hash tables for add, delete, and lookup operations with the ability to maintain the order of key insertion like a linked list.

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

Implementation Concept of LinkedHashMap

Code Implementation

Implementation of `LinkedHashSet`

loading...