js set底层实现
JavaScript Set 的底层实现
JavaScript 中的 Set 是一种集合数据结构，用于存储唯一值。其底层实现通常基于哈希表或类似机制，以确保高效的插入、删除和查找操作。
哈希表的基本原理
Set 的底层实现通常使用哈希表来存储元素。哈希表通过哈希函数将键（或值）映射到特定的索引位置，从而实现快速访问。
- 哈希函数：将输入值转换为固定长度的哈希值，用于确定存储位置。
- 冲突处理：当多个值映射到同一位置时，通常采用链地址法（链表）或开放寻址法解决冲突。
关键操作的时间复杂度
- 插入（
add）：平均时间复杂度为 O(1)，最坏情况下（哈希冲突严重）为 O(n)。 - 删除（
delete）：平均时间复杂度为 O(1)，最坏情况下为 O(n)。 - 查找（
has）：平均时间复杂度为 O(1)，最坏情况下为 O(n)。
示例代码
以下是一个简化版的 Set 实现，展示其核心逻辑：
class SimpleSet {
constructor() {
this._items = {};
}
add(value) {
this._items[value] = true;
return this;
}
has(value) {
return this._items[value] === true;
}
delete(value) {
if (this.has(value)) {
delete this._items[value];
return true;
}
return false;
}
clear() {
this._items = {};
}
get size() {
return Object.keys(this._items).length;
}
}浏览器和引擎的优化
现代 JavaScript 引擎（如 V8、SpiderMonkey）对 Set 的实现进行了高度优化：
- 内存效率：使用紧凑的存储结构减少内存占用。
- 性能优化：针对常见操作（如迭代、批量插入）进行特殊处理。
- 类型特化：对数字、字符串等常见类型采用特化实现。
使用注意事项
Set中的值是基于严格相等（===）比较的，因此5和"5"被视为不同值。NaN在Set中被视为等于自身，尽管NaN !== NaN在其他情况下成立。- 对象引用是唯一的，因此两个内容相同的对象会被视为不同的值。
与其他数据结构的对比
- 与数组对比：
Set提供了更快的查找和去重功能，但无法通过索引访问。 - 与对象对比：
Set专门为存储值设计，而对象更适合键值对存储。
