尧图网站建设 随机集合)
我前后提交了六遍才把 LeetCode 380 这道题的细节全部捋顺倒不是说思路有多绕而是“O(1)”这个约束把所有数据结构的老毛病全逼出来了。题目要求你实现一个 RandomizedSet支持插入、删除、获取随机元素三个操作都要 O(1)而且是最硬核的 C 语言环境——没有 C 的 unordered_set没有 Java 的 HashSet标准库能用的只有 malloc、free 和 rand。刚看到题我第一反应是哈希表插入 O(1)、删除 O(1)、查重 O(1)问题不就解决了但下一秒就被 getRandom 卡住了哈希表是无序的你既不能按下标访问也不能保证遍历顺序和随机性沾边。反过来用数组随机下标访问确实是 O(1)可插入要查重得先遍历一遍删除中间元素要把后面所有元素往前挪又是 O(n)。所以这道题真正考的是组合让哈希表负责快速定位让动态数组负责随机访问再用“下标”这根线把两边缝成一套一致的结构。这篇文章我会用 C 语言完整实现一遍把哈希表手写细节、动态数组的覆盖删除技巧、以及提交过程中真正容易翻车的几个坑全部摊开讲。适合刚刷完链表和树、想进阶数据结构组合题的读者也适合所有用 C 语言刷题、受够了“没有现成哈希表”的朋友。1. 题目拆解三个操作都要 O(1)为什么不是一道简单题1.1 先看清题目让你实现什么RandomizedSet 的接口很短一个初始化加三个操作。插入时如果值已经存在就返回 false且集合保持不变不存在才插入并返回 true。删除时如果值不存在就返回 false存在则删除并返回 true。最后一个 getRandom 要求返回集合中的任意一个元素并且题目明确要求每个元素被返回的概率相同。这个接口里藏着一个非常关键的前提集合内的值必须唯一。正因为值唯一我们才可以把“值本身”当作哈希表的 key而不需要处理一个值对应多个下标的情况。很多第一次写的人没有意识到这个前提有多重要等做到 LeetCode 381允许重复元素的版本时会发现复杂度直接跳一档原因就在这里。另外还要注意题目的 O(1) 严格说是“期望 O(1)”和“摊销 O(1)”。哈希表在负载因子控制合理时单次查询期望 O(1)数组扩容和哈希表 rehash 虽然偶尔发生一次但均摊到每次操作上依然是 O(1)。LeetCode 的测试一般不会刻意卡这类退化但你心里要清楚这个边界别把话说满。1.2 单独看都不难组合起来才要命把三种操作单独拉出来看每种都有数据结构能胜任但没有任何一种能同时满足全部需求操作朴素方案致命问题insert动态数组尾部插入查重只能线性遍历O(n)remove哈希表直接删除哈希表无法等概率随机取元素getRandom数组随机下标插入/删除中间元素需要移位O(n)这张表揭示了一个结构性矛盾数组擅长“按下标访问”但不擅长“按值找位置”哈希表擅长“按值找位置”但它的内部存储是散列的无法保证随机访问的语义。链表更不用提随机访问本身就是 O(n)平衡树能做到 O(log n) 的查找和删除但 getRandom 要等概率还得维护顺序统计依然做不到 O(1)。所以这道题真正考的不是某个单独的数据结构而是“组合”之后的一致性维护数组存什么、哈希表存什么、两个结构在每次插入和删除后如何保持同步。这是下文要重点展开的内容。2. 为什么偏偏是“哈希表 动态数组”让两个结构各管一摊2.1 数组负责“随机”哈希表负责“查重”先明确两个结构各自的职责这是理解整道题的地基。动态数组在这里是数据本体当前集合里所有值依次存在数组中数组下标就是它们的位置编号。getRandom 的实现因此简单到没朋友——随机生成一个[0, size)的下标返回arr.data[idx]即可。随机访问数组元素是硬件级操作这是 O(1) 最没有争议的实现方式。哈希表在这里是索引保存每个值在动态数组中的下标。有了这张索引表insert 想知道val在不在集合里O(1) 查一下remove 想知道val在数组的哪个位置O(1) 查一下。没有哈希表数组的一切操作都得从头遍历那数组再能随机也是白搭。打个比方数组是一排储物柜柜门上的编号就是下标哈希表是一本台账写着“某件物品存放在几号柜”。你要随机拿一件物品闭着眼睛报一个柜门编号就行数组你要检查某件物品在不在库房、或者想把某件物品精确清出去先翻台账哈希表。台账保证秒级定位柜子保证秒级抽查两者缺一不可。2.2 下标是连接两个世界的“契约”这里最关键的工程决策是两个数据结构之间只通过下标通信绝不通过指针。为什么因为动态数组扩容时要 realloc扩容后底层内存地址可能完全变了。如果哈希表节点里存的是指向数组元素的指针扩容的一瞬间所有指针全部失效台账上的地址全部作废。但如果存的是下标逻辑位置没变——数组扩容只是把元素搬到更大的新家“第 3 个位置”依然是第 3 个位置。哈希表里的键值对始终是“值 - 下标”这个语义不受 realloc 影响。我第一次写的时候没想透直接在哈希节点里存了int *ptr本地小规模测试一切正常连续插入几万个数据触发扩容后程序就随机崩溃。排查了很久才意识到是扩容导致指针失效。所以后来我给自己定了一条硬规矩数组和哈希表之间只传下标不传指针。2.3 数据冗余是刻意设计不是浪费有人可能会问哈希表节点里存 key数组里也存一份值两份数据不是冗余吗这个冗余确实是刻意设计的。哈希表节点只管key和idx它不负责数据生命周期的管理数组才是唯一真正“持有”数据的地方。插入、删除、随机全部以数组为准哈希表永远是数组的索引。这种“一份数据 一套索引”的模式在工程界太常见了最典型的就是数据库表数据存在磁盘页里索引结构只存键和指向数据行的位置理念完全一致。理解这一点后面写删除逻辑时就不会搞混数组变了索引要跟着变索引错了数据本身也会跟着乱。3. C语言手写哈希表从零开始构建映射关系3.1 为什么必须自己造轮子C 标准库没有哈希表。你在 stdlib.h 和 string.h 里翻破天也找不到一个 hash_map。所以用 C 刷题必须自己实现一套够用的哈希表。好在 LeetCode 的测试规模一般不超过 2*10^5 次操作我们不需要工业级实现只要做到“插入、删除、查找平均 O(1)”就行。冲突处理我选的是链地址法维护一个桶数组每个桶是一个链表的头指针算完哈希值之后取模定位到桶再在对应链表里查找。为什么不选开放地址法线性探测因为开放地址法删除时要打“墓碑”标记代码绕而且随着负载升高性能会急剧恶化。链地址法实现直观、删除方便、每个节点都是独立 malloc 的内存块生命周期好控制最适合刷题场景。3.2 节点与哈希表的结构定义typedef struct HashNode { int key; // 集合中的值 int idx; // 该值在动态数组中的下标 struct HashNode *next; // 同桶链表的下一个节点 } HashNode; typedef struct { HashNode **buckets; // 桶数组每个元素是链表头指针 int bucketCount; // 桶的数量 int size; // 哈希表中键值对总数 } HashMap;哈希函数我直接用了取模int hashKey(int key, int bucketCount) { return (unsigned)key % bucketCount; }3.3 哈希函数里的 C 语言陷阱负数取模这个哈希函数值得展开说因为它至少涉及两个经典 C 坑。第一为什么要先转(unsigned)key因为 C 语言里负数对正数取模结果还是负数。-7 % 16在 C 里结果是-7拿一个负数下标去访问桶数组直接越界崩溃。转成 unsigned 后取模结果一定落在[0, bucketCount)。第二为什么不直接abs(key) % bucketCount因为abs(INT_MIN)是未定义行为结果会溢出成负数。一旦集合里真的出现INT_MIN程序当场爆炸。而(unsigned)INT_MIN % bucketCount完全合法结果稳定。第三取模在 key 分布随机时完全够用。即使 key 有明显规律比如全是偶数链地址法也能吃得住冲突因为负载因子控制住了每个桶的平均长度。有人会担心bucketCount必须是质数才能让取模均匀那是开放地址法时代的老黄历对链地址法来说桶数量用 2 的幂完全没问题。3.4 put / get / remove 三个基础操作查询函数最直接算出桶下标沿链表找 key找到返回 idx找不到返回 -1。-1 永远不会和合法下标冲突因为数组下标从 0 开始。int hashGet(HashMap *map, int key) { int h hashKey(key, map-bucketCount); HashNode *cur map-buckets[h]; while (cur ! NULL) { if (cur-key key) { return cur-idx; } cur cur-next; } return -1; }插入用头插法新节点直接挂在桶链表最前面不需要遍历找尾节点天生 O(1)。插入前检查负载因子超过 0.7 就先扩容void hashPut(HashMap *map, int key, int idx) { if ((map-size 1) * 10 map-bucketCount * 7) { hashRehash(map, map-bucketCount * 2); } int h hashKey(key, map-bucketCount); HashNode *node (HashNode*)malloc(sizeof(HashNode)); node-key key; node-idx idx; node-next map-buckets[h]; map-buckets[h] node; map-size; }删除操作要遍历链表找到后修改前驱节点的next指针注意头结点的特判void hashRemove(HashMap *map, int key) { int h hashKey(key, map-bucketCount); HashNode *cur map-buckets[h]; HashNode *prev NULL; while (cur ! NULL) { if (cur-key key) { if (prev NULL) { map-buckets[h] cur-next; } else { prev-next cur-next; } free(cur); map-size--; return; } prev cur; cur cur-next; } }3.5 负载因子与 rehash保证“期望 O(1)”的关键如果桶的数量固定不变插入越来越多每个桶的链表会越来越长查找慢慢就退化成了线性扫描。所以要在负载因子size / bucketCount过高时把桶数组扩大把旧节点全部重新分布到新桶数组里。我设的阈值是 0.7即(size 1) * 10 bucketCount * 7时翻倍。rehash 的实现就是遍历所有旧桶的链表把节点取下来重新计算桶下标挂到新桶数组里。节点本身不重新 malloc搬家的只是“桶归属关系”void hashRehash(HashMap *map, int newBucketCount) { HashNode **oldBuckets map-buckets; int oldCount map-bucketCount; map-buckets (HashNode**)calloc(newBucketCount, sizeof(HashNode*)); map-bucketCount newBucketCount; for (int i 0; i oldCount; i) { HashNode *cur oldBuckets[i]; while (cur ! NULL) { HashNode *next cur-next; int h hashKey(cur-key, map-bucketCount); cur-next map-buckets[h]; map-buckets[h] cur; cur next; } } free(oldBuckets); }有个细节因为一直用头插rehash 后每个桶里链表的顺序会反转。这道题无所谓哈希表只关心“键是否存在、对应下标是多少”不关心桶内部顺序。但如果你在其他场景依赖链表顺序就需要注意。提示负载因子阈值选 0.7 是时间和空间的折中。阈值越小桶越稀疏查找越快但内存越浪费阈值太接近 1链表变长查找变慢。工程里常见默认值是 0.75写成 7/10 是为了避免浮点运算。4. 动态数组 删除操作的“障眼法”用覆盖避免 O(n)4.1 数组为什么“不敢”删除中间元素动态数组负责数据本体插入很简单末尾追加满了扩容。但删除是这道题真正的陷阱。假设数组是[7, 2, 9, 4]要删除9下标 2。如果只把下标 2 的元素置 0数组里会留下一个“洞”size 没法正确减一getRandom 随机到洞上就全乱套。要让“数组前 size 个位置都是有效元素”常规做法是把9后面的所有元素往前挪一位得到[7, 2, 4]。这一步需要移动 O(n) 个元素违反题目的 O(1) 要求。于是这里就用一个经典技巧不但不把后面的元素往前挪反而把最后一个元素搬过来覆盖被删的位置。4.2 用“末尾元素覆盖”实现 O(1) 删除还是[7, 2, 9, 4]删除9。先把最后一个元素4下标 3拿来覆盖下标 2数组变成[7, 2, 4, 4]然后把 size 减一逻辑数组变成[7, 2, 4]。被删的9已经不存在末尾残留的旧值4也无所谓因为 size 已经不再把它当作有效元素。这个操作的时间复杂度是 O(1)一次数组赋值一次 size 自减。代价是数组中元素的相对顺序被破坏了原来下标 2 和下标 3 的先后顺序没了。所以这个技巧只能用于“对顺序没有要求”的集合而本题恰好只要求等概率随机返回不要求保序完美适配。真正的难点在联动更新。被删位置换成了4哈希表里4对应的下标就必须从 3 改成 2。完整顺序是用哈希表查到9的下标delIdx 2。取数组最后一个元素lastVal 4、lastIdx 3。从哈希表里删除key 9的条目。如果delIdx ! lastIdx把arr.data[2]覆盖成4并把哈希表里key 4的下标改为 2。arr.size--。下面这张表可以直观看到删除过程中数组和哈希表的每一步变化阶段数组内容哈希表部分初始[7, 2, 9, 4]7→0, 2→1, 9→2, 4→3移除 9 的映射[7, 2, 9, 4]7→0, 2→1, 4→3末尾元素覆盖[7, 2, 4, 4]7→0, 2→1, 4→3更新 4 的下标[7, 2, 4, 4]7→0, 2→1, 4→2size 减一逻辑数组 [7, 2, 4]7→0, 2→1, 4→24.3 删除同步更新的代码细节对应到 C 代码就是下面这一段注意delIdx ! lastIdx的判断bool randomizedSetRemove(RandomizedSet *obj, int val) { int delIdx hashGet(obj-map, val); if (delIdx -1) { return false; } int lastIdx obj-arr.size - 1; int lastVal obj-arr.data[lastIdx]; hashRemove(obj-map, val); // 第一步删掉 val 的索引条目 if (delIdx ! lastIdx) { obj-arr.data[delIdx] lastVal; // 第二步末尾元素覆盖被删位置 hashRemove(obj-map, lastVal); // 第三步更新 lastVal 的索引 hashPut(obj-map, lastVal, delIdx); } obj-arr.size--; // 第四步逻辑删除末尾 return true; }如果删除的本来就是最后一个元素那么delIdx lastIdxlastVal就是val本身这时哈希表里val的条目已经被第一步删掉了不能再执行hashRemove(lastVal)和hashPut(lastVal, delIdx)否则就是对同一个 key 做无意义甚至危险的操作。这个if判断毛糙一点就会漏我在踩坑部分还会再强调。4.4 数组容量管理与 realloc 的坑数组初始容量我设为 8每次满了翻倍if (obj-arr.size obj-arr.capacity) { obj-arr.capacity * 2; obj-arr.data (int*)realloc(obj-arr.data, sizeof(int) * obj-arr.capacity); }realloc 有三种表现原地扩大、搬家复制、失败返回 NULL。原地扩大时指针不变搬家时 realloc 内部会复制旧数据并释放旧内存新指针可能完全不同。好在哈希表里只存下标不存指针搬家不会破坏映射关系这就是前面强调“只传下标不传指针”的回报。注意realloc 失败会返回 NULL但原指针依然有效。如果直接arr.data realloc(...)一旦失败就把原指针覆盖成 NULL造成泄漏。刷题时我们默认内存充足不处理这种情况但在项目代码里务必先用临时变量接住返回值再判空。5. 完整代码实现与用例验证5.1 可直接复制提交的完整代码把前面拆开的哈希表函数、数组管理和 RandomizedSet 的接口整合在一起加齐头文件就是一份能直接粘到 LeetCode 编辑器里的完整实现#include stdbool.h #include stdlib.h #include time.h typedef struct HashNode { int key; int idx; struct HashNode *next; } HashNode; typedef struct { HashNode **buckets; int bucketCount; int size; } HashMap; typedef struct { int *data; int size; int capacity; } DynamicArray; typedef struct { DynamicArray arr; HashMap map; } RandomizedSet; int hashKey(int key, int bucketCount) { return (unsigned)key % bucketCount; } void hashRehash(HashMap *map, int newBucketCount) { HashNode **oldBuckets map-buckets; int oldCount map-bucketCount; map-buckets (HashNode**)calloc(newBucketCount, sizeof(HashNode*)); map-bucketCount newBucketCount; for (int i 0; i oldCount; i) { HashNode *cur oldBuckets[i]; while (cur ! NULL) { HashNode *next cur-next; int h hashKey(cur-key, map-bucketCount); cur-next map-buckets[h]; map-buckets[h] cur; cur next; } } free(oldBuckets); } void hashPut(HashMap *map, int key, int idx) { if ((map-size 1) * 10 map-bucketCount * 7) { hashRehash(map, map-bucketCount * 2); } int h hashKey(key, map-bucketCount); HashNode *node (HashNode*)malloc(sizeof(HashNode)); node-key key; node-idx idx; node-next map-buckets[h]; map-buckets[h] node; map-size; } int hashGet(HashMap *map, int key) { int h hashKey(key, map-bucketCount); HashNode *cur map-buckets[h]; while (cur ! NULL) { if (cur-key key) { return cur-idx; } cur cur-next; } return -1; } void hashRemove(HashMap *map, int key) { int h hashKey(key, map-bucketCount); HashNode *cur map-buckets[h]; HashNode *prev NULL; while (cur ! NULL) { if (cur-key key) { if (prev NULL) { map-buckets[h] cur-next; } else { prev-next cur-next; } free(cur); map-size--; return; } prev cur; cur cur-next; } } RandomizedSet* randomizedSetCreate() { RandomizedSet *obj (RandomizedSet*)malloc(sizeof(RandomizedSet)); obj-arr.capacity 8; obj-arr.size 0; obj-arr.data (int*)malloc(sizeof(int) * obj-arr.capacity); obj-map.bucketCount 16; obj-map.size 0; obj-map.buckets (HashNode**)calloc(obj-map.bucketCount, sizeof(HashNode*)); srand((unsigned)time(NULL)); return obj; } bool randomizedSetInsert(RandomizedSet *obj, int val) { if (hashGet(obj-map, val) ! -1) { return false; } if (obj-arr.size obj-arr.capacity) { obj-arr.capacity * 2; obj-arr.data (int*)realloc(obj-arr.data, sizeof(int) * obj-arr.capacity); } obj-arr.data[obj-arr.size] val; hashPut(obj-map, val, obj-arr.size); obj-arr.size; return true; } bool randomizedSetRemove(RandomizedSet *obj, int val) { int delIdx hashGet(obj-map, val); if (delIdx -1) { return false; } int lastIdx obj-arr.size - 1; int lastVal obj-arr.data[lastIdx]; hashRemove(obj-map, val); if (delIdx ! lastIdx) { obj-arr.data[delIdx] lastVal; hashRemove(obj-map, lastVal); hashPut(obj-map, lastVal, delIdx); } obj-arr.size--; return true; } int randomizedSetGetRandom(RandomizedSet *obj) { int idx rand() % obj-arr.size; return obj-arr.data[idx]; } void randomizedSetFree(RandomizedSet *obj) { for (int i 0; i obj-map.bucketCount; i) { HashNode *cur obj-map.buckets[i]; while (cur ! NULL) { HashNode *tmp cur; cur cur-next; free(tmp); } } free(obj-map.buckets); free(obj-arr.data); free(obj); }这段代码在 LeetCode 官方 C 语言环境下可以直接提交不需要额外依赖任何第三方头文件。5.2 用官方示例手推一遍题目给的示例是输入: [RandomizedSet,insert,remove,insert,getRandom,remove,insert,getRandom] [[],[1],[2],[2],[],[1],[2],[]] 输出: [null,true,false,true,2,true,false,2]一步一步推RandomizedSet()创建空集合。insert(1)集合中没有 1插入返回 true。数组变为[1]哈希表{1:0}。remove(2)集合中没有 2返回 false。状态不变。insert(2)集合中没有 2插入。数组变为[1,2]哈希表{1:0, 2:1}返回 true。getRandom()size 为 2随机下标是 0 或 1可能返回 1 或 2。示例输出是 2。remove(1)查到 1 的下标是 0数组最后一个元素是 2下标 1。删掉哈希表里的 1把 2 覆盖到下标 0更新哈希表{2:0}size 变为 1数组逻辑上变为[2]返回 true。insert(2)哈希表里已经有 2返回 false。getRandom()集合里只剩 2返回 2。第七步是关键验证点如果删除 1 时没有同步更新 2 的下标哈希表里2还指向 1那么insert(2)会因为hashGet返回 1而不是 -1而错误地认为 2 不存在结果变成插入成功。整条链路的一致性就在这。5.3 提交表现参考在 LeetCode 上这份 C 代码的时间通常在 80ms~130ms 浮动空间在 25MB 左右击败率会随着测试数据波动不必太在意。真正重要的是手写哈希表 手动扩容这套逻辑在 2*10^5 规模下运行得很稳没有出现超时或内存异常。6. 提交过程中容易踩的坑6.1 删除时哈希表更新的先后顺序删除逻辑最忌讳的就是顺序搞反。核心原则是先通过哈希表定位再动手改数组最后同步哈希表。正确顺序我已经写在代码里先hashGet拿到delIdx再hashRemove(val)然后覆盖数组。如果你先覆盖数组再回头查哈希表数组里被删位置已经被lastVal占领此时再想拿到val的原始下标就难了。更隐蔽的错误是在覆盖数组之前就把lastVal的哈希条目删掉结果数组覆盖完成后忘了重新插入哈希表里直接少了一条映射之后insert(lastVal)会错误地认为它不存在。6.2 “删除最后一个元素”的特殊分支必须单独处理当delIdx lastIdx时我们已经在第一步删掉了val的哈希条目数组也不需要覆盖直接size--收工。如果不加if (delIdx ! lastIdx)这个保护而是统一执行hashRemove(lastVal)和hashPut(lastVal, delIdx)就会对同一个 key 做两次删除等于把别的节点也一起删了或者造成链表操作混乱。我在实现里加了保护你如果自己写务必保留这个分支判断。6.3 rand() 的随机范围和小样本偏向RAND_MAX在不同平台差异很大。Linux 的 glibc 下是 2147483647Windows 的 MSVC 下只有 32767。如果集合里有 50000 个元素在 MSVC 平台上rand() % size虽然不会越界但低位的随机性和均匀性都很差。LeetCode 评测机是 Linux GCC直接取模能过但如果你在本地用 VS 调试发现随机结果有明显偏向可以用rand() * (RAND_MAX 1) rand()缝合两个随机数再取模均匀性会好很多。另一个小坑是 srand 的调用位置。srand 只应该在randomizedSetCreate里调用一次千万别放在getRandom里否则每次调用都重置随机种子连续调用会返回同一个值。我在完整代码里把srand((unsigned)time(NULL))放在 create 里这是正确的位置。6.4 getRandom 在空集合上的除零rand() % 0是未定义行为实际运行时大概率直接崩溃。题目保证 getRandom 只在集合非空时调用LeetCode 测试不会踩这个雷。但如果你在本地做压力测试或者以后复用这套代码建议加一行防御int randomizedSetGetRandom(RandomizedSet *obj) { if (obj-arr.size 0) { return -1; } int idx rand() % obj-arr.size; return obj-arr.data[idx]; }虽然题目用不上但“对空集合有明确行为”是合格 C 代码的基本素养。6.5 内存释放的顺序不能乱randomizedSetFree的顺序必须是先释放所有哈希节点再释放桶数组然后释放动态数组数据最后释放 RandomizedSet 本身。反过来释放会先丢指针后面就没法遍历链表了。哈希节点是每次hashPut时单独 malloc 的数量等于集合元素个数遍历所有桶逐一 free 是必须的否则就是一堆悬挂指针。提示LeetCode 的在线评测并不严格检查每个对象的内存泄漏但如果多次测试在同一个进程里跑泄漏的内存会累积可能导致后面的用例出现奇怪的内存错误。养成随手写好 Free 函数的习惯对本地调试也有帮助。7. 复杂度分析与后续扩展7.1 三个操作的复杂度验证操作平均时间复杂度主要步骤insertO(1) 摊销哈希查询 O(1) 尾部插入 O(1)扩容和 rehash 均摊removeO(1) 摊销哈希定位 O(1) 覆盖 O(1) 哈希更新 O(1)getRandomO(1)随机下标 直接返回空间复杂度是 O(n)由三部分组成动态数组存 n 个 int哈希表存 n 个节点桶数组本身。数组扩容到 2 倍容量时最坏情况下容量接近 2n所以实际空间是 O(n) 级别常数稍大但规模完全可控。7.2 从 380 到 381允许重复元素时怎么改LeetCode 381 是同一道题的“允许重复”版本默认你已经掌握了 380 的核心。区别只有一点哈希表的 value 从“单个下标”变成“一组下标的集合”。数组依然存值每个值可能出现多次哈希表的每个 key 对应一个下标容器这个容器可以用另一个简化哈希表实现也可以直接用链表。删除时从该值的下标集合里随便取一个下标用它和数组最后一个元素做覆盖交换再同步更新两个值各自的下标集合。整体思路完全是从 380 长的如果你把 380 的一致性维护逻辑吃透了381 只是给 value 包了一层容器写起来就是时间问题。7.3 这套结构在真实工程里还能干什么哈希表 动态数组的组合在算法题之外非常常见。在线抽奖系统需要一个“可快速去重、可等概率抽取、抽取后快速移除”的奖品池用户 ID 放数组哈希表记录 ID 在数组中的位置中奖用户用覆盖法移除抽奖过程天然等概率。游戏服务器的随机昵称池、随机匹配队列本质也是同一套结构。数据库里的“表数据 索引”更是这种模式的高配版数据是本体索引负责快速定位只是工程实现换成了 B 树而已。所以这道题虽然挂着“LeetCode 380”的名字实际上是一个在现实系统中反复出现的工程模式的最小演示。把“两个结构如何保持同步”这个问题想明白很多系统的核心数据路径就不再神秘了。最后说点题外的感受。用 C 语言刷题最大的福利就是没有现成的哈希表可用逼你手写一遍之后你对“哈希表到底是什么、为什么平均 O(1)”的理解会和背 API 完全不同。刷完 380 我再去做 381思路几乎是平移过去的只花了大半个晚上就写完了。如果你也是 C 党我强烈建议别一上来就依赖 uthash先手写一个链地址法版本等真正理解了内部机制再回头看那些现成库会发现它们的 API 设计反而更好懂了。 C语言实现LeetCode 380：哈希表+动态数组打造O(1)随机集合
我前后提交了六遍才把 LeetCode 380 这道题的细节全部捋顺倒不是说思路有多绕而是“O(1)”这个约束把所有数据结构的老毛病全逼出来了。题目要求你实现一个 RandomizedSet支持插入、删除、获取随机元素三个操作都要 O(1)而且是最硬核的 C 语言环境——没有 C 的 unordered_set没有 Java 的 HashSet标准库能用的只有 malloc、free 和 rand。刚看到题我第一反应是哈希表插入 O(1)、删除 O(1)、查重 O(1)问题不就解决了但下一秒就被 getRandom 卡住了哈希表是无序的你既不能按下标访问也不能保证遍历顺序和随机性沾边。反过来用数组随机下标访问确实是 O(1)可插入要查重得先遍历一遍删除中间元素要把后面所有元素往前挪又是 O(n)。所以这道题真正考的是组合让哈希表负责快速定位让动态数组负责随机访问再用“下标”这根线把两边缝成一套一致的结构。这篇文章我会用 C 语言完整实现一遍把哈希表手写细节、动态数组的覆盖删除技巧、以及提交过程中真正容易翻车的几个坑全部摊开讲。适合刚刷完链表和树、想进阶数据结构组合题的读者也适合所有用 C 语言刷题、受够了“没有现成哈希表”的朋友。1. 题目拆解三个操作都要 O(1)为什么不是一道简单题1.1 先看清题目让你实现什么RandomizedSet 的接口很短一个初始化加三个操作。插入时如果值已经存在就返回 false且集合保持不变不存在才插入并返回 true。删除时如果值不存在就返回 false存在则删除并返回 true。最后一个 getRandom 要求返回集合中的任意一个元素并且题目明确要求每个元素被返回的概率相同。这个接口里藏着一个非常关键的前提集合内的值必须唯一。正因为值唯一我们才可以把“值本身”当作哈希表的 key而不需要处理一个值对应多个下标的情况。很多第一次写的人没有意识到这个前提有多重要等做到 LeetCode 381允许重复元素的版本时会发现复杂度直接跳一档原因就在这里。另外还要注意题目的 O(1) 严格说是“期望 O(1)”和“摊销 O(1)”。哈希表在负载因子控制合理时单次查询期望 O(1)数组扩容和哈希表 rehash 虽然偶尔发生一次但均摊到每次操作上依然是 O(1)。LeetCode 的测试一般不会刻意卡这类退化但你心里要清楚这个边界别把话说满。1.2 单独看都不难组合起来才要命把三种操作单独拉出来看每种都有数据结构能胜任但没有任何一种能同时满足全部需求操作朴素方案致命问题insert动态数组尾部插入查重只能线性遍历O(n)remove哈希表直接删除哈希表无法等概率随机取元素getRandom数组随机下标插入/删除中间元素需要移位O(n)这张表揭示了一个结构性矛盾数组擅长“按下标访问”但不擅长“按值找位置”哈希表擅长“按值找位置”但它的内部存储是散列的无法保证随机访问的语义。链表更不用提随机访问本身就是 O(n)平衡树能做到 O(log n) 的查找和删除但 getRandom 要等概率还得维护顺序统计依然做不到 O(1)。所以这道题真正考的不是某个单独的数据结构而是“组合”之后的一致性维护数组存什么、哈希表存什么、两个结构在每次插入和删除后如何保持同步。这是下文要重点展开的内容。2. 为什么偏偏是“哈希表 动态数组”让两个结构各管一摊2.1 数组负责“随机”哈希表负责“查重”先明确两个结构各自的职责这是理解整道题的地基。动态数组在这里是数据本体当前集合里所有值依次存在数组中数组下标就是它们的位置编号。getRandom 的实现因此简单到没朋友——随机生成一个[0, size)的下标返回arr.data[idx]即可。随机访问数组元素是硬件级操作这是 O(1) 最没有争议的实现方式。哈希表在这里是索引保存每个值在动态数组中的下标。有了这张索引表insert 想知道val在不在集合里O(1) 查一下remove 想知道val在数组的哪个位置O(1) 查一下。没有哈希表数组的一切操作都得从头遍历那数组再能随机也是白搭。打个比方数组是一排储物柜柜门上的编号就是下标哈希表是一本台账写着“某件物品存放在几号柜”。你要随机拿一件物品闭着眼睛报一个柜门编号就行数组你要检查某件物品在不在库房、或者想把某件物品精确清出去先翻台账哈希表。台账保证秒级定位柜子保证秒级抽查两者缺一不可。2.2 下标是连接两个世界的“契约”这里最关键的工程决策是两个数据结构之间只通过下标通信绝不通过指针。为什么因为动态数组扩容时要 realloc扩容后底层内存地址可能完全变了。如果哈希表节点里存的是指向数组元素的指针扩容的一瞬间所有指针全部失效台账上的地址全部作废。但如果存的是下标逻辑位置没变——数组扩容只是把元素搬到更大的新家“第 3 个位置”依然是第 3 个位置。哈希表里的键值对始终是“值 - 下标”这个语义不受 realloc 影响。我第一次写的时候没想透直接在哈希节点里存了int *ptr本地小规模测试一切正常连续插入几万个数据触发扩容后程序就随机崩溃。排查了很久才意识到是扩容导致指针失效。所以后来我给自己定了一条硬规矩数组和哈希表之间只传下标不传指针。2.3 数据冗余是刻意设计不是浪费有人可能会问哈希表节点里存 key数组里也存一份值两份数据不是冗余吗这个冗余确实是刻意设计的。哈希表节点只管key和idx它不负责数据生命周期的管理数组才是唯一真正“持有”数据的地方。插入、删除、随机全部以数组为准哈希表永远是数组的索引。这种“一份数据 一套索引”的模式在工程界太常见了最典型的就是数据库表数据存在磁盘页里索引结构只存键和指向数据行的位置理念完全一致。理解这一点后面写删除逻辑时就不会搞混数组变了索引要跟着变索引错了数据本身也会跟着乱。3. C语言手写哈希表从零开始构建映射关系3.1 为什么必须自己造轮子C 标准库没有哈希表。你在 stdlib.h 和 string.h 里翻破天也找不到一个 hash_map。所以用 C 刷题必须自己实现一套够用的哈希表。好在 LeetCode 的测试规模一般不超过 2*10^5 次操作我们不需要工业级实现只要做到“插入、删除、查找平均 O(1)”就行。冲突处理我选的是链地址法维护一个桶数组每个桶是一个链表的头指针算完哈希值之后取模定位到桶再在对应链表里查找。为什么不选开放地址法线性探测因为开放地址法删除时要打“墓碑”标记代码绕而且随着负载升高性能会急剧恶化。链地址法实现直观、删除方便、每个节点都是独立 malloc 的内存块生命周期好控制最适合刷题场景。3.2 节点与哈希表的结构定义typedef struct HashNode { int key; // 集合中的值 int idx; // 该值在动态数组中的下标 struct HashNode *next; // 同桶链表的下一个节点 } HashNode; typedef struct { HashNode **buckets; // 桶数组每个元素是链表头指针 int bucketCount; // 桶的数量 int size; // 哈希表中键值对总数 } HashMap;哈希函数我直接用了取模int hashKey(int key, int bucketCount) { return (unsigned)key % bucketCount; }3.3 哈希函数里的 C 语言陷阱负数取模这个哈希函数值得展开说因为它至少涉及两个经典 C 坑。第一为什么要先转(unsigned)key因为 C 语言里负数对正数取模结果还是负数。-7 % 16在 C 里结果是-7拿一个负数下标去访问桶数组直接越界崩溃。转成 unsigned 后取模结果一定落在[0, bucketCount)。第二为什么不直接abs(key) % bucketCount因为abs(INT_MIN)是未定义行为结果会溢出成负数。一旦集合里真的出现INT_MIN程序当场爆炸。而(unsigned)INT_MIN % bucketCount完全合法结果稳定。第三取模在 key 分布随机时完全够用。即使 key 有明显规律比如全是偶数链地址法也能吃得住冲突因为负载因子控制住了每个桶的平均长度。有人会担心bucketCount必须是质数才能让取模均匀那是开放地址法时代的老黄历对链地址法来说桶数量用 2 的幂完全没问题。3.4 put / get / remove 三个基础操作查询函数最直接算出桶下标沿链表找 key找到返回 idx找不到返回 -1。-1 永远不会和合法下标冲突因为数组下标从 0 开始。int hashGet(HashMap *map, int key) { int h hashKey(key, map-bucketCount); HashNode *cur map-buckets[h]; while (cur ! NULL) { if (cur-key key) { return cur-idx; } cur cur-next; } return -1; }插入用头插法新节点直接挂在桶链表最前面不需要遍历找尾节点天生 O(1)。插入前检查负载因子超过 0.7 就先扩容void hashPut(HashMap *map, int key, int idx) { if ((map-size 1) * 10 map-bucketCount * 7) { hashRehash(map, map-bucketCount * 2); } int h hashKey(key, map-bucketCount); HashNode *node (HashNode*)malloc(sizeof(HashNode)); node-key key; node-idx idx; node-next map-buckets[h]; map-buckets[h] node; map-size; }删除操作要遍历链表找到后修改前驱节点的next指针注意头结点的特判void hashRemove(HashMap *map, int key) { int h hashKey(key, map-bucketCount); HashNode *cur map-buckets[h]; HashNode *prev NULL; while (cur ! NULL) { if (cur-key key) { if (prev NULL) { map-buckets[h] cur-next; } else { prev-next cur-next; } free(cur); map-size--; return; } prev cur; cur cur-next; } }3.5 负载因子与 rehash保证“期望 O(1)”的关键如果桶的数量固定不变插入越来越多每个桶的链表会越来越长查找慢慢就退化成了线性扫描。所以要在负载因子size / bucketCount过高时把桶数组扩大把旧节点全部重新分布到新桶数组里。我设的阈值是 0.7即(size 1) * 10 bucketCount * 7时翻倍。rehash 的实现就是遍历所有旧桶的链表把节点取下来重新计算桶下标挂到新桶数组里。节点本身不重新 malloc搬家的只是“桶归属关系”void hashRehash(HashMap *map, int newBucketCount) { HashNode **oldBuckets map-buckets; int oldCount map-bucketCount; map-buckets (HashNode**)calloc(newBucketCount, sizeof(HashNode*)); map-bucketCount newBucketCount; for (int i 0; i oldCount; i) { HashNode *cur oldBuckets[i]; while (cur ! NULL) { HashNode *next cur-next; int h hashKey(cur-key, map-bucketCount); cur-next map-buckets[h]; map-buckets[h] cur; cur next; } } free(oldBuckets); }有个细节因为一直用头插rehash 后每个桶里链表的顺序会反转。这道题无所谓哈希表只关心“键是否存在、对应下标是多少”不关心桶内部顺序。但如果你在其他场景依赖链表顺序就需要注意。提示负载因子阈值选 0.7 是时间和空间的折中。阈值越小桶越稀疏查找越快但内存越浪费阈值太接近 1链表变长查找变慢。工程里常见默认值是 0.75写成 7/10 是为了避免浮点运算。4. 动态数组 删除操作的“障眼法”用覆盖避免 O(n)4.1 数组为什么“不敢”删除中间元素动态数组负责数据本体插入很简单末尾追加满了扩容。但删除是这道题真正的陷阱。假设数组是[7, 2, 9, 4]要删除9下标 2。如果只把下标 2 的元素置 0数组里会留下一个“洞”size 没法正确减一getRandom 随机到洞上就全乱套。要让“数组前 size 个位置都是有效元素”常规做法是把9后面的所有元素往前挪一位得到[7, 2, 4]。这一步需要移动 O(n) 个元素违反题目的 O(1) 要求。于是这里就用一个经典技巧不但不把后面的元素往前挪反而把最后一个元素搬过来覆盖被删的位置。4.2 用“末尾元素覆盖”实现 O(1) 删除还是[7, 2, 9, 4]删除9。先把最后一个元素4下标 3拿来覆盖下标 2数组变成[7, 2, 4, 4]然后把 size 减一逻辑数组变成[7, 2, 4]。被删的9已经不存在末尾残留的旧值4也无所谓因为 size 已经不再把它当作有效元素。这个操作的时间复杂度是 O(1)一次数组赋值一次 size 自减。代价是数组中元素的相对顺序被破坏了原来下标 2 和下标 3 的先后顺序没了。所以这个技巧只能用于“对顺序没有要求”的集合而本题恰好只要求等概率随机返回不要求保序完美适配。真正的难点在联动更新。被删位置换成了4哈希表里4对应的下标就必须从 3 改成 2。完整顺序是用哈希表查到9的下标delIdx 2。取数组最后一个元素lastVal 4、lastIdx 3。从哈希表里删除key 9的条目。如果delIdx ! lastIdx把arr.data[2]覆盖成4并把哈希表里key 4的下标改为 2。arr.size--。下面这张表可以直观看到删除过程中数组和哈希表的每一步变化阶段数组内容哈希表部分初始[7, 2, 9, 4]7→0, 2→1, 9→2, 4→3移除 9 的映射[7, 2, 9, 4]7→0, 2→1, 4→3末尾元素覆盖[7, 2, 4, 4]7→0, 2→1, 4→3更新 4 的下标[7, 2, 4, 4]7→0, 2→1, 4→2size 减一逻辑数组 [7, 2, 4]7→0, 2→1, 4→24.3 删除同步更新的代码细节对应到 C 代码就是下面这一段注意delIdx ! lastIdx的判断bool randomizedSetRemove(RandomizedSet *obj, int val) { int delIdx hashGet(obj-map, val); if (delIdx -1) { return false; } int lastIdx obj-arr.size - 1; int lastVal obj-arr.data[lastIdx]; hashRemove(obj-map, val); // 第一步删掉 val 的索引条目 if (delIdx ! lastIdx) { obj-arr.data[delIdx] lastVal; // 第二步末尾元素覆盖被删位置 hashRemove(obj-map, lastVal); // 第三步更新 lastVal 的索引 hashPut(obj-map, lastVal, delIdx); } obj-arr.size--; // 第四步逻辑删除末尾 return true; }如果删除的本来就是最后一个元素那么delIdx lastIdxlastVal就是val本身这时哈希表里val的条目已经被第一步删掉了不能再执行hashRemove(lastVal)和hashPut(lastVal, delIdx)否则就是对同一个 key 做无意义甚至危险的操作。这个if判断毛糙一点就会漏我在踩坑部分还会再强调。4.4 数组容量管理与 realloc 的坑数组初始容量我设为 8每次满了翻倍if (obj-arr.size obj-arr.capacity) { obj-arr.capacity * 2; obj-arr.data (int*)realloc(obj-arr.data, sizeof(int) * obj-arr.capacity); }realloc 有三种表现原地扩大、搬家复制、失败返回 NULL。原地扩大时指针不变搬家时 realloc 内部会复制旧数据并释放旧内存新指针可能完全不同。好在哈希表里只存下标不存指针搬家不会破坏映射关系这就是前面强调“只传下标不传指针”的回报。注意realloc 失败会返回 NULL但原指针依然有效。如果直接arr.data realloc(...)一旦失败就把原指针覆盖成 NULL造成泄漏。刷题时我们默认内存充足不处理这种情况但在项目代码里务必先用临时变量接住返回值再判空。5. 完整代码实现与用例验证5.1 可直接复制提交的完整代码把前面拆开的哈希表函数、数组管理和 RandomizedSet 的接口整合在一起加齐头文件就是一份能直接粘到 LeetCode 编辑器里的完整实现#include stdbool.h #include stdlib.h #include time.h typedef struct HashNode { int key; int idx; struct HashNode *next; } HashNode; typedef struct { HashNode **buckets; int bucketCount; int size; } HashMap; typedef struct { int *data; int size; int capacity; } DynamicArray; typedef struct { DynamicArray arr; HashMap map; } RandomizedSet; int hashKey(int key, int bucketCount) { return (unsigned)key % bucketCount; } void hashRehash(HashMap *map, int newBucketCount) { HashNode **oldBuckets map-buckets; int oldCount map-bucketCount; map-buckets (HashNode**)calloc(newBucketCount, sizeof(HashNode*)); map-bucketCount newBucketCount; for (int i 0; i oldCount; i) { HashNode *cur oldBuckets[i]; while (cur ! NULL) { HashNode *next cur-next; int h hashKey(cur-key, map-bucketCount); cur-next map-buckets[h]; map-buckets[h] cur; cur next; } } free(oldBuckets); } void hashPut(HashMap *map, int key, int idx) { if ((map-size 1) * 10 map-bucketCount * 7) { hashRehash(map, map-bucketCount * 2); } int h hashKey(key, map-bucketCount); HashNode *node (HashNode*)malloc(sizeof(HashNode)); node-key key; node-idx idx; node-next map-buckets[h]; map-buckets[h] node; map-size; } int hashGet(HashMap *map, int key) { int h hashKey(key, map-bucketCount); HashNode *cur map-buckets[h]; while (cur ! NULL) { if (cur-key key) { return cur-idx; } cur cur-next; } return -1; } void hashRemove(HashMap *map, int key) { int h hashKey(key, map-bucketCount); HashNode *cur map-buckets[h]; HashNode *prev NULL; while (cur ! NULL) { if (cur-key key) { if (prev NULL) { map-buckets[h] cur-next; } else { prev-next cur-next; } free(cur); map-size--; return; } prev cur; cur cur-next; } } RandomizedSet* randomizedSetCreate() { RandomizedSet *obj (RandomizedSet*)malloc(sizeof(RandomizedSet)); obj-arr.capacity 8; obj-arr.size 0; obj-arr.data (int*)malloc(sizeof(int) * obj-arr.capacity); obj-map.bucketCount 16; obj-map.size 0; obj-map.buckets (HashNode**)calloc(obj-map.bucketCount, sizeof(HashNode*)); srand((unsigned)time(NULL)); return obj; } bool randomizedSetInsert(RandomizedSet *obj, int val) { if (hashGet(obj-map, val) ! -1) { return false; } if (obj-arr.size obj-arr.capacity) { obj-arr.capacity * 2; obj-arr.data (int*)realloc(obj-arr.data, sizeof(int) * obj-arr.capacity); } obj-arr.data[obj-arr.size] val; hashPut(obj-map, val, obj-arr.size); obj-arr.size; return true; } bool randomizedSetRemove(RandomizedSet *obj, int val) { int delIdx hashGet(obj-map, val); if (delIdx -1) { return false; } int lastIdx obj-arr.size - 1; int lastVal obj-arr.data[lastIdx]; hashRemove(obj-map, val); if (delIdx ! lastIdx) { obj-arr.data[delIdx] lastVal; hashRemove(obj-map, lastVal); hashPut(obj-map, lastVal, delIdx); } obj-arr.size--; return true; } int randomizedSetGetRandom(RandomizedSet *obj) { int idx rand() % obj-arr.size; return obj-arr.data[idx]; } void randomizedSetFree(RandomizedSet *obj) { for (int i 0; i obj-map.bucketCount; i) { HashNode *cur obj-map.buckets[i]; while (cur ! NULL) { HashNode *tmp cur; cur cur-next; free(tmp); } } free(obj-map.buckets); free(obj-arr.data); free(obj); }这段代码在 LeetCode 官方 C 语言环境下可以直接提交不需要额外依赖任何第三方头文件。5.2 用官方示例手推一遍题目给的示例是输入: [RandomizedSet,insert,remove,insert,getRandom,remove,insert,getRandom] [[],[1],[2],[2],[],[1],[2],[]] 输出: [null,true,false,true,2,true,false,2]一步一步推RandomizedSet()创建空集合。insert(1)集合中没有 1插入返回 true。数组变为[1]哈希表{1:0}。remove(2)集合中没有 2返回 false。状态不变。insert(2)集合中没有 2插入。数组变为[1,2]哈希表{1:0, 2:1}返回 true。getRandom()size 为 2随机下标是 0 或 1可能返回 1 或 2。示例输出是 2。remove(1)查到 1 的下标是 0数组最后一个元素是 2下标 1。删掉哈希表里的 1把 2 覆盖到下标 0更新哈希表{2:0}size 变为 1数组逻辑上变为[2]返回 true。insert(2)哈希表里已经有 2返回 false。getRandom()集合里只剩 2返回 2。第七步是关键验证点如果删除 1 时没有同步更新 2 的下标哈希表里2还指向 1那么insert(2)会因为hashGet返回 1而不是 -1而错误地认为 2 不存在结果变成插入成功。整条链路的一致性就在这。5.3 提交表现参考在 LeetCode 上这份 C 代码的时间通常在 80ms~130ms 浮动空间在 25MB 左右击败率会随着测试数据波动不必太在意。真正重要的是手写哈希表 手动扩容这套逻辑在 2*10^5 规模下运行得很稳没有出现超时或内存异常。6. 提交过程中容易踩的坑6.1 删除时哈希表更新的先后顺序删除逻辑最忌讳的就是顺序搞反。核心原则是先通过哈希表定位再动手改数组最后同步哈希表。正确顺序我已经写在代码里先hashGet拿到delIdx再hashRemove(val)然后覆盖数组。如果你先覆盖数组再回头查哈希表数组里被删位置已经被lastVal占领此时再想拿到val的原始下标就难了。更隐蔽的错误是在覆盖数组之前就把lastVal的哈希条目删掉结果数组覆盖完成后忘了重新插入哈希表里直接少了一条映射之后insert(lastVal)会错误地认为它不存在。6.2 “删除最后一个元素”的特殊分支必须单独处理当delIdx lastIdx时我们已经在第一步删掉了val的哈希条目数组也不需要覆盖直接size--收工。如果不加if (delIdx ! lastIdx)这个保护而是统一执行hashRemove(lastVal)和hashPut(lastVal, delIdx)就会对同一个 key 做两次删除等于把别的节点也一起删了或者造成链表操作混乱。我在实现里加了保护你如果自己写务必保留这个分支判断。6.3 rand() 的随机范围和小样本偏向RAND_MAX在不同平台差异很大。Linux 的 glibc 下是 2147483647Windows 的 MSVC 下只有 32767。如果集合里有 50000 个元素在 MSVC 平台上rand() % size虽然不会越界但低位的随机性和均匀性都很差。LeetCode 评测机是 Linux GCC直接取模能过但如果你在本地用 VS 调试发现随机结果有明显偏向可以用rand() * (RAND_MAX 1) rand()缝合两个随机数再取模均匀性会好很多。另一个小坑是 srand 的调用位置。srand 只应该在randomizedSetCreate里调用一次千万别放在getRandom里否则每次调用都重置随机种子连续调用会返回同一个值。我在完整代码里把srand((unsigned)time(NULL))放在 create 里这是正确的位置。6.4 getRandom 在空集合上的除零rand() % 0是未定义行为实际运行时大概率直接崩溃。题目保证 getRandom 只在集合非空时调用LeetCode 测试不会踩这个雷。但如果你在本地做压力测试或者以后复用这套代码建议加一行防御int randomizedSetGetRandom(RandomizedSet *obj) { if (obj-arr.size 0) { return -1; } int idx rand() % obj-arr.size; return obj-arr.data[idx]; }虽然题目用不上但“对空集合有明确行为”是合格 C 代码的基本素养。6.5 内存释放的顺序不能乱randomizedSetFree的顺序必须是先释放所有哈希节点再释放桶数组然后释放动态数组数据最后释放 RandomizedSet 本身。反过来释放会先丢指针后面就没法遍历链表了。哈希节点是每次hashPut时单独 malloc 的数量等于集合元素个数遍历所有桶逐一 free 是必须的否则就是一堆悬挂指针。提示LeetCode 的在线评测并不严格检查每个对象的内存泄漏但如果多次测试在同一个进程里跑泄漏的内存会累积可能导致后面的用例出现奇怪的内存错误。养成随手写好 Free 函数的习惯对本地调试也有帮助。7. 复杂度分析与后续扩展7.1 三个操作的复杂度验证操作平均时间复杂度主要步骤insertO(1) 摊销哈希查询 O(1) 尾部插入 O(1)扩容和 rehash 均摊removeO(1) 摊销哈希定位 O(1) 覆盖 O(1) 哈希更新 O(1)getRandomO(1)随机下标 直接返回空间复杂度是 O(n)由三部分组成动态数组存 n 个 int哈希表存 n 个节点桶数组本身。数组扩容到 2 倍容量时最坏情况下容量接近 2n所以实际空间是 O(n) 级别常数稍大但规模完全可控。7.2 从 380 到 381允许重复元素时怎么改LeetCode 381 是同一道题的“允许重复”版本默认你已经掌握了 380 的核心。区别只有一点哈希表的 value 从“单个下标”变成“一组下标的集合”。数组依然存值每个值可能出现多次哈希表的每个 key 对应一个下标容器这个容器可以用另一个简化哈希表实现也可以直接用链表。删除时从该值的下标集合里随便取一个下标用它和数组最后一个元素做覆盖交换再同步更新两个值各自的下标集合。整体思路完全是从 380 长的如果你把 380 的一致性维护逻辑吃透了381 只是给 value 包了一层容器写起来就是时间问题。7.3 这套结构在真实工程里还能干什么哈希表 动态数组的组合在算法题之外非常常见。在线抽奖系统需要一个“可快速去重、可等概率抽取、抽取后快速移除”的奖品池用户 ID 放数组哈希表记录 ID 在数组中的位置中奖用户用覆盖法移除抽奖过程天然等概率。游戏服务器的随机昵称池、随机匹配队列本质也是同一套结构。数据库里的“表数据 索引”更是这种模式的高配版数据是本体索引负责快速定位只是工程实现换成了 B 树而已。所以这道题虽然挂着“LeetCode 380”的名字实际上是一个在现实系统中反复出现的工程模式的最小演示。把“两个结构如何保持同步”这个问题想明白很多系统的核心数据路径就不再神秘了。最后说点题外的感受。用 C 语言刷题最大的福利就是没有现成的哈希表可用逼你手写一遍之后你对“哈希表到底是什么、为什么平均 O(1)”的理解会和背 API 完全不同。刷完 380 我再去做 381思路几乎是平移过去的只花了大半个晚上就写完了。如果你也是 C 党我强烈建议别一上来就依赖 uthash先手写一个链地址法版本等真正理解了内部机制再回头看那些现成库会发现它们的 API 设计反而更好懂了。