题干与适用场景
集合需要判断成员、插入、删除，并从当前元素中等概率返回一个值。哈希表适合成员定位，动态数组适合按随机索引取值；难点是删除中间元素会留下空洞。
面试官考察点
- 是否组合哈希表与数组，而非强行使用单一结构。
- 是否保存“值到数组索引”的映射，并在交换后同步更新。
- 是否理解平均 O(1) 与数组扩容的摊销含义。
- 是否明确 getRandom 的等概率和重复值语义。
- 是否处理空集合、删除不存在元素和并发边界。
回答前需要澄清的问题
- 元素是否唯一？允许重复时需要把映射改为索引集合。
- getRandom 要求等概率，还是返回任意随机元素即可？两者实现验收不同。
- O(1) 是平均摊销还是严格最坏情况？哈希冲突策略会改变承诺。
- 返回的是值还是句柄？对象可变时需要定义哈希和相等性。
- 是否要求线程安全、固定内存或可复现随机源？
30 秒回答框架
“我维护数组 items 和哈希表 indexOf。插入时把新值放到数组尾部并记录索引；随机取值用均匀随机下标。删除时找到目标索引，把尾元素搬到该位置，更新尾元素索引，再弹出数组尾部并删除目标映射，因此避免 O(n) 的中间搬移。哈希和动态数组操作按平均摊销 O(1) 计算；空集合返回约定错误，重复值则把映射改成索引集合。”
分步骤深入解答
步骤 1：建立不变量。 对每个值 v，indexOf[v] 指向 items 中唯一位置；数组没有空洞，所有索引都在范围内。
步骤 2：实现 insert。 若映射已有值，按题意返回 false；否则追加到尾部并写入索引，平均 O(1)。
步骤 3：实现 remove。 取目标索引 i 和尾索引 last。若 i !== last，把尾值写到 items[i] 并把它的映射改为 i；随后弹尾并删除目标映射。
步骤 4：实现 getRandom。 对非空数组取均匀下标；Python 文档的 choice 说明序列元素等概率，不能从哈希表迭代顺序推断随机性。
步骤 5：说明复杂度。 哈希查找、尾部追加、交换和弹尾平均摊销 O(1)，数组与映射空间 O(n)。哈希最坏冲突或扩容暂停需要在严格 SLO 下另行讨论。
步骤 6：处理重复值。 将 indexOf[v] 改成存放多个索引的集合；删除一个实例时先移除其索引，再用同样的尾部交换更新集合。
步骤 7：验证边界。 测试空集合、单元素、重复删除、删除尾部、连续扩容和固定种子；运行大量 getRandom 检查频数接近均匀，而不是只断言返回值属于集合。
高质量示范回答
“我用数组保存当前值，用哈希表保存每个值的数组索引。删除中间项时，把尾项搬过来并更新它的索引，再删除尾部；这样没有元素需要整体左移。随机取值从数组的均匀随机下标读取，所以每个唯一值等概率。这个 O(1) 是哈希操作和动态数组扩容的平均摊销保证；若允许重复值，我会把单索引映射扩展成索引集合，并重新定义删除一个实例的语义。”
常见错误
- 只用哈希表 → getRandom 需遍历全部键 → 增加紧凑数组。
- 删除后整体左移 → 删除变成 O(n) → 交换尾元素。
- 交换后忘记更新尾值索引 → 后续删除定位错误 → 把映射更新视为同一原子步骤。
- 从哈希迭代器取随机项 → 顺序不保证均匀或稳定 → 按数组索引采样。
- 把平均 O(1) 宣称为最坏 O(1) → 忽略冲突和扩容 → 明确摊销和实现前提。
追问及应对
追问 1：删除数组最后一个元素时怎么办？
目标索引等于尾索引，直接弹尾并删除映射，无需交换。
追问 2：如何支持重复值？
映射保存值对应的索引集合；交换尾元素后同步移除旧索引、加入新索引，再从目标集合删除一个实例。
追问 3：如何证明 getRandom 等概率？
数组每个位置只保存一个当前实例，随机下标在 0..n-1 均匀，因此唯一值各占一个位置时等概率。
追问 4：哈希冲突会破坏 O(1) 吗？
平均复杂度依赖负载因子和哈希质量；严格最坏情况需要树化桶、随机化哈希或不同数据结构。
追问 5：如何并发读取和删除？
读随机下标与删除交换必须使用同一锁或版本校验，否则读者可能拿到已弹出的索引。
追问 6：如何做统计测试？
固定集合运行大量抽样，对每个值计数并设置统计容差；同时验证每次返回值仍存在于集合。