哈希链表 vs 数组加强哈希表
对比两种基于哈希表的组合数据结构设计
概述
| 维度 | 哈希链表 (Hash Linked List) | 数组加强哈希表 (Hash Table + Array) |
|---|---|---|
| 别名 | LinkedHashMap | Hash Map with Array / Randomized HashMap |
| 核心目标 | 维护键的插入顺序 | O(1) 时间随机返回一个键 (randomKey) |
| 组合方式 | 哈希表 + 双向链表 | 哈希表 + 紧凑数组 |
| 来源文章 | 哈希表与链表组合原理 | 用数组加强哈希表 |
数据结构设计对比
哈希链表（LinkedHashMap）
哈希表 table 数组
↓
[桶0] → Node(key1, val1) ⇄ Node(key2, val2) ← 桶内链表（拉链法）
[桶1] → Node(key3, val3)
[桶2] → null
...
双向链表维护所有节点的插入顺序：
head ⇄ Node(key1) ⇄ Node(key2) ⇄ Node(key3) ⇄ tail
额外维护：
- 每个节点：哈希表指针（next用于桶内冲突）+ 链表指针（prev/next用于全局顺序）
- 全局 head 和 tail 指针
数组加强哈希表
哈希表 (key → index in array)
┌─────────┬─────────┐
│ key1 │ 0 │
│ key2 │ 1 │
│ key3 │ 2 │
└─────────┴─────────┘
紧凑数组 (无空洞)
┌─────────┬─────────┬─────────┐
│ key1 │ key2 │ key3 │
└─────────┴─────────┴─────────┘
↑ 0 ↑ 1 ↑ 2
额外维护：
- 哈希表记录每个 key 在数组中的索引
- 紧凑数组存储所有 key（用于 O(1) 随机访问）
操作复杂度对比
| 操作 | 哈希链表 | 数组加强哈希表 |
|---|---|---|
| get(key) | O(1) 哈希表查找 | O(1) 哈希表查找 |
| put(key, val) | O(1) 哈希表插入 + 链表追加 | O(1) 哈希表插入 + 数组追加 |
| remove(key) | O(1) 哈希表删除 + 链表摘除 | O(1) 用末尾元素填补 + 更新哈希表 |
| 遍历顺序 | O(n) 按插入顺序 | O(n) 无序（按数组顺序） |
| randomKey() | O(n) 需要遍历链表 | O(1) 随机数组索引 |
删除操作细节（数组加强哈希表）
删除 key2 (索引1):
1. 数组末尾元素 key3 移到位置1
2. 数组末尾删除（size--）
3. 更新哈希表：key3 → 1
数组变化：
删除前: [key1, key2, key3]
删除后: [key1, key3]
关键点：用末尾元素填补空缺，避免数组空洞，保持 O(1) 操作。
使用场景对比
| 场景 | 推荐结构 | 原因 |
|---|---|---|
| 需要保持插入顺序 | 哈希链表 | 双向链表天然维护顺序 |
| 需要按插入顺序遍历 | 哈希链表 | keySet() 按插入顺序返回 |
| 需要 O(1) 随机返回键 | 数组加强哈希表 | 紧凑数组支持随机访问 |
| 实现 LRU 缓存 | 哈希链表 | 访问顺序 + 插入顺序结合 |
| 游戏/抽样场景 | 数组加强哈希表 | 需要均匀随机选择一个键 |
空间开销对比
| 开销类型 | 哈希链表 | 数组加强哈希表 |
|---|---|---|
| 每个节点指针 | 3个（next桶内 + prev/next全局） | 1个（数组索引，存于哈希表） |
| 额外全局指针 | head + tail | 无（数组本身有序） |
| 数组存储 | 仅哈希表 table | table + 紧凑数组（存储所有key） |
结论：两种结构空间开销相近，选择取决于功能需求。
与标准哈希表的关系
标准哈希表 (HashMap)
│
├─→ 哈希链表 (LinkedHashMap) ：增加顺序维护
│
└─→ 数组加强哈希表 (RandomizedHashMap) ：增加随机访问能力