Swift实现允许重复的O(1)随机集合：数组+哈希表+下标集合

1. 为什么需要这个结构从问题到设计思路我第一次真正对“允许重复的 O(1) 随机集合”产生兴趣倒不是因为 LeetCode 第 381 题本身而是后来在一个抽奖系统里被迫亲手实现它。业务场景特别朴素奖品池里同一个奖可以出现多份运营随时会往池子里加奖品、下架某个具体奖品而每次抽奖必须在几十万甚至上百万条记录里瞬间完成随机命中。如果只是拿一个数组硬存随机取值确实很快但删除一个非末尾奖品时线性查找加元素前移带来的 O(n) 开销在百万级数据下基本等于慢性自杀。这时候“插入、删除、随机取值三个操作全部 O(1)”这个从算法题里走出来的需求就变成了实打实的业务刚需。这个结构要解决的核心问题其实就一句话在允许重复元素的动态集合中让插入任意值、删除任意值、随机取一个值这三个操作都达到均摊 O(1)。注意这里的“重复”是关键同一个数值可以同时存在多份每一份都是独立实例。熟悉 LeetCode 380 不重复版本的同学都知道那个版本只要维护“值 - 唯一索引”的映射就够了一旦允许重复单个索引无法描述一个值因为它可能散落在数组里的五个位置。于是整个设计难度就从“数组 哈希表”升级成了“数组 哈希表 每个值的位置集合”。这篇文章既适合正在刷题的朋友也适合在做抽奖、卡池、测试分流这类业务的开发者。我会用 Swift 从零实现一版从数据结构选型、每个方法的边界处理、到实际调试踩过的坑全部展开来讲。看完你不仅能过题还能放心把这套实现搬进自己的生产项目里。1.1 为什么不能只用数组也不能只用哈希表先做一次“反证法”式的推演。如果只用数组随机取值是完美的randomElement()严格 O(1)但删除任意值需要先找到它的下标数组查找避免不了遍历就算你强行接受了查找的代价删除中间元素还会触发后续元素的大规模前移这是 O(n) 的移动成本在频繁删改的场景里直接崩盘。反过来只用哈希表插入和删除都能通过哈希定位做到均摊 O(1)但哈希表没有下标概念你没法让它在等概率的前提下快速随机挑出一个元素。虽然可以遍历所有 key 再随机选但那是 O(k)而且哈希表内部顺序和存储桶分布让均匀性根本得不到保证。所以自然解法就是把两者拼起来数组负责随机访问和顺序存储哈希表负责“值到位置的映射”让删除也能快速定位目标位置。数组尾部增删是 O(1)删除任意位置时把尾巴元素搬过来填空再删尾巴就把“任意位置删除”伪装成了“尾部删除”。这个技巧英文叫 swap-remove中文圈子里一般叫交换删除。允许重复场景下这个拼法比不重复版本多了一个关键改动哈希表里存的不是单个下标而是一组下标。因为同一个值可能出现多次每个出现位置都要能被快速找到和移除。1.2 一个帮你建立直觉的生活类比我把这个结构想象成带检索目录的图书馆书库。书架上是一排书这就是数组平时随机取书时闭着眼睛随便指一个位置拿到哪本算哪本。目录卡片是“书名 - 这本书所在的所有架位”这就是哈希表用来快速定位指定书目。如果要借走一本书先翻目录拿到一个架位编号把目标书抽出来再从书架最后一格搬一本过来填空更新目录最后把空出来的末尾划掉。整个过程只动书架尾部一格和目录上的几条记录完全不需要把整排书重排一遍。这个类比的精妙之处在于它能帮你直观理解“交换删除为什么不会破坏均匀性”书架位置总数在变化但每个位置始终对应一本具体的书随机取值只关心长度不关心书与书的排列顺序。袋子里装的球顺序无关紧要关键是球的种类和数量保持正确。2. 数据模型与 Swift 类型设计明确了轮廓接下来就是把想法落成 Swift 类型。我最终采用的设计是用[Int]数组values存储所有元素允许重复用[Int: SetInt]字典indexMap存储“值 - 该值当前占用的下标集合”。先把下标集合选成SetInt而不是[Int]这就是第一个关键决策。原因很简单SetInt的插入、删除、判存在都是均摊 O(1)而且我们完全不在乎下标之间的顺序只要能快速增删即可。数组存下标只有插入是 O(1)删除中间元素是 O(n)在频繁增删的重复场景里用数组存下标等于把一个本来 O(1) 的操作硬生生拖回 O(n)。2.1 为什么必须是“值 - 下标集合”而不是“值 - 计数”有人可能觉得用“值 - 出现次数”来计数不是更轻量吗存在就加一删除就减一随机取值时再根据计数重建下标。这个思路在只做存在性判断的场景没问题但一旦要精确删除一个确定的实例计数法就无能为力了。比如集合里有 1、1、2我要删掉其中一个 1计数法能把 1 的计数从 2 改成 1可它没法指出该删数组里的哪个位置如果随机删除了其中一个下标数据结构本身无法确认删除的到底是不是目标值。计数法丢掉了“哪个下标对应哪个值”的关联信息最终要么补一次 O(n) 扫描要么把数据状态弄坏。所以正确姿势是记录每个值到底出现在哪些位置。当集合里有两个 1就记录1 - [0, 3]这样的下标集合。这样删除时能直接定位其中一个具体下标执行交换删除后再把对应位置从集合中移除。这个映射关系是整个数据结构的生命线索引一旦和真实数组错位后续所有操作都会变成随机 bug。2.2 用 class 还是 struct可变状态的归属实现上我用的是final class RandomizedCollection而不是 struct。虽然 Swift 的 struct 也能通过 mutating 方法实现同样逻辑但这个结构本质上是“一块持续变化的状态容器”业务侧希望引用同一个实例反复增删改查而不是每次操作后把新值赋回给一个新变量。class 的引用语义在这里更自然也避免在调用侧产生不必要的值拷贝。顺带一提Swift 的数组和字典虽然是值类型但底层都有写时复制copy-on-write优化。在我们这个类里values和indexMap都是私有属性所有修改都发生在类内部属性变更不会触发对外部容器的整份深拷贝性能上不需要额外担心。真正要警惕的反而是另外两件事Set 同样是值类型以及删除分支里可能会不小心创建同一个 Set 的多个局部副本这两点会在第 5 章的踩坑实录里详细展开。前面选了SetInt存下标Swift Set 的底层是哈希桶结构靠Hashable定位元素所以 remove、insert、contains 都是均摊 O(1)。哈希表同理indexMap[val]的读写也是均摊 O(1)。最终三个操作能压到 O(1)靠的就是这三样东西的组合数组的随机访问和尾增尾删、哈希表的快速定位、Set 的快速增删。3. 核心操作实现与逐行解析下面开始上代码。我会先讲每个方法的实现思路再结合代码逐行说明最后给出一个完整可运行的类。代码基于 Swift 5.7 / Xcode 15 验证过不依赖任何第三方库。3.1 初始化属性定义与不变量说明final class RandomizedCollection { private var values: [Int] [] private var indexMap: [Int: SetInt] [:] init() {} }values在逻辑上等于“当前还活着的元素列表”indexMap是辅助索引。这里有一个必须时刻维护的不变量indexMap里的每一个下标都必须真实存在于values的对应位置反过来values里出现的每一个不同值都要在indexMap里有对应键且这个键对应的集合绝不为空。这条不变量是后面所有方法不出错的基石任何分支只要破坏了它整个结构就会逐渐脱同步最后变成一个状态不可信的坏容器。语义约定上我遵循 LeetCode 381 的返回值约定insert(_:)返回true表示该值在插入之前从未出现过返回false表示集合里已经有该值但无论哪种情况都会正常插入一份remove(_:)返回true表示确实删掉了一个该值返回false表示集合里没有这个值什么都不做getRandom()在所有元素中均匀随机返回一个值。注意一个特别容易让队友迷糊的点因为允许重复insert(1)第二次调用时虽然返回false集合中已经有 1但它仍然会把另一个 1 加进去。这和不重复版本的语义完全不同写业务代码时一定要在注释里写清楚否则别人会误以为返回值代表“这次有没有真正插入”随后产生一堆不可预期的状态判断。3.2 插入操作把新下标登记进集合func insert(_ val: Int) - Bool { values.append(val) let newIndex values.count - 1 if indexMap[val] nil { indexMap[val] [newIndex] return true } else { indexMap[val]?.insert(newIndex) return false } }插入的步骤就是三件事先把值放进数组末尾拿到它的新下标newIndex然后把下标登记到该值的下标集合里再根据之前是否存在决定返回值。这里的newIndex一定是values.count - 1因为每次只 append 一个元素不会出现错位。有一个 Swift 细节值得注意indexMap[val]?.insert(newIndex)是通过可选链对值类型 Set 做修改。虽然从语义上说它是“在字典里的那个 Set 上改动”但由于 Set 是值类型一些复杂嵌套场景下可能让人产生“我的修改到底生效了没有”的困惑。为了代码可读性和避免后续调试时反复确认我在最终版本里更倾向于先把 Set 取出来、改完再写回而不是完全依赖可选链的隐式写回。下面删除方法的代码就是这种显式写回风格看起来略长但思路清晰很多。3.3 随机获取数组的唯一主场func getRandom() - Int { return values.randomElement()! }只要数组非空randomElement()就是从0..values.count里等概率取一个下标然后返回对应元素。数组在内存里是连续存储每个位置等长所以随机下标天然均匀不需要遍历也不需要知道元素分布这是动态数组区别于链表的核心优势之一。配合后面的交换删除只要保证“数组里每一个位置都对应一个真实存在的元素”随机取值的均匀性永远不会被破坏。这里我用了强制解包纯粹是为了保持题目语义。真实生产环境强烈不建议这样做一旦集合为空这一行就是崩溃引爆点。更好的做法是让getRandom()返回Int?或者在业务侧先判空再调用也可以使用guard let value values.randomElement()显式处理空集合。毕竟随机集合在空数组上强解包是迟早会引火烧身的操作。3.4 删除操作全结构最需要小心的灵魂删除任意一个值val的标准流程如下从indexMap[val]里拿出一个下标作为removeIndex如果该键不存在直接返回false如果removeIndex正好是数组最后一个下标直接弹出末尾元素然后把该下标从值对应的下标集合里删除如果removeIndex不在末尾把数组末尾元素lastVal覆盖到removeIndex位置再弹出末尾更新lastVal的下标集合删除原来的lastIndex加入新的removeIndex更新val的下标集合删除removeIndex如果集合删空把该键从字典中移除返回true。这套流程就是前面说的交换删除。它不是在数组中间用后续元素一个一个补洞而是拿尾巴去填洞再把缩短后的尾巴丢掉。数组的其他位置完全不动删除只涉及常数个位置时间复杂度才能压到 O(1)。边界处理中最容易翻车的一个场景是lastVal val。意思是你想删的值在数组末尾还有个一模一样的实例。如果这时候还走通用流程本质上是拿 val 自己覆盖自己同时在一个哈希键的索引集合上做两次互斥修改Swift 的值类型副本会把你辛苦登记的索引覆盖掉。我见过很多版本错误的代码就缺这一行判断所以单独把它拎出来展开讲。3.5 分情况讨论val lastVal 这个致命边界先看正确的 Swift 实现func remove(_ val: Int) - Bool { guard var indices indexMap[val], let removeIndex indices.first else { return false } let lastIndex values.count - 1 let lastVal values[lastIndex] // 情况 A目标恰好在末尾直接删 if removeIndex lastIndex { values.removeLast() indices.remove(removeIndex) if indices.isEmpty { indexMap.removeValue(forKey: val) } else { indexMap[val] indices } return true } // 情况 B要删的值和末尾的值相同不能走通用交换 if val lastVal { values.removeLast() indices.remove(lastIndex) if indices.isEmpty { indexMap.removeValue(forKey: val) } else { indexMap[val] indices } return true } // 普通情况用末尾元素覆盖目标位置 values[removeIndex] lastVal values.removeLast() if var lastIndices indexMap[lastVal] { lastIndices.remove(lastIndex) lastIndices.insert(removeIndex) indexMap[lastVal] lastIndices } indices.remove(removeIndex) if indices.isEmpty { indexMap.removeValue(forKey: val) } else { indexMap[val] indices } return true }情况 B 的逻辑很直接因为只是把末尾的val挪到中间来填空两个位置上的值又都是val所以数组的内容本质上没有变化只是长度短了 1。既然如此就没必要真的去动removeIndex位置的元素只需要在indexMap[val]里删掉末尾下标lastIndex就好。removeIndex仍然保留因为那个位置还站着一个货真价实的val。为什么不能走通用流程因为通用流程会先从indexMap[lastVal]取出一个局部副本删除lastIndex、插入removeIndex再把副本写回字典接着又对indexMap[val]当val lastVal时就是同一个字典键取出另一个局部副本删除removeIndex再写回。后一个写回会覆盖前一个写回最终的结果可能是删掉了removeIndex却把本应删掉的lastIndex留在集合里甚至出现 indexMap 和 values 完全对不上的玄学问题。这就是 Swift 值语义下的“副本覆盖”陷阱也是我在 5.2 节会展开讲的第二个坑。执行删除时我通过indices.first选择removeIndex。因为 Set 是无序的first到底选到哪个下标并不保证但无论哪一个都满足需求我们要删的是“任意一个”该值的实例。需要注意的是不要对indices.first的稳定性做任何假设只要保证它当前存在于该值的下标集合里就够用。3.6 完整类代码final class RandomizedCollection { private var values: [Int] [] private var indexMap: [Int: SetInt] [:] init() {} func insert(_ val: Int) - Bool { values.append(val) let newIndex values.count - 1 if indexMap[val] nil { indexMap[val] [newIndex] return true } else { indexMap[val]?.insert(newIndex) return false } } func remove(_ val: Int) - Bool { guard var indices indexMap[val], let removeIndex indices.first else { return false } let lastIndex values.count - 1 let lastVal values[lastIndex] if removeIndex lastIndex { values.removeLast() indices.remove(removeIndex) if indices.isEmpty { indexMap.removeValue(forKey: val) } else { indexMap[val] indices } return true } if val lastVal { values.removeLast() indices.remove(lastIndex) if indices.isEmpty { indexMap.removeValue(forKey: val) } else { indexMap[val] indices } return true } values[removeIndex] lastVal values.removeLast() if var lastIndices indexMap[lastVal] { lastIndices.remove(lastIndex) lastIndices.insert(removeIndex) indexMap[lastVal] lastIndices } indices.remove(removeIndex) if indices.isEmpty { indexMap.removeValue(forKey: val) } else { indexMap[val] indices } return true } func getRandom() - Int { return values.randomElement()! } }再强调一次getRandom()里的强制解包只适合刷题场景生产环境请一定改成可空返回或错误处理。完整代码我在本地用随机操作序列连续跑了十几万次增删改查全部通过5.4 节会给出一个可以自己跑的自测思路。4. 复杂度推导、边界验证与优化余地数据结构做完接下来最要紧的是把“为什么是 O(1)”这件事讲清楚否则代码写完了心里也不踏实。4.1 三个操作的时间复杂度推导逐个看。插入values.append在数组容量足够时是常数时间摊还下来 O(1)字典读、Set 插入都是均摊 O(1)。即使触发数组扩容均摊到每一次插入仍然是常数。所以insert是均摊 O(1)。删除最坏情况需要执行这些动作字典查询一次 O(1)、Set 取一个元素并删除一次 O(1)、数组读取lastVal并覆盖removeIndexO(1)、values.removeLast()O(1)、对lastIndices做一次删除和插入 O(1)、最后indices.remove(removeIndex)O(1)。每一步都跟集合总规模无关只和哈希冲突与扩容相关摊还后是 O(1)。随机获取values.randomElement()本质是生成一个0..count范围内的随机数然后按下标访问数组。数组按下标访问严格 O(1)随机数生成固定开销所以getRandom()是严格 O(1)。需要说明的是这里的 O(1) 是期望摊还的 O(1)依赖哈希表的良好分布。Swift 的 Dictionary 和 Set 在标准哈希函数下表现非常稳定普通业务场景完全不用操心。但如果是极端恶意构造的哈希碰撞理论上可能退化为 O(n)这是哈希结构的通病不是这个设计的缺陷。4.2 交换删除的正确性论据不少第一次接触交换删除的人会问把末尾元素搬到中间会不会破坏数组的随机均匀性答案是否定的。因为我们只关心“每次随机取一个值时是否等概率”并不关心数组内部元素的具体顺序。数组每个位置有且仅有一个元素随机下标天然等概率。你可以把数组想象成袋子袋子里球的顺序无关紧要关键是球的种类和数量不能少。交换删除只是把一个球从袋尾挪到袋中被掏空的位置没有改变球的总数和种类均匀性自然不受影响。在允许重复的前提下还需要额外保证一件事每次删除后indexMap里记录的“值 - 下标集合”必须和数组真实内容一一对应。交换删除搬运了一个元素相当于把lastVal从旧下标搬到了新下标所以indexMap[lastVal]必须删旧补新被删掉的那个值少了一个下标要从它的下标集合里划掉removeIndex。这两步必须同时成功任何一步掉链子都会导致后续操作的索引错乱。第 5 章里提到的几个 bug本质都是破坏了这条“映射与数组同步”的不变量。4.3 内存占用与可优化点这个结构的内存开销比普通数组高不少数组存一份值字典的 key 又存一份值每个值的下标集合还要为一堆整数分配内存。集合规模不大时这点开销无足轻重但如果你的业务是百万级数据就需要认真权衡了。一个常见优化方向是下标集合不一定非用SetInt在“每个值出现次数很少”的场景下用[Int]数组配合“只追加、删除时做交换删除”也能保持 O(1)。但这样做代码复杂度更高而且一旦某个值出现次数增多很容易退化回 O(n)。我的建议是默认使用SetInt再根据实际 profiling 结果决定是否优化。另一个优化是如果业务取值范围很小比如奖品 id 固定落在 0..1000 区间可以把[Int: SetInt]换成固定长度数组加位图的特化方案那就是另一个赛道的问题了。5. 踩坑实录我自己 debug 出来的问题这一部分是我的重头戏。我写第一版时以为“数组 字典 Set 交换删除”闭眼都能写对结果连续被三个 bug 打脸。每个 bug 都能复现、能讲清、也能从代码里看出门道分享出来是为了让后来的朋友少走弯路。5.1 问题一忘记清理空集合第一个 bug 非常隐蔽。我在删除方法里先把val对应下标集合的局部副本取出来删除removeIndex后判断“如果删除前集合里只有一个下标删完就变成空”。当时我偷懒没有把空集合从字典里移除而是让indexMap[val]保留了一个空 Set。从外部看indexMap[val]仍然存在所以后续insert(val)会走“已存在”分支返回false然后试图往一个空集合里插入下标结果变成一个“新值插入却被告知已存在”的怪状态逻辑彻底乱掉。更危险的是删除方法开头的guard var indices indexMap[val]会把“键存在但集合空”当成“值存在”返回true可数组里根本没有这个值索引和数组从这一刻开始脱绑。之后每一次随机取值都可能取到“数组里不存在的位置”最终以 crash 或脏数据收场。教训是任何让indices变空的地方都要记得删掉indexMap里对应的键。始终维护“空集合不出现在字典中”这个不变量。它看似多余实际上是整个数据结构稳定工作的地基。5.2 问题二val lastVal 时的索引集合互踩第二个 bug 是我调得最久的一次。最初我写的删除逻辑没有单独判断val lastVal而是统一走“拿 lastVal 覆盖 removeIndex”的通用分支。单测里各种乱序数据都过了但一遇到[1, 1]这种连续重复数组状态就在几次操作后彻底崩坏。原因并不复杂当val lastVal时indexMap[val]和indexMap[lastVal]根本就是同一个字典键。通用流程会先从该键取出局部副本 A删除lastIndex、插入removeIndex写回然后对该键再取出局部副本 B删除removeIndex写回。因为 Swift 的 Set 是值类型两个局部副本从同一个原始集合拷贝出来彼此毫无感知最终写回字典的是后者。于是该删的lastIndex没删掉该保留的removeIndex反而可能被删掉indexMap和values出现错位。再往后一切操作都建立在错误索引之上越走越歪。修复方式就是我在 3.5 节给出的把val lastVal单独成一个分支直接删末尾下标不经过任何覆盖流程。这样一次只操作一个副本不会出现覆盖问题。5.3 问题三把下标集合用成了数组我一开始图省事把indexMap定义成[Int: [Int]]想着数组读起来直观。结果删除操作直接变成灾难要删一个值得先从它的下标数组里找到removeIndex数组删除中间元素是 O(n)更麻烦的是交换删除之后被搬走的lastVal的下标数组还要更新又得线性查找原来的lastIndex再做替换。当数据规模到十万条以上每次删除的开销就从“常数”变成了“和出现次数相关”整个结构名存实亡。换回SetInt后问题立刻消失remove、insert、contains 全是均摊 O(1)而且完全不需要关心下标顺序。这个教训告诉我操作复杂度的要求必须前移到类型选型阶段不能等代码跑慢了再回头重构。5.4 给一份可以自己跑的自测思路我建议把下面这段测试逻辑放到 Playground 或 XCTest 里跑。它每次随机执行一个操作再用一个朴素的[Int]作为参照物逐项比对结果连续跑几千步就能把边界问题炸出来import XCTest final class RandomizedCollectionTests: XCTestCase { func testRandomOps() { let rc RandomizedCollection() var reference: [Int] [] for _ in 0..20000 { let op Int.random(in: 0..3) if op 0 || reference.isEmpty { let v Int.random(in: 0..5) let rcInserted rc.insert(v) let refInserted !reference.contains(v) XCTAssertEqual(rcInserted, refInserted) reference.append(v) } else if op 1 { let v Int.random(in: 0..5) let rcRemoved rc.remove(v) let refRemoved reference.contains(v) XCTAssertEqual(rcRemoved, refRemoved) if let idx reference.firstIndex(of: v) { reference.remove(at: idx) } } else { XCTAssertFalse(reference.isEmpty) _ rc.getRandom() } } } }需要说明的是测试里的reference.contains是 O(n)所以这个脚本只适合做功能正确性验证不能当性能基准。要验证真的 O(1)得用大数据量加独立计时而不是内嵌一个 O(n) 参照物来拖后腿。6. 一些个人体会和工程化建议如果只让我从这次实现里留下一条感悟那就是在 Swift 里写这类结构题最大的坑不是算法本身而是值语义带来的副本覆盖。C 里你可以拿unordered_mapint, unordered_setint的引用一顿操作天然就是“改同一份”Swift 里沿用这种思维惯性就会直接踩中我在 5.2 节描述的那类 bug。所以写 Swift 时遇到字典值类型嵌套一定要时刻问自己此刻拿到的是引用还是副本我写回了吗另一个分支会不会覆盖我工程化落地时我还会额外做三件事。第一在RandomizedCollection内部维护一个count属性避免每次通过values.count推导状态减少出错面。第二给这个类加线程保护用NSLock或 Swift 的 actor 包裹否则并发环境下一次删除可能导致数组和字典不同步随机集合会直接变成一个随机 bug 发生器。第三把getRandom()的空值处理改到业务层返回 Optional 或抛错误不要在崩溃边缘反复试探。还有一个可玩的扩展方向把元素类型从Int泛化成Element: Hashable整个结构就能适用于字符串、UUID、枚举等任意可哈希类型。泛型化之后它能服务的场景就不止抽奖和题库了像推荐系统的候选池、消息队列里支持随机消费的去重集合都能直接复用这套设计。我后来在项目里就是这么干的把[Int]换成[Element]其余逻辑一行没动就全部跑通。这个扩展让我意识到这个结构表面叫“随机集合”本质其实是一种“支持快速随机访问的动态哈希索引”。想通这一层才算真正吃透了它。