js set底层实现

JavaScript Set 的底层实现

JavaScript 的 Set 是一种集合数据结构，用于存储唯一值。其底层实现依赖于引擎（如 V8、SpiderMonkey 等），但通常基于哈希表或类似机制实现。

哈希表实现原理

Set 的核心是通过哈希表存储唯一值。当添加一个值时，引擎会计算其哈希值，并在哈希表中检查是否已存在相同的值。如果哈希值冲突，会通过链表或其他冲突解决机制处理。

关键特性

• 唯一性：通过哈希表确保每个值唯一，重复添加会被忽略。
• 迭代顺序：插入顺序决定迭代顺序，这是 ECMAScript 规范的要求。
• O(1) 时间复杂度：哈希表的设计使得添加、删除和查找操作的平均时间复杂度为 O(1)。

示例代码

const set = new Set();
set.add(1);
set.add(2);
set.add(1); // 重复值，被忽略
console.log(set.size); // 输出 2

性能优化

引擎可能对特定类型（如数字或字符串）进行优化。例如，V8 对小整数使用特殊存储方式以减少内存占用。

与其他语言对比

• Java：HashSet 也是基于哈希表，但允许自定义哈希函数。
• Python：set 类似，但迭代顺序在早期版本中不固定（Python 3.7+ 后改为插入顺序）。

使用场景

• 去重：快速去除数组中的重复项。
• 成员检查：高效判断某个值是否存在。
• 数学运算：实现并集、交集等集合操作。

注意事项

• 对象引用：Set 存储的是对象引用，两个不同对象即使内容相同也会被视为不同值。
• NaN 处理：Set 会将 NaN 视为相同的值，尽管 NaN !== NaN。