核心内容摘要
铜铜钢铿锵：解锁时代心跳的免费视听盛宴
很多新手都会混淆Set和Map也会疑惑「为什么它们的查询是 O (
」—— 我先帮你理清「Set vs Map」的关系再用通俗的方式解释「为什么时间复杂度是 O (
」全程结合前端场景保证你能分清、记牢。
先搞懂Set 和 Map 都是「哈希表」只是用途不同你昨天学的Map是哈希表今天遇到的Set同样是哈希表底层实现逻辑完全一样只是两者的「存储形式」不同 —— 可以把它们理解成「哈希表的两种不同用法」特性Map映射 / 字典Set集合存储形式键值对key: value只有值value且值唯一核心作用「映射」通过 key 找 value「去重 快速查询」判断值是否存在常用方法set(key, val)get(key)has(key)add(val)has(val)delete(val)类比生活例子通讯录名字→手机号花名册只记录名字不重复算法题常用场景两数之和存数→下标、字母异位词分组存特征键→数组最长连续序列去重 查数是否存在、数组去重用「抽屉」比喻两者的区别底层都是哈希表哈希表的底层 一排带编号的抽屉通过哈希函数计算值 / 键对应的抽屉号Map每个抽屉里放「一个信封」信封上写 key里面装 value比如抽屉 7 放「7:1」Set每个抽屉里只放「一张纸条」纸条上写值且每个抽屉最多放一张不重复比如抽屉 7 放「7」再放 7 就会被忽略。
前端算法题里的选择原则新手直接记需要「键值对应」比如存数的下标、存分组数组→ 用Map只需要「去重」或「快速判断值是否存在」→ 用Set更简洁。
代码示例Set 的基础用法对应最长连续序列javascript运行//
初始化空Set const numSet new Set(); //
添加值自动去重 numSet.add(
; numSet.add(
; numSet.add(
; // 重复值不会添加 //
判断值是否存在O(
console.log(numSet.has(
); // true console.log(numSet.has(
); // false //
遍历Set for (const num of numSet) { console.log(num); //
2去重后的结果 }
为什么 Set/Map 的has方法是 O (
核心你可能会问「Set 里存了一堆数找某个数为什么不用遍历」—— 答案和你之前学的 Map 一样Set/Map 的底层是哈希表查询时通过「哈希函数」直接定位值的存储位置不是遍历。
再用「快递柜」比喻简化版底层逻辑存值时比如往 Set 里加数字100哈希函数会计算100的哈希值比如100 % 10 0直接把100放进「0 号快递柜」不用管其他柜子。
查询时numSet.has(
先用同一个哈希函数计算100的哈希值 → 0 号柜直接打开 0 号柜看里面有没有100→ 有就返回 true没有就返回 false整个过程只有「计算哈希值 开柜」两步和 Set 里有多少个数无关哪怕有 1000 个数找 100 还是只查 0 号柜。
对比数组的includes是 O (n)Set 的has是 O (
用 10 万条数据做对比你能直观看到差异javascript运行//
准备10万个数字 const nums []; for (let i 0; i 100000; i) { nums.push(i); } const numSet new Set(nums); //
数组查询includes遍历找99999O(n) console.time(数组查询); nums.includes(
; console.timeEnd(数组查询); // 耗时约5ms随数据量增长 //
Set查询has直接定位O(
console.time(Set查询); numSet.has(
; console.timeEnd(Set查询); // 耗时约
01ms几乎不随数据量增长关键结论数组的includes要从第一个数开始遍历直到找到目标值最坏遍历整个数组→ O (n)Set/Map 的has通过哈希函数直接定位存储位置一步到位 → O (
。
回到「最长连续序列」理解 Set 的作用这道题用 Set 而不用 Map核心原因是去重比如数组[0,0,1]去重后只需要处理
1避免重复计算序列长度快速查询判断num-1/num1是否存在时用numSet.has()O (
如果用数组的includes会变成 O (n²)不符合题目「O (n) 时间复杂度」的要求。
反例不用 Set用数组的后果javascript运行var longestConsecutive function(nums) { if (nums.length
return 0; let maxLength 1; // 不用Set直接遍历数组去重都没做 for (const num of nums) { if (!nums.includes(num -
) { // includes是O(n) let currentNum num; let currentLength 1; while (nums.includes(currentNum
) { // includes是O(n) currentNum; currentLength; } maxLength Math.max(maxLength, currentLength); } } return maxLength; }; // 输入10万条数据时这个代码会卡死O(n²)复杂度而用Set的版本能快速运行
总结Set 和 Map 的关系都是哈希表Map 存「键值对」映射Set 存「唯一值」去重 查询底层查询都是 O (
O (
的原因通过哈希函数直接定位存储位置不用遍历查询时间和数据量无关最长连续序列用 Set 的原因去重 O (
快速判断数是否存在保证整体时间复杂度是 O (n)。
现在你能分清 Set 和 Map 了也懂了为什么它们的查询是 O (
—— 如果还有哪个细节没懂比如 Set 的 add 方法、哈希函数的具体计算都可以问我会拆到最基础的层面set为什么每个只存一个怎么计算的比如7和17/27你问的这两个问题刚好是理解 Set 核心特性的关键 ——「为什么 Set 只存一个重复值」「哈希冲突时 Set 怎么处理比如
7、
27」我用「大白话 底层逻辑 示例」帮你彻底讲透还是结合你熟悉的「快递柜」比喻保证好懂。
先懂Set 为什么「每个值只存一个」去重原理Set 的核心定义就是「值的集合且所有值唯一重复添加会被忽略」—— 这不是复杂的计算而是 Set 的「内置规则」底层实现时会先判断值是否已存在再决定是否添加。
Set 添加值的完整流程以添加 7 为例当你执行set.add(
时Set 会做两步操作① 用哈希函数计算 7 的哈希值比如7 % 10 7找到对应的存储位置7 号快递柜② 检查 7 号柜里是否已有「7」这个值如果没有 → 把 7 存进去如果已有 → 直接忽略不做任何操作。
代码验证重复添加会被忽略javascript运行const set new Set(); set.add(
; // 7号柜空存入7 set.add(
; // 7号柜已有7忽略 set.add(
; // 哈希值17%1077号柜没有17存入17 console.log(set); // 输出 Set {7, 17}没有重复的
核心结论Set 的「去重」不是靠「计算」而是靠「添加前的存在性检查」—— 每次 add 值时都会先通过哈希表的 O (
查询判断值是否已存在存在就跳过不存在才存入所以最终 Set 里不会有重复值。
再懂
7、
27 共存时Set 怎么计算 / 存储哈希冲突处理你问的
7、
27按「哈希函数 值 %10」计算哈希值都是 77%
17%
27%107—— 这就是「哈希冲突」多个值映射到同一个存储位置但 Set 依然能存下这三个值核心靠「链地址法」和 Map 的冲突处理完全一样。
用「快递柜 层板」比喻冲突处理哈希表的存储位置 快递柜编号
每个快递柜里不是只放一张纸条而是有「层板 / 小格子」链表结构每个层板可以放一个唯一值冲突的值会按顺序存在同一个柜子的不同层板里。
2.
7、