js中Set.has()是什么原理？

在 JavaScript 里，Set 是一种集合结构，用来存储 不重复的值。
Set.prototype.has(value) 就是用来检查某个值是否在这个集合里。

语法

set.has(value)

value：要检查的值
返回值：布尔值（true 表示存在，false 表示不存在）

使用示例

let s = new Set([1, 2, 3]);

console.log(s.has(2));   // true
console.log(s.has(4));   // false

底层原理

JS 的 Set 内部一般是用 哈希表(Hash Table) 或类似的数据结构实现的（规范没有强制，但主流引擎如 V8 是这样做的）。

当你调用 set.has(x) 时，大致流程是：

计算哈希值（或查找 key 索引）
引擎会根据 x 的值来定位到存储桶。
比较相等性
使用的是 SameValueZero 比较算法（类似 ===，但 NaN 和 NaN 被认为相等，+0 和 -0 被认为相等）。
返回布尔值
- 如果找到了，就返回 true
- 否则返回 false

SameValueZero 规则

1 === 1 → true
'a' === 'a' → true
NaN === NaN → false，但在 Set 中 NaN 和 NaN 视为相同
+0 和 -0 在 Set 中也被认为是相等的

let s = new Set();
s.add(NaN);
console.log(s.has(NaN)); // true

s.add(+0);
console.log(s.has(-0));  // true

时间复杂度

由于底层是哈希表，set.has(value) 的平均时间复杂度是 O(1)，非常高效。

✅ 总结：

Set.has(value) 检查某个值是否存在于 Set 中
内部基于哈希结构 + SameValueZero 相等性判断
平均复杂度 O(1)，比用 Array.includes 遍历查找更快

哈希表查找为什么时间复杂度是O1

这个问题问得非常专业 👏，我帮你分层解释一下为什么 哈希表（Hash Table）查找的时间复杂度平均是 O(1)。

1. 哈希表的结构

哈希表的核心思想是：

用一个 哈希函数 (Hash Function) 把“键”映射成 数组下标。
然后直接在这个下标位置存储或查找数据。

举个简单例子：

key: "apple"  → hash("apple") = 3 → 存到数组索引 3
key: "banana" → hash("banana") = 7 → 存到数组索引 7

这样，查找 "apple" 时只需要：

计算 hash("apple") → 3
直接访问数组[3] → 拿到结果

不需要像链表或数组那样从头到尾遍历。

2. 平均 O(1) 的原因

数组访问元素是 O(1)（直接按下标访问）。
哈希函数计算通常也被认为是 O(1)。

所以查找某个 key 的过程是：

O(1) （计算哈希值） + O(1) （访问数组）
→ 平均 O(1)

3. 冲突处理

问题是：两个不同的 key 可能会映射到同一个下标（称为 哈希冲突）。
常见解决办法有：

链地址法：在数组每个槽位存放一个链表（或更高效的红黑树）。
开放地址法：如果冲突了，就找下一个空位。

查找时如果有冲突，需要多比较几个值。
但只要哈希函数设计合理、装载因子（load factor）控制得当，平均情况下冲突数量很少，仍然可以认为是 O(1)。

4. 最坏情况

如果哈希函数很差，或者所有 key 都落在同一个槽位，那么会退化成：

链表存储时：查找 O(n)
树存储时：查找 O(log n)

所以 哈希表的查找复杂度：

平均情况：O(1)
最坏情况：O(n)

5. 举个直观类比

想象你在一个图书馆找书：

如果书是按 哈希函数分类放进柜子（比如书名 → 柜号），你只要一步就能找到 → O(1)。
如果所有书随便乱堆在一起，你得一本本翻找 → O(n)。