哈希链表
定义
哈希链表（Hash Linked List）是一种组合数据结构，将哈希表与双向链表结合，兼具两者的优点：
- 哈希表特性：O(1) 时间复杂度的增删查改
- 链表特性：维护元素的逻辑顺序（如插入顺序）
实现原理
核心思想：每个哈希表节点同时维护链表指针
哈希表 table 数组
↓
[桶0] → Node(key1, val1) ⇄ Node(key2, val2) ← 双向链表
[桶1] → Node(key3, val3)
[桶2] → null
...
双向链表维护所有节点的插入顺序：
head ⇄ Node(key1) ⇄ Node(key2) ⇄ Node(key3) ⇄ tail
操作逻辑：
- 插入：按哈希表方式插入，同时追加到双向链表尾部
- 删除：从哈希表中移除，同时从双向链表中摘除
- 遍历：按双向链表顺序遍历，得到插入顺序
典型实现
Java LinkedHashMap
Java 标准库的 LinkedHashMap 是哈希链表的典型实现：
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("a", 1);
map.put("b", 2);
System.out.println(map.keySet()); // [a, b] 按插入顺序
特点：
- 继承
HashMap，底层使用哈希表 + 双向链表 keySet()、entrySet()按插入顺序返回- 维护
head（最早插入）和tail（最近插入）指针
与拉链法的区别
| 特性 | 拉链法（链地址法） | 哈希链表 |
|---|---|---|
| 链表作用 | 解决同一桶内的哈希冲突 | 维护所有元素的逻辑顺序 |
| 链表范围 | 仅限单个桶内 | 跨所有桶，全局链接 |
| 遍历顺序 | 无序（依赖桶和链表顺序） | 有序（按插入顺序） |
| 空间开销 | 只存冲突元素 | 所有元素都需维护链表指针 |
应用场景
- 需要保持插入顺序的键值对存储
- LRU 缓存实现（结合访问顺序）
- 需要按插入顺序遍历的哈希表场景