用数组加强哈希表
核心问题
在标准哈希表 API 基础上，添加 randomKey() API，要求 O(1) 时间复杂度随机返回一个键（均匀随机）。
interface Map<K, V> {
V get(K key);
void put(K key, V value);
void remove(K key);
boolean containsKey(K key);
List<K> keys();
// 新增：O(1) 随机返回一个 key
K randomKey();
}
问题难点分析
1. 哈希表底层数组的特点
哈希表底层 table 数组存在两个问题：
- 存在空洞：删除或哈希冲突后，数组中有些位置为
null - 拉链法更复杂：数组每个元素是一个链表，需要同时随机索引和链表节点
2. 错误方案分析
| 方案 | 问题 | 是否满足要求 |
|---|---|---|
| 线性探查（向右找非空） | 不是均匀随机（空洞右侧元素概率更高） | ❌ |
| 重复随机直到命中非空 | 时间复杂度依赖随机数，不保证 O(1) | ❌ |
| 遍历所有键到数组再随机 | 时间复杂度 O(N) | ❌ |
概率分析示例：
- 数组
[1, 2, null, 4]，线性探查方案：1,2,4被选中的概率分别是1/4, 1/4, 2/4（不均匀） - 拉链法：若数组 2 个桶，桶1有 3 个键，桶2有 2 个键。均匀随机索引+均匀随机节点 →
k1,k2,k3概率1/2 * 1/3 = 1/6，k4,k5概率1/2 * 1/2 = 1/4（不均匀）
数据结构设计：数组加强哈希表
（原文内容不完整，仅获取到问题分析部分，解决方案部分缺失）
预告方案：用数组（紧凑存储）配合哈希表，维护键的有序列表，实现 O(1) 随机访问。
设计思路（推测）
- 维护一个紧凑数组：存储所有当前键，无空洞
- 哈希表记录索引：
key → 在数组中的位置 - randomKey()：随机生成
[0, size)的索引，直接从数组返回 - 删除时：用数组末尾元素填补空缺，更新哈希表（O(1)）
结构示意：
哈希表 (key → index)
┌─────────┬─────────┐
│ key1 │ 0 │
│ key2 │ 1 │
│ key3 │ 2 │
└─────────┴─────────┘
数组 (紧凑存储)
┌─────────┬─────────┬─────────┐
│ key1 │ key2 │ key3 │
└─────────┴─────────┴─────────┘
↑ 0 ↑ 1 ↑ 2
与哈希链表对比
| 特性 | 哈希链表 (LinkedHashMap) | 数组加强哈希表 |
|---|---|---|
| 目标 | 维护插入顺序 | O(1) 随机返回键 |
| 组合方式 | 哈希表 + 双向链表 | 哈希表 + 紧凑数组 |
| 额外操作 | 维护链表指针 | 维护数组索引 |
| 删除复杂度 | O(1) 链表摘除 | O(1) 末尾填补 |
| 遍历顺序 | 按插入顺序 | 无序（随机访问） |
详细对比见：哈希链表vs数组加强哈希表