Swift 里写一个支持重复元素的 O(1) 随机集合是我最近在准备算法面试时重新捡起来做的一道题。题目本身不算难实现insert、remove、getRandom三个接口要求平均时间复杂度为 O(1)而且允许相同元素出现多次。网上的讨论大多集中在 C 或 Java 版本Swift 版本里Hashable约束、字典判空、删除时的索引更新顺序几乎没有文章讲透。我实际跑了一遍还在重复值场景踩过一次索引错乱的坑最终把完整实现、设计思路和排错过程一起整理出来希望对准备面试或者需要在工程里做随机抽样的人有帮助。这道题适合谁呢一是准备大厂算法面试、想搞懂 LeetCode 380/381 这类题目的人二是在做游戏卡池、抽样工具、可放回随机选择等功能的开发者三是对“数组 哈希表”这种经典数据结构组合感兴趣的人。下面直接从设计难点讲起。1. O(1)随机集合的难点到底在哪1.1 随机访问决定了存储主体必须是数组先看最朴素的需求随机获取一个元素并且每次获取时集合中每个已有元素被选中的概率要均等。这看起来是个很简单的操作但如果你只用一个Set或Dictionary来存数据就会发现“均匀随机取出一个元素”并不好办。Swift 的Set虽然支持 O(1) 的插入、删除和查找但它是一个哈希表结构内部元素的存储顺序由哈希值决定并不保证随机分布。调用set.first拿到的只是“哈希桶里的第一个”既不是均匀随机的也不能当作随机结果。换句话说哈希表擅长回答“某个值在不在”但回答不了“给我一个等概率的随机成员”。数组就不一样。所有元素按下标连续排列array[randomIndex]本身就是一次 O(1) 访问配合Int.random(in: 0..array.count)就能严格做到等概率取槽位。所以这道题的主体存储必须是数组而不是集合。这一条几乎是所有解法的基础。1.2 “允许重复”为什么是质变而不是简单放开限制LeetCode 380 是不允许重复的版本这个版本只需要一个[值: 下标]的字典每个值对应数组里的唯一位置。删除时找到这个值对应的下标把它和数组最后一个元素交换再删除尾部即可。到了允许重复的 381问题就不一样了。同一个值可能出现在数组的多个下标上字典里一个 key 对应的 value 不能再是单个Int而必须是一组下标。这就是“允许重复”带来的质变本来一个值只有一个“住址”现在一个值有多个“住址”删除的时候要能快速任选其中一个住址并保持其他住址仍然有效。还有一个容易被忽略的点允许重复的集合语义上已经不是普通的“集合”而是一个多重集合multiset也叫 bag。插入同一个值两次集合里就有两个相同的元素。因此随机抽取时出现次数多的值被抽中的概率也应该更大。后文会看到用数组槽位来存储天然就满足这种权重。1.3 三个约束条件共同指向的方案轮廓把三个接口的要求放在一起看insert要在 O(1) 内完成。数组尾部追加是均摊 O(1)字典记下标也是 O(1)。remove要删除指定值的任意一个出现位置。如果直接删除数组中间的元素后续所有元素都要左移O(n) 就超了。于是必须用经典的“尾部交换法”把待删位置上的元素和数组最后一个元素交换然后删除尾部。这样数组不需要整体搬移。getRandom要 O(1) 随机访问。数组下标随机即可。但尾部交换法有一个代价数组内部元素的相对顺序会被打乱。比如删除下标 0 的元素时会把尾部元素搬运过来原来的顺序就变了。这一点对普通数组是坏事却对本题没有影响因为题目只要求“随机取一个元素”不要求按插入顺序遍历。搞清楚“顺序可牺牲、随机和 O(1) 不可牺牲”这个交换条件方案的轮廓就出来了。2. 数组主存哈希索引这个组合为什么成立2.1 整体结构设计与 Swift 类型声明既然决定用数组存储元素本体用字典存储“值到下标的映射”那 Swift 的类型就非常自然final class RandomizedCollectionT: Hashable { private var values: [T] [] private var indexMap: [T: SetInt] [:] // 后续核心方法都围绕这两个属性展开 }values是真正装数据的地方所有元素往里放随机访问也在它上面做。indexMap的 key 是元素值value 是SetInt存的是该值在values中出现的所有下标。这里用Set而不是Array存下标是一个细节下面展开讲。2.2 为什么哈希表的 value 要存“索引集合”而不是直接计数有人可能会想允许重复的话字典里存[T: Int]计数不就行了比如插入 1 两次dict[1] 2。这个方案做插入和 getRandom 是没问题的但做删除会卡住。删除一个值的时候我们必须知道它在数组里的具体位置才能把这个位置和尾部元素交换。如果只存计数值就只知道“数组里有 2 个 1”不知道这 2 个 1 分别住在 0、2 还是 1、5。要从头扫描数组才能定位这样删除就不是 O(1) 了。所以要存真正的索引而不是计数器。indexMap[1] [0, 2]意味着下标 0 和 2 处的元素都是 1。插入时往集合里追加一个下标删除时从集合里任选一个下标去交换。这样“值到位置”的映射始终精确删除才谈得上 O(1)。2.3 Set 存索引的优势Swift 的Set底层也是哈希表。用SetInt存下标有三个具体好处插入新下标是 O(1)。每次往数组尾部追加元素得到的新下标直接塞进集合。删除指定下标是 O(1)。set.remove(index)按值删除不需要像数组那样查找元素位置再搬移。无序性反而不碍事。我们删除某个值时只需要它任意一个下标不需要“最小的”或“最新的”。Set没有顺序popFirst()就返回任意一个元素正好合适。这里放一张三种存储方案的对比能更清楚地看出为什么是SetInt存储方案插入下标删除指定下标随机访问[T: Int]单个下标O(1)无法处理重复值依赖值对数组[T: [Int]]有序数组O(1) 尾部追加O(n) 数组删除需要搬移可以[T: SetInt]哈希集合O(1)O(1) 平均可以直观理解就是把“下标”也当成一组元素来管理它本身需要频繁增删而且每次只取一个不关心顺序这正是一个集合的典型使用场景。用它整个删除链路里所有操作都控制在 O(1)。在进入核心实现前再提醒一个 Swift 特有的点Dictionary的 value 是结构体dict[key]返回的是一个值副本不能直接对它调用 mutating 方法。换句话说写成dict[key]!.insert(newIndex)编译器会报错。正确做法是把集合取出来存进var修改完再写回去。后面的代码里你会反复看到这个模式。3. 核心实现insert、remove、getRandom 的完整代码3.1 insert先判断“之前是否存在”再记录下标题目要求 insert 返回一个布尔值如果集合中此前没有这个值返回 true如果此前已经存在无论有几个返回 false。因此插入的逻辑分三步看看indexMap[val]是否存在且非空。把新元素追加到values尾部拿到新下标。把这个下标记录到indexMap[val]中如果这个值之前不存在就新建一个集合。实现如下discardableResult func insert(_ val: T) - Bool { if var indices indexMap[val] { // 集合里已经有这个值返回 false let existed !indices.isEmpty indices.insert(values.count) indexMap[val] indices values.append(val) return !existed } else { // 第一次出现创建索引集合 indexMap[val] [values.count] values.append(val) return true } }注意这里用values.count作为新元素下标因为 append 之前数组长度正好等于新元素将要占用的下标。append 之后下标就变成了count - 1但那时长度已经变了。我的习惯是先算下标再 append逻辑上更直接。还有一种边界情况indexMap[val]这个 key 还在但它的集合是空的。什么时候会出现呢当你把所有val都删除后如果删除时没有把空集合从字典里清掉就会留下一个key - []。所以代码里专门用!indices.isEmpty判断是否真的存在。这也是一个很容易踩的细节字典“有 key”不等于“集合里有元素”。3.2 remove尾部交换法的正确顺序删除是这道题的核心也是坑最多的地方。先讲清楚算法流程再给出代码。假设要删除的值是val从indexMap[val]的索引集合里任意取出一个下标pos这就是待删元素在数组中的位置。记录当前数组最后一个元素的下标lastIdx values.count - 1以及最后一个元素值lastVal values[lastIdx]。如果pos lastIdx说明要删的恰好是数组尾部元素不需要任何交换直接删字典索引和数组尾部即可。如果pos ! lastIdx就把values[lastIdx]搬到values[pos]同时更新lastVal的索引集合把lastIdx删掉把pos加进去。最后从values删除尾部并清理字典中的空集合。这里最需要小心的是val lastVal的情况。如果尾元素和待删元素值相同它们共享同一个字典 key更新索引时需要合并处理绝不能分成两个互不关联的步骤去写回。我的实现如下discardableResult func remove(_ val: T) - Bool { guard var indices indexMap[val], let pos indices.popFirst() else { return false } let lastIdx values.count - 1 let lastVal values[lastIdx] if pos ! lastIdx { // 把尾部元素搬到待删位置 values[pos] lastVal if lastVal val { // 关键分支尾元素和待删元素是同一个值 // indices 是 [val] 的索引集合popFirst 已经移除了 pos // 需要把 lastIdx 从集合里删掉再把 pos 加回来 indices.remove(lastIdx) indices.insert(pos) } else { // 不同值分别维护两个 key 的索引 var lastIndices indexMap[lastVal]! lastIndices.remove(lastIdx) lastIndices.insert(pos) indexMap[lastVal] lastIndices } } if indices.isEmpty { indexMap[val] nil } else { indexMap[val] indices } values.removeLast() return true }这段代码里popFirst()是一个很妙的小操作。它把“取出任意一个下标”和“从集合中删除这个下标”合并成一步返回值是被取出的元素同时原集合不会再包含它。接下来indices这个可变副本就是“删除 pos 之后的剩余集合”后面可以直接复用不必再做一次remove(pos)。为什么lastVal val时要单独处理用一个例子推演假设当前数组是[1, 2, 1]字典是1 - {0, 2}、2 - {1}。删除 1pos假设被popFirst选为 0lastIdx 2lastVal 1。此时values[0]被覆盖成 1数组依然是[1, 2, 1]因为两个位置的值相同。索引集合需要从{0, 2}变成{0}下标 2 没了下标 0 保留。但popFirst已经把 0 从集合里拿走了所以此时集合是{2}。必须手动remove(lastIdx)变成空集再insert(pos)把 0 加回来才得到{0}。如果直接走“不同值”的通用分支就会用一个lastIndices副本更新完写回再用另一个副本覆盖最终结果完全错误。这个边界分支不是数学上画蛇添足而是真正决定代码是否正确的关键。下面第 4 节再专门复盘我踩过的错误版本。3.3 getRandom一个默认随机源就够了getRandom 是最简单的部分。数组里每个槽位都是有效元素直接用系统随机源生成下标func getRandom() - T { precondition(!values.isEmpty, RandomizedCollection is empty.) return values[Int.random(in: 0..values.count)] }Int.random(in:)默认使用 Swift 的SystemRandomNumberGenerator无需额外配置。如果希望在测试时复现随机序列还可以提供支持注入随机源的版本func getRandomRNG: RandomNumberGenerator(using generator: inout RNG) - T { precondition(!values.isEmpty, RandomizedCollection is empty.) return values[Int.random(in: 0..values.count, using: generator)] }用自定义 RNG 做单元测试时这个重载能保证同样的种子跑出同样的序列非常实用。默认的getRandom()调用内部会创建一个系统随机源对绝大多数场景都够用。4. 最容易翻车的删除顺序一次真实踩坑4.1 我最初写的错误版本第一次实现时我没有单独处理val lastVal的情况而是按照“直觉”写了一个通用顺序先更新尾部元素的索引再从待删值的集合里删除 pos。代码逻辑大概是这样的// 错误版本仅用于展示问题 if pos ! lastIdx { values[pos] lastVal var lastIndices indexMap[lastVal]! lastIndices.remove(lastIdx) lastIndices.insert(pos) indexMap[lastVal] lastIndices var valIndices indexMap[val]! valIndices.remove(pos) indexMap[val] valIndices } else { ... } values.removeLast()这个版本在处理“待删值不等于尾部值”时是没问题的。比如数组[3, 5, 4]删除 4选中的 pos 是 2pos 等于 lastIdx直接删删除 3选中的 pos 是 0lastVal 是 4先搬 4 到数组开头更新 4 的索引再删 3 的索引皆大欢喜。但一旦遇到重复值整个索引体系就崩了。4.2 重复值场景下的完整错误推演用最小用例慢慢走一遍。初始状态values [1, 2, 1] indexMap { 1: Set([0, 2]), 2: Set([1]) }调用remove(1)假设pos 0lastIdx 2lastVal 1。错误版本在val lastVal时会发生什么第一步values[0] 1数组没有任何肉眼可见的变化因为覆盖前后的值都是 1。第二步取出lastIndices indexMap[1]也就是{0, 2}。删除lastIdx也就是 2得到{0}再插入pos也就是 0还是{0}。此时indexMap[1]被写成了{0}。第三步取出valIndices indexMap[1]。注意这时的字典里 1 对应的已经是上一步写进去的{0}如果你在实现中是用两个临时变量分别快照就会出现另一个混乱两个临时变量都持有{0, 2}的旧副本最后谁写回谁覆盖谁完全取决于代码顺序。无论哪种写错最终都会出现类似的症状数组执行removeLast()后变成[1, 2]但字典里 1 对应的下标集合要么是{2}这种明显越界的要么是空的反正和实际数组对不上。下次 getRandom 一旦随机到越界下标整个程序直接崩溃。问题本质是当val lastVal时两个逻辑步骤操作的是同一个字典 key如果你把它们当成两个独立 key 来写回先后两次写回必然发生覆盖。要么保留第一次的结果要么保留第二次的结果总有一个错。正确思路是意识到这是一个合并操作集合里做过一次 popFirst又搬了一次尾部元素最终的净效果应该在同一个集合里完成。4.3 用微型断言验证实现吃了一次亏之后我养成了一个习惯写完这种“数组 哈希表”同步维护的数据结构先写一个全量校验函数再跑操作。校验思路很简单重新遍历数组重建一套索引字典和当前的indexMap对比func validate() - Bool { var rebuilt: [T: SetInt] [:] for (i, v) in values.enumerated() { rebuilt[v, default: []].insert(i) } return rebuilt indexMap }这个函数本身是 O(n) 的生产环境不建议用但调试阶段价值极大。每次 insert、remove 后立刻调用能快速暴露“数组和字典不同步”的问题。我当时就是靠它在错误版本上稳定复现了崩溃又在修正版本上确认了所有操作后仍然validate()为 true。再给一组经典的测试用例覆盖重复值相等场景var rc RandomizedCollectionInt() assert(rc.insert(1) true) // 首次出现 assert(rc.insert(1) false) // 已经存在 assert(rc.insert(2) true) assert(rc.validate()) assert(rc.remove(1) true) // 删除重复值之一 assert(rc.validate()) assert(rc.insert(1) false) // 集合里应该还有 1 assert(rc.validate()) assert(rc.remove(2) true) assert(rc.validate()) assert(rc.remove(1) true) // 删除最后一个 1 assert(rc.validate()) assert(rc.remove(1) false) // 集合里已经没有 1 了 assert(rc.validate())特别注意最后的remove(1) false它要求删除前把所有 val 对应的空集合清理掉否则indexMap[val]虽然存在但为空就会被误判为 true。我在第 3 节的代码里已经用guard var indices indexMap[val], let pos indices.popFirst()堵死了这个问题因为空集合的popFirst()返回 nil自然返回 false。5. 复杂度与正确性验证5.1 为什么这些操作严格是 O(1)抛开复杂度证明直接看实现insert数组尾部 append 均摊 O(1)字典取值、插入集合 O(1)。removepopFirst()从集合取任意元素 O(1)数组尾部removeLast()O(1)更新字典索引集合 O(1)。唯一需要注意的是数组尾部 append 时如果容量不够会发生扩容需要把所有旧元素拷贝到新缓冲区单次操作可能是 O(n)但它平摊到多次插入后均摊成本仍然是 O(1)。这正是“均摊 O(1)”的标准语义。getRandomInt.random(in:)O(1)数组下标访问 O(1)。值得注意的是这里所有 O(1) 都是“平均意义”上的 O(1)不是“最坏情况严格 O(1)”。因为哈希表在极端哈希冲突下可能退化但工程上Swift.Dictionary和Set的哈希实现分布足够均匀竞赛和实际使用都按平均 O(1) 看待。5.2 构造极端用例做测试写完算法后我用几类极端序列做了压测重点不是跑分而是验证逻辑不崩连续插入同一个值 10 万次再连续删除同一个值 10 万次。这一步主要验证val lastVal分支在极端密集场景下的稳定性。先插入 10 万个不同值再从尾部倒着删除。这是pos lastIdx最频繁出现的场景验证空集合清理逻辑。交替插入和删除、随机穿插 getRandom。这一步最容易暴露随机顺序下的索引错乱。在上面这些测试里只要每次操作后调用validate()都能保证数组和字典完全同步。另一个简单的观察是values.count永远等于indexMap所有 value 集合的元素数量之和。这个恒等式在调试过程中也很管用一旦不相等说明某步索引维护出了问题。5.3 随机均匀性检查getRandom 的均匀性其实不需要随机数统计来证明因为每个数组槽位被选中的概率都是1 / values.count没有任何额外条件判断。如果你想自己在测试中验证可以用一个简单统计var frequency: [Int: Int] [:] for _ in 0..100000 { let v rc.getRandom() frequency[v, default: 0] 1 } // 每个值的频率应接近 values 中该值的数量 / total有一个容易被忽略的语义点这个 getRandom 是“按槽位等概率”不是“按唯一值等概率”。数组 [1, 1, 2] 里抽到 1 的概率是 2/3抽到 2 的概率是 1/3。对允许重复的集合来说这个行为才是正确的一个值出现次数多被抽中的概率就大天然实现了按出现次数加权的随机抽样。如果你期望每个唯一值等概率就需要额外引入一个“唯一值列表”或单独做加权选择这是另一个扩展话题第 6 节会提到。6. 从刷题到工程泛型化、线程安全与扩展方向6.1 泛型化与自定义元素的 Hashable上面所有代码都是泛型T: Hashable写的所以结构上可以直接塞进工程。Swift 对自定义结构体使用这个容器时通常只需要让结构体遵守Hashable编译器会自动合成和hash(into:)struct Token: Hashable { let symbol: String let exchange: String } var tokens RandomizedCollectionToken() tokens.insert(Token(symbol: BTC, exchange: A))真正需要注意的是引用类型class。如果元素是 NSObject 子类哈希值由hash属性决定而hash又由对象的属性派生那千万不要在插入容器后修改对象的属性。哈希值一变字典里就再也找不到它了。工程上的建议很简单作为 key 的对象要么设计成不可变类型要么只使用let属性和值类型。还有一个 Swift 特有的坑Dictionary 的 value 是结构体副本。如果你的 key 类型本身是结构体而 value 是SetInt每次读取字典后修改再写回是比较自然的模式。如果忘了写回你的修改只发生在临时副本上字典完全没有变化。这类 bug 不会报错但是数据会静默丢失非常隐蔽。6.2 多线程环境下的一个简单加固如果要放到 App 里被多个线程访问裸的数组和字典都不是线程安全的。最直接的做法是用一把锁包住所有公开方法private let lock NSLock() discardableResult func insert(_ val: T) - Bool { lock.lock() defer { lock.unlock() } // 原插入逻辑 return true }其他方法同理。加锁的常数开销很小不会改变 O(1) 的复杂度但能避免数据竞争导致的崩溃。Swift 5.5 之后也可以用 actor 来封装不过 actor 会改变调用方式需要await在普通同步场景里 NSLock 反而是更轻的选择。6.3 扩展到加权随机与可放回抽样由于这个结构本质上是“数组主存 下标索引”你从数组槽位随机抽取时天然就是按重复次数加权的抽样。很多场景其实需要这种能力游戏卡池里同一个道具可以配置多个掉落位掉落概率等于出现次数占比。文本 bag-of-words 模型里对词表做随机采样出现频率高的词被采样概率更高。蒙特卡洛模拟里从一组带重复的样本点中做可放回抽样。如果你反过来需要“唯一值等概率”而不是“槽位等概率”可以在indexMap.keys上做随机但Dictionary.Keys本身不支持 O(1) 随机选一个 key。那就要额外维护一个uniqueValues: [T]数组和[T: Int]的唯一值位置映射删除时如果某个值的索引集合变空再把它从唯一值数组里删除。复杂度依然可以做到 O(1)但代码体量会多不少。另外一个常见的变体是“带权重随机删除”比如想按权重删除某个值的元素而不是任意删除那就不能用popFirst()随意取一个下标。需要在SetInt基础上增加权重信息或者用有序结构记录键的权重顺序。这个扩展方向很值得做但已经超出今天这道题的范围了。最后再分享一个我实际调试中的体会这类由多个数据结构组合而成的容器最难的往往不是某个算法的设计而是“同步状态的时机”。数组、字典、集合三者的状态在每一步操作后都必须保持一致。哪怕是 Swift 的popFirst()这种看起来顺手的小操作背后的“取出并删除”语义也会影响后续流程。建议你拿到代码后一步一步用笔在纸上画一个两位数的小数组把 insert 和 remove 的每一步索引变化都写出来跑通之后再看复杂用例会顺手很多。这个习惯比我一开始上来就写完整实现要省力。