用链表加强哈希表（LinkedHashMap）

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']

package main

import (
	"fmt"
)

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

	// 定义遍历 map 的函数
	printMapKeys := func(m map[string]int) {
		for key := range m {
			fmt.Print(key, " ")
		}
		fmt.Println()
	}

	// 多次遍历 map，观察键的顺序
	printMapKeys(myMap)
	printMapKeys(myMap)
	printMapKeys(myMap)
	printMapKeys(myMap)
}

// 我运行的结果如下：
// 1 2 3 4 5
// 5 1 2 3 4
// 2 3 4 5 1
// 1 2 3 4 5

**先说 Golang 吧，每次遍历都乱序的原因就是，它故意的**。

这个原因属实是让人有些哭笑不得，Golang 为了防止开发者依赖哈希表的遍历顺序，所以每次遍历都故意返回不同的顺序，可谓用心良苦。也可以从侧面看出，确实不少开发者没了解过哈希表的基本原理。

我们不妨进一步想想，它是怎么打乱顺序的呢？真是随机打乱吗？

其实不是，你仔细看看，它这个乱序是有规律的。有没有想起前面讲过的[环形数组](05-环形数组技巧及实现.md)？

```text
| 1 2 3 4 5
5 | 1 2 3 4
2 3 4 5 | 1
| 1 2 3 4 5
```

看出来没有？如果不触发扩缩容的话，实际上它的遍历顺序应该也是固定的，只不过它不是每次都从底层 table 数组的头部开始，而是从一个随机的位置开始，然后利用环形数组技巧遍历整个 table 数组，这样就能保证多次遍历的结果具有随机性，同时又不至于为了随机性而牺牲太多性能。

再说 **Python，它能让所有键按照插入顺序排列，是因为它把标准的哈希表和链表结合起来，组成了一种新的数据结构：哈希链表**。

其他编程语言也有类似的实现，比如 Java 的 LinkedHashMap。这种数据结构兼具了哈希表 O(1) 的增删查改效率，同时又可以像数组链表一样保持键的插入顺序。

它是怎么做的呢？下面我会具体讲解。

**发挥抽象思维，不要陷入细节**

但肯定有读者会绕晕：之前[拉链法实现哈希表](12-用拉链法实现哈希表.md) 不就是用链表解决哈希冲突的吗？现在相当于在链表上再套一层链表？这咋实现啊？

所以我在本站的开篇就说，要有抽象能力。你看所有数据结构，本质上就是在数组、链表这两种基本结构上雕花，但即便如此，多套几层你也晕了。

如果产生这样的疑问，是因为你脑子里全是前两章讲的拉链法、线性探查法的底层实现原理，陷入细节无法自拔了，是不是这样？

请跳出细节，抽象来看，哈希表本质上就是一个键值映射，链表本质上就是一个顺序存储元素的容器。现在我就是想让这个键值映射中的键按照插入顺序排列，怎么把哈希表和链表结合起来？

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

// 插入键值对
String key = "k1";
String value = "v1";

map.put(key, value);

// 双链表节点
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<>();

// 插入键值对
String key = "k1";
String value = "v1";

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

// 这里做了简化，实际实现中还要操作新的链表节点加入链表

链表的删除操作时间复杂度是 O(1)？

肯定有读者记得，前文
链表原理 说过，链表的删除操作时间复杂度是 (n) 啊，怎么现在又说是 O(1) 了？

实际上我说的已经很严谨了，我这里说的是 **删除给定双链表节点的操作是 O(1)**。

前文我们动手实现链表的时候，我们是删除指定索引的链表节点，时间复杂度确实是 O(n)，因为要先遍历到这个索引，然后才能开始删除嘛。

但是这里并没有遍历的过程，我们是直接通过哈希表键值映射拿到的这个链表节点，时间复杂度是 O(1)。

且双链表节点只需进行简单的指针操作即可把自身从链表中删除，时间复杂度是 O(1)：

```java
// 删除给定双链表节点
Node target;

// 在双链表中删除 target 节点
target.prev.next = target.next;
target.next.prev = target.prev;
target.prev = null;
target.next = null;
```

package main

import "fmt"

type MyLinkedHashMap struct {
    head *Node
    tail *Node
    m    map[string]*Node
}

type Node struct {
    key  string
    val  int
    next *Node
    prev *Node
}

func Constructor() MyLinkedHashMap {
    head := &Node{}
    tail := &Node{}
    head.next = tail
    tail.prev = head
    return MyLinkedHashMap{
        head: head,
        tail: tail,
        m:    make(map[string]*Node),
    }
}

func (this *MyLinkedHashMap) Get(key string) int {
    if node, ok := this.m[key]; ok {
        return node.val
    }
    return -1
}

func (this *MyLinkedHashMap) Put(key string, val int) {
    // 若为新插入的节点，则同时插入链表和 map
    if _, ok := this.m[key]; !ok {
        // 插入新的 Node
        node := &Node{key: key, val: val}
        this.addLastNode(node)
        this.m[key] = node
        return
    }
    // 若存在，则替换之前的 val
    this.m[key].val = val
}

func (this *MyLinkedHashMap) Remove(key string) {
    // 若 key 本不存在，直接返回
    if _, ok := this.m[key]; !ok {
        return
    }
    // 若 key 存在，则需要同时在哈希表和链表中删除
    node := this.m[key]
    delete(this.m, key)
    this.removeNode(node)
}

func (this *MyLinkedHashMap) ContainsKey(key string) bool {
    _, ok := this.m[key]
    return ok
}

func (this *MyLinkedHashMap) Keys() []string {
    keyList := make([]string, 0)
    for p := this.head.next; p != this.tail; p = p.next {
        keyList = append(keyList, p.key)
    }
    return keyList
}

func (this *MyLinkedHashMap) addLastNode(x *Node) {
    temp := this.tail.prev
    // temp <-> tail

    x.next = this.tail
    x.prev = temp
    // temp <- x -> tail

    temp.next = x
    this.tail.prev = x
    // temp <-> x <-> tail
}

func (this *MyLinkedHashMap) removeNode(x *Node) {
    prev := x.prev
    next := x.next
    // prev <-> x <-> next

    prev.next = next
    next.prev = prev

    x.next = nil
    x.prev = nil
}


func main() {
    myMap := Constructor()
    myMap.Put("a", 1)
    myMap.Put("b", 2)
    myMap.Put("c", 3)
    myMap.Put("d", 4)
    myMap.Put("e", 5)

    // output: a b c d e
    fmt.Println(myMap.Keys())

    myMap.Remove("c")

    // output: a b d e
    fmt.Println(myMap.Keys())
}