LeetCode 380 详解：哈希表+动态数组实现O(1)随机集合设计

LeetCode 380这道题说实在的它是设计类题目里最“甜”的一道。题面简单到没有任何包装实现一个数据结构支持在O(1) 时间内完成插入、删除和获取随机元素。第一次看到这个要求大多数人第一反应是“就这”结果真上手写的时候才发现前两个操作好说关键是“随机”和“O(1)”一旦绑在一起方案就变窄了。这道题常年挂在LeetCode热门100题列表上也是面试高频题很适合作为“哈希表 线性结构组合设计”的入门模板。我最早做这道题的时候也卡了挺久这里把我完整的思考过程、最终实现、以及实测踩过的坑都整理出来希望能帮到你。1. 题意拆解三个方法一个都不能慢1.1 需求到底在说什么先看清楚要求。题目要我们实现一个RandomizedSet类内部维护一个集合提供三个方法insert(val)如果 val 不在集合中插入并返回 true如果已经存在返回 false不插入。remove(val)如果 val 在集合中删除并返回 true如果不存在返回 false。getRandom()等概率随机返回集合中的一个元素。注意一个隐含前提题目保证不会在集合为空的时候调用getRandom()也不会在删除空集合里的元素时把你难住不存在时返回 false 就行。这里最容易被忽略的是“等概率”三个字。有的写法确实能从集合里随机出一个数但不是等概率的或者依赖了某种会退化的结构这个等会详细讲。1.2 为什么 O(1) 这么难凑齐三个操作都要 O(1) 平均时间复杂度这个约束放在一起基本把绝大多数“直观方案”都毙掉了。如果只用数组ArrayList存元素插入 O(1) 没问题随机 O(1) 也没问题但删除一个中间元素需要把后面的元素全部前移最坏 O(n)。不可接受。如果只用哈希表HashMap存元素插入 O(1)、删除 O(1) 都很自然可随机获取呢哈希表本身不保序你想随机拿一个 key要么把 keys 转成数组再随机那是 O(n)要么遍历到某个位置那也是 O(n)。用 LinkedHashSet 这类带顺序的结构插入删除是 O(1)但随机访问底层链表时需要从头部走到随机位置还是 O(n)。所以单独任何一种常用结构都没法同时满足三个 O(1)。这时候就得换个思路既然单打独斗不行那就让两个结构分工协作。1.3 这道题在面试里考察什么它是典型的数据结构设计题面试官想考察的不只是你会不会用 HashMap而是你有没有“把不同结构的优势组合起来”的意识。在系统设计里没有任何一种数据结构是万能银弹很多时候性能瓶颈就是靠多级结构配合来解决的。比如 LRU Cache 是“哈希表 双向链表”LFU Cache 是“哈希表 多个桶链表”而这道 380 是“哈希表 动态数组”。你会发现核心思想一脉相承哈希表负责 O(1) 定位线性/链式结构负责 O(1) 维护顺序或随机访问。2. 核心思路哈希表负责定位数组负责随机2.1 为什么选 ArrayList 当存储本体先定一个基调所有元素真正存储在ArrayListInteger里。为什么是数组而不是链表因为getRandom()要求等概率访问任意元素只有数组能在 O(1) 时间内按下标直接取元素。链表要走到第 i 个节点再快也得 O(i)。数组唯一的痛点就是“删除中间元素要搬移后续元素”。但这个问题可以被技巧绕过关键就是这个技巧。2.2 哈希表存的不是元素而是下标用一个HashMapInteger, Integerkey 存元素值value 存该元素在数组中的下标。这样设计的原因很直接删除的时候我得先知道这个元素在数组的哪个位置才能去动数组。HashMap 的get(val)能 O(1) 告诉我下标。反过来如果只用ArrayList.indexOf(val)去查下标那是 O(n) 遍历直接废了。所以两个结构的分工非常清晰list是“数据本体”承担随机访问。map是“索引表”承担快速定位。二者维护同一个逻辑集合彼此通过下标关联。2.3 插入为什么要先查重插入其实最好写先判断 map 里有没有这个值。有说明集合里已经存在返回 false。没有把元素追加到 list 末尾然后把(val, list.size() - 1)记进 map返回 true。向数组末尾追加是均摊 O(1)HashMap 的 put 也是平均 O(1)满足要求。要注意的是list.size() - 1一定是插入前的 size因为此时元素还没 add。顺序上我习惯先 add 再 put 映射或者先记录下标再 add 都行只要下标算对。2.4 删除的精髓把目标换到末尾再删这是整道题最核心的 trick。假设当前数组是[10, 20, 30, 40]要删除20通过 map 查出 20 的下标是 1。取出数组最后一个元素 40把它覆盖到下标 1 的位置数组变成[10, 40, 30, 40]。更新 map 里 40 的映射40 原来在下标 3现在变成了下标 1。把数组末尾真正删除list 变成[10, 40, 30]。从 map 中删除 20。整个过程不涉及数组元素的搬移只有一次覆盖和一次末尾删除所以是 O(1)。这个处理方式背后有一个理解误区需要纠正很多人觉得删除就是“把数组里的洞补上”为了保持数组紧凑只能把后面的元素整体左移。但“保持紧凑”不等于“保持相对顺序不变”我们只要求集合内容一致数组内部顺序无所谓。既然顺序无所谓那就没必要左移直接把最后一个元素拿过来填空就行了。这就像整理一排书架你不用把后面所有书都往左挪一本直接把最右边的书抽出来插到空位上再把空书架处理掉一样能达到“没有空位”的效果。3. 代码实现与逐行讲解3.1 Java 版本import java.util.*; class RandomizedSet { private final MapInteger, Integer valToIndex; private final ListInteger values; private final Random random; public RandomizedSet() { valToIndex new HashMap(); values new ArrayList(); random new Random(); } public boolean insert(int val) { if (valToIndex.containsKey(val)) { return false; } valToIndex.put(val, values.size()); values.add(val); return true; } public boolean remove(int val) { if (!valToIndex.containsKey(val)) { return false; } int index valToIndex.get(val); int lastIndex values.size() - 1; int lastVal values.get(lastIndex); // 用末尾元素覆盖待删除元素 values.set(index, lastVal); // 更新末尾元素的新下标 valToIndex.put(lastVal, index); // 真正删除末尾 values.remove(lastIndex); // 移除待删除元素的映射 valToIndex.remove(val); return true; } public int getRandom() { return values.get(random.nextInt(values.size())); } }3.2 Python 版本import random class RandomizedSet: def __init__(self): self.val_to_index {} self.values [] def insert(self, val: int) - bool: if val in self.val_to_index: return False self.val_to_index[val] len(self.values) self.values.append(val) return True def remove(self, val: int) - bool: if val not in self.val_to_index: return False idx self.val_to_index[val] last_val self.values[-1] self.values[idx] last_val self.val_to_index[last_val] idx self.values.pop() del self.val_to_index[val] return True def getRandom(self) - int: return random.choice(self.values)两种写法逻辑完全一致核心就四步查下标、末尾覆盖、更新映射、删除两处。3.3 删除操作的顺序陷阱有几行代码的顺序是精心安排的我实测中踩过坑。先看这段values.set(index, lastVal); valToIndex.put(lastVal, index); values.remove(lastIndex); valToIndex.remove(val);如果你把valToIndex.remove(val)提前比如放在valToIndex.put(lastVal, index)之前会有什么问题如果val恰好等于lastVal也就是你删除的就是最后一个元素那么put(lastVal, index)会把刚删掉的映射又加回来但因为后面还会执行valToIndex.remove(val)最终结果还是正确的。真正的问题出现在反向如果你先remove(val)然后在覆盖数组时没有更新lastVal的映射那么数组里lastVal的位置变了map 里却还记着旧下标下次删除它时就会定位错误。这种 bug 非常隐蔽因为它不是必现而是跟具体操作序列有关。正确的心法是先把数组覆盖好再把映射关系修正完整最后才删旧映射。这个顺序背后的逻辑是“先让数据本体保持一致再让索引表保持一致最后清理残留”。养成这种习惯删除类操作普遍不容易出问题。还有一个细节当index lastIndex时这套流程也完全没问题。values.set(index, lastVal)是自己覆盖自己put(lastVal, index)是原样更新同一个映射最后remove(lastIndex)和remove(val)分别清理数据。实测下来不会有异常。4. 复杂度分析与正确性论证4.1 时间复杂度分项拆解操作时间复杂度说明insert均摊 O(1)containsKey 和 put 平均 O(1)add 到数组末尾均摊 O(1)触发扩容时可能 O(n)但均摊到每次操作是 O(1)remove平均 O(1)get、set、remove(list末尾) 都是 O(1)HashMap remove 平均 O(1)getRandomO(1)nextInt 和 arrayList.get 都是 O(1)要注意“O(1)”在这里是指平均时间复杂度。HashMap 的 put/get 在最坏情况下哈希冲突严重时会退化到 O(n)但工程实现的哈希表通过扩容和扰动函数把这种情况的概率压得非常低面试里回答“平均 O(1)”即可。ArrayList 的扩容从单次操作看可能 O(n)但用摊还分析每次 add 的平均代价就是 O(1)。4.2 空间复杂度空间开销是 O(n)n 是当前集合中元素个数。数组本身存 n 个元素哈希表存 n 对键值两份结构都在维护同一份数据空间翻倍是这个方案的必然代价。好在保存内容是同一份引用没有额外的对象开销实际内存增长是线性的。4.3 随机均匀性为什么是天然成立的getRandom()的均匀性依赖于两个前提第一数组必须是紧凑的也就是所有有效元素都在0到size - 1的连续下标上。这个前提靠删除时的“末尾覆盖”保证数组永远没有空洞。第二随机数生成范围必须精确等于数组长度。random.nextInt(values.size())生成的是[0, size)的整数每个整数概率相等每个下标对应一个元素所以每个元素被选中的概率也就是1/size。如果你用Math.random() * values.size()再转 int虽然概率上也是均匀的但会遇到浮点数精度问题而且边界处理不小心容易越界。我强烈建议直接nextInt(size)简洁安全。5. 易错点与避坑指南5.1 别用 list.remove(index) 删中间元素这是最经典的低级错误。有人会觉得“既然我都知道下标了直接values.remove(index)不就行了吗”问题在于ArrayList 的remove(int index)删除的是 index 这个位置但为了维持数组连续它必须把后面的所有元素往前挪一格。这个操作的复杂度是 O(n)不能通过测试。更坑的是 Java 里的重载问题如果集合装的是Integer你写values.remove(val)的时候Java 会优先把val当成Object来匹配执行的是remove(Object o)也就是删除“值等于 val 的元素”而不是你想要的“删除下标为 val 的元素”。这会导致删错元素而且即便逻辑碰巧对上了也是 O(n) 遍历删除。正确姿势永远是两层配合用 map 定位下标用values.remove(values.size() - 1)删末尾。5.2 删除“最后一个元素本身”时的边界处理前文提到过如果当前集合只有一个元素或者待删除的 val 恰好就是最后一个元素整段删除逻辑依然成立。我特意拿这一个场景测试过集合只有一个元素[5]remove(5)。index 0lastIndex 0lastVal 5。values.set(0, 5)无变化。valToIndex.put(5, 0)无变化。values.remove(0)清空数组。valToIndex.remove(5)清空映射。一切正常。有人为了“预防”这种场景会在代码里加if (index lastIndex)的特殊分支但这是完全多余的反而容易因为分支处理不一致引入新 bug。5.3 插入时忘记判重会导致集合语义被破坏如果不加containsKey判断插入重复值时会执行两次values.add(val)但 map 里的映射被覆盖成同一个下标。结果数组里有两个相同值map 只记录了一个位置整个集合出现重复元素随机概率也不再是每个独立元素等概率了。这个 bug 特别容易出现在你从“普通 set 操作”转换思路的时候。记住insert返回 false 表示数据没有任何变化这是一个很重要的语义。5.4 getRandom 的越界风险还有一次我把随机范围写成了values.size() 1想着“多一个余量更安全”结果当随机到最后一个额外下标时直接IndexOutOfBoundsException。Random.nextInt(bound)的边界在最左边是 0在最右边是 bound - 1永远拿不到 bound。你想从 0 到 size-1 里选就写nextInt(size)不要多此一举。另外当 size 很大时Math.random()的浮点精度理论上会产生极小的偏差虽然实际影响不大但nextInt的实现用的是整数运算没有这个问题。6. 常见追问与变体扩展6.1 如果允许重复元素怎么办这是 LeetCode 381题目叫Insert Delete GetRandom O(1) - Duplicates allowed。思路从“值到下标的单一映射”升级为“值到多个下标的集合映射”。结构变成HashMapInteger, SetIntegerkey 是元素值value 是所有出现该值的下标的集合。插入时如果值已存在只需要新增一个下标删除时从该值的下标集合中取出任意一个位置比如set.iterator().next()依然用末尾元素占位覆盖然后更新末尾元素的下标集合最后清掉被删下标。这个变体最大的坑在于一个值可能同时出现在多个位置更新下标时要注意不要让集合里残留失效下标。我在实测时因为这个 bug 翻车过一次排查了很久才发现是HashSet里存了旧坐标后来换了LinkedHashSet拿“任意一个可删除下标”也更稳定。6.2 面试官问“为什么不用 LinkedHashMap”这是一个很常见的追问。LinkedHashMap确实保证插入顺序也支持 O(1) 的 get/put/remove但问题是它不支持下标访问。“随机取一个”意味着你要等概率地选一个 key这在迭代器层面做文章很别扭。要么 resort 到转数组要么记录 size 后用某种固定步长遍历这两种都会破坏等概率或者变成 O(n)。所以这道题的“标准解”就是 HashMap ArrayListLinkedHashMap 在这道题里不是正确选型。6.3 与 LRU、LFU 设计题放在一起看刷到后期你回头看会发现设计题的结构是有套路的LeetCode 146 LRUHashMap 负责快速定位节点双向链表负责维护使用顺序。LeetCode 380HashMap 负责定位下标ArrayList 负责随机访问。LeetCode 381HashMap 映射到下标集合ArrayList 负责随机访问。共同点都是用哈希表解决“查找”问题用另一个有序/可索引结构解决“顺序”或“随机”问题。你只要把这个心智模型记住再遇到类似设计题思路会顺畅很多。顺便说一句如果你刚开始刷题380 可以作为设计题的入门如果刷到中后期可以和同样出现在热门题里的 994 腐烂的橘子多源 BFS、073 爱吃香蕉的狒狒二分答案、基本计算器栈模拟放在一起横向对比会发现这些高频题其实分别考察了数据结构和算法里几个完全不同的侧面做题的感受会很不一样。7. 实测踩坑与刷题心得7.1 手动构造测试序列最稳妥LeetCode 自带的测试用例不一定能覆盖所有边界。我自己写完代码后会手动构造几组操作序列来验证连续插入大量数字观察是否存在覆盖旧映射的问题。先插后删再插同一个值确认 insert 返回值和内部状态与“新插入”一致。删除集合最后一个元素后立刻 getRandom确认不会越界。删除一个不存在的值确认返回 false 且不改变内部结构。大规模随机操作序列用纯 Java 的HashSet做对照校验每次 insert/remove 的返回值是否一致。其中最有效的就是“对照实验”找另一个实现相同逻辑的简单结构让它们俩执行同一串随机操作任何一步返回值不一致都能立刻暴露问题。7.2 这题真正难的地方是“组合思维”从我带人的经验看很多人第一次做这题会急于写代码结果写到 remove 就卡住了。这很正常因为前面说了单靠一种数据结构就是凑不齐三个 O(1)你必须有意识地跨出“一种结构搞定一切”的惯性。反过来一旦你理解了“哈希表定位 数组承载”这个组合下次再看到“O(1) 时间完成 XX XX”的设计题你的第一反应就不再是“这怎么可能”而是“那我需要哪两种结构来互相补位”。7.3 小技巧写完了顺手把 map 和 list 的关系画出来我在做这种双结构设计题的时候会习惯性地在纸上画两列左边是数组右边是 map 的键值对。然后拿一组样例数据一步步手工模拟插入、删除、再插入。虽然听起来慢但效率极高因为大多数 bug 都是因为“脑子里自动脑补了某个结构同步更新”实际代码里根本没同步。这道题做完以后建议顺手去看一眼 381 的双倍题解理解一下从单个下标映射到下标集合映射的变化这样你对“哈希表能映射到什么粒度”会有更深的理解。我第一次 AC 这道题的时候超时了一次原因就是 remove 用了values.remove(index)而不是交换删除。当时系统报出超时我还以为是随机数的问题回头逐行看代码才意识到中间删除是 O(n)。从那之后我对“数组删除尾元素 O(1)、删除中间 O(n)”这个常识有了肌肉记忆。希望读到这里的你也能一步到位不用像我一样先交一次学费。