JavaScript中Map的实现原理

---

核心实现：哈希表

哈希表是实现 Map 理想的数据结构，因为它能提供非常高效的查找、插入和删除操作，平均时间复杂度接近 O(1)。

为什么哈希表能实现这个效果？ 它的核心思想是使用一个哈希函数 (Hash Function) 将一个键 (key) 转换成一个数字（哈希值），然后将这个数字映射到内部数组的一个索引上。数据就存储在这个数组对应的位置。

基本工作流程：

1. 设置值 (set(key, value)):
   • 对键 key 应用哈希函数，计算出一个哈希值。
   • 将这个哈希值通过某种运算（比如取模 %）转换到内部数组的一个索引 index。
   • 将键值对存储到数组的 index 位置。
2. 获取值 (get(key)):
   • 对同一个键 key 再次应用相同的哈希函数，得到相同的哈希值。
   • 计算出相同的索引 index。
   • 直接去数组的 index 位置读取数据。

正因为通过索引直接访问数组元素是极快的，所以 Map 的操作才如此高效。

关键技术点与优化

单纯的哈希表会遇到一些问题，JS 引擎的实现中会使用高级技术来解决它们。

哈希冲突处理

当两个不同的键经过哈希函数计算后得到了相同的数组索引，就发生了哈希冲突。Map 必须有能力处理这种情况。

解决方案： 最常见的解决方案是链地址法 (Separate Chaining)。数组的每一个位置不再直接存储一个键值对，而是存储一个链表（或数组）。当发生冲突时，新的键值对会被添加到这个索引对应的链表中。

• 查找时：先通过索引找到链表，然后再遍历这个短链表来找到准确的键（使用严格相等 === 进行比较）。
• 优化：为了保持高效，引擎会监控哈希表的"负载因子"（已用位置/总位置）。当负载因子过高时，会执行"扩容"（Rehashing），即创建一个更大的新数组，并重新计算所有键的哈希值和新索引，然后将数据迁移过去。这虽然是一次昂贵的操作，但平均摊还下来，依然能保持 O(1) 的时间复杂度。

键的多样性支持

与普通对象（Object）只能使用字符串或 Symbol 作为键不同，Map 的键可以是任何类型，包括对象、函数、数字、字符串等。

实现方式： 引擎会为每个键（尤其是对象这样的引用类型）生成一个唯一的标识符或内部哈希码，用于计算哈希值。这个细节对 JavaScript 开发者是完全透明的。

迭代顺序维护

Map 的一个关键特性是它保持键的插入顺序。当你用 for...of 循环遍历 Map 时，得到的顺序与你插入 set 的顺序一致。

实现方式： 单纯的哈希表本身不记录插入顺序。为了实现这个特性，引擎在哈希表之外，还会维护一个双向链表（或类似的有序数据结构）来记录键值对的插入顺序。

• 当你插入一个新的键值对时，它既会被放入哈希表中，也会被追加到链表的末尾。
• 当你遍历 Map 时，引擎实际上是在遍历这个链表，从而保证了顺序。
• 删除操作也需要同时从哈希表和链表中移除该项。

这是一种典型的空间换时间的策略，用额外的内存开销来换取确定的迭代顺序。

总结：实现效果的原因

Map 能实现哈希表的效果是因为：

1. 基于哈希函数： 使用哈希函数将键快速映射到内存地址，实现了平均 O(1) 的访问速度。
2. 处理冲突： 使用链地址法等技术妥善处理哈希冲突，保证数据的正确性。
3. 动态扩容： 在数据量增加时自动扩容，维持高效的性能。
4. 维护顺序： 通过额外的数据结构（如链表）来维护插入顺序，满足了 ECMAScript 规范的要求。
5. 引擎优化： 像 V8 这样的引擎还会根据 Map 的大小和操作类型进行多种优化（例如，对于小 Map 可能使用不同的底层表示），但这些实现细节对开发者是隐藏的。

与Object的对比

特性	Map	Object
键类型	任意值	String 或 Symbol
迭代顺序	可靠的插入顺序	不可靠（虽然现代规范也定义了顺序，但规则复杂）
大小获取	size 属性（O(1)）	手动计算（O(n)）
性能	在频繁增删键值对的场景下优化得更好	未针对频繁增删进行特殊优化
默认原型	无	有，可能意外地从原型链上继承到键名

结论： JavaScript 的 Map 是一种高级抽象，其底层核心是哈希表，并辅以链表等数据结构来处理冲突和维护顺序。正是这种实现使得它具备了快速查找和有序迭代的强大特性。

---

Map Set 映射和集合

---

Map

是一个带键的数据项的集合，就像一个 Object 一样。 但是它们最大的差别是 Map 允许任何类型的键（key）。 它的方法和属性如下：

• new Map([[键,值],[键,值]]) —— 创建 map。
• map.set(key, value) —— 根据键存储值。
• map.get(key) —— 根据键来返回值，如果 map 中不存在对应的 key，则返回 undefined。
• map.has(key) —— 如果 key 存在则返回 true，否则返回 false。
• map.delete(key) —— 删除指定键的值。
• map.clear() —— 清空 map。
• map.size —— 返回当前元素个数。 每一次 map.set 调用都会返回 map 本身，所以我们可以进行“链式”调用

如果要在 map 里使用循环，可以使用以下三个方法：

• map.keys() —— 遍历并返回一个包含所有键的可迭代对象，
• map.values() —— 遍历并返回一个包含所有值的可迭代对象，
• map.entries() —— 遍历并返回一个包含所有实体 [key, value] 的可迭代对象，for..of 在默认情况下使用的就是这个。

从对象创建Map：

let obj = {
    name: "dano",
    age: 21,
};

let map = new Map(Object.entries(obj));

console.log(map);//Map(2) { 'name' => 'dano', 'age' => 21 }

从Map创建对象：

let prices = Object.fromEntries([
    ['shitr', 2],
    ['apple', 23],
    ['fruit',43]
])

console.log(prices);//{ shitr: 2, apple: 23, fruit: 43 }

Set

Set 是一个特殊的类型集合 —— “值的集合”（没有键），它的每一个值只能出现一次。 它的主要方法如下：

• new Set(iterable) —— 创建一个 set，如果提供了一个 iterable 对象（通常是数组），将会从数组里面复制值到 set 中。
• set.add(value) —— 添加一个值，返回 set 本身
• set.delete(value) —— 删除值，如果 value 在这个方法调用的时候存在则返回 true ，否则返回 false。
• set.has(value) —— 如果 value 在 set 中，返回 true，否则返回 false。
• set.clear() —— 清空 set。
• set.size —— 返回元素个数。

我们有客人来访，我们想记住他们每一个人。但是已经来访过的客人再次来访，不应造成重复记录。每个访客必须只被“计数”一次。

let set = new Set();

set.add({ name: 'dano' }).add({ name: 'jungle' });

console.log(set.size);//2

for (let value of set) {
    console.log(value.name);
    //dano jungle
}

注意一件有趣的事儿。forEach 的回调函数有三个参数：一个 value，然后是 同一个值 valueAgain，最后是目标对象。没错，同一个值在参数里出现了两次。

forEach 的回调函数有三个参数，是为了与 Map 兼容。当然，这看起来确实有些奇怪。但是这对在特定情况下轻松地用 Set 代替 Map 很有帮助，反之亦然。

Map 中用于迭代的方法在 Set 中也同样支持：

• set.keys() —— 遍历并返回一个包含所有值的可迭代对象，
• set.values() —— 与 set.keys() 作用相同，这是为了兼容 Map，
• set.entries() —— 遍历并返回一个包含所有的实体 [value, value] 的可迭代对象，它的存在也是为了兼容 Map。

弱映射和弱集合

---

WeakMap 和 Map 的第一个不同点就是，WeakMap 的==键必须是对象，不能是原始值== 如果我们在 weakMap 中使用一个对象作为键，并且没有其他对这个对象的引用 —— 该对象将会被从内存（和map）中自动清除。也就是说WeakMap并不能阻止对象被回收，而普通的Map可以。

let obj = { name: 'dano' };

//let map = new Map().set(obj, "shit");
let weakmap = new WeakMap().set(obj, "shit2");

obj = null;

//console.log(map.get(obj));
console.log(weakmap.get(obj));

WeakMap 的主要应用场景是 额外数据的存储。

假如我们正在处理一个“属于”另一个代码的一个对象，也可能是第三方库，并想存储一些与之相关的数据，那么这些数据就应该与这个对象共存亡 —— 这时候 WeakMap 正是我们所需要的利器。

我们将这些数据放到 WeakMap 中，并使用该对象作为这些数据的键，那么当该对象被垃圾回收机制回收后，这些数据也会被自动清除。

WeakSet 的表现类似：

• 与 Set 类似，但是我们只能向 WeakSet 添加对象（而不能是原始值）。
• 对象只有在其它某个（些）地方能被访问的时候，才能留在 WeakSet 中。
• 跟 Set 一样，WeakSet 支持 add，has 和 delete 方法，但不支持 size 和 keys()，并且不可迭代。

WeakSet 是类似于 Set 的集合，它仅存储对象，并且一旦通过其他方式无法访问这些对象，垃圾回收便会将这些对象删除。

在 JavaScript 中，Set 是 ES6 引入的一种集合数据结构，用于存储唯一的值（不允许重复）。它类似于数组，但成员的值都是唯一的，没有重复项。Set 本身是一个构造函数，用于创建 Set 实例。

Set 的基本特性

1. 值的唯一性：Set 中的每个值都是唯一的，无论添加多少次相同的值，最终只会保留一个。
   （判断唯一性的方式类似 ===，但特殊地，NaN 被视为与自身相等，这与 === 不同）

2. 无序性：Set 中的元素没有索引，无法通过下标访问（与数组不同）。

3. 可迭代性：Set 是可迭代对象，可通过 for...of 循环遍历，也支持扩展运算符（...）。

Set 的常用方法与属性

1. 基本操作

• new Set([iterable])：创建 Set 实例，可选参数为可迭代对象（如数组），会自动去重。
• add(value)：添加值，返回 Set 本身（可链式调用）。
• delete(value)：删除值，返回布尔值（是否删除成功）。
• has(value)：判断是否包含某个值，返回布尔值。
• clear()：清空所有元素，无返回值。
• size：属性，返回元素个数（类似数组的 length）。

示例：

// 创建 Set（自动去重）
const set = new Set([1, 2, 2, 3, 3, 3]);
console.log(set); // Set(3) {1, 2, 3}
console.log(set.size); // 3

// 添加元素
set.add(4).add(5); // 链式调用
console.log(set); // Set(5) {1, 2, 3, 4, 5}

// 判断是否包含
console.log(set.has(3)); // true
console.log(set.has(6)); // false

// 删除元素
set.delete(2);
console.log(set); // Set(4) {1, 3, 4, 5}

// 清空
set.clear();
console.log(set.size); // 0

2. 遍历方法

Set 提供了多种遍历方式，由于元素无序，遍历顺序与插入顺序一致：

• keys()：返回键名的迭代器（Set 的键名与键值相同）。
• values()：返回键值的迭代器（常用）。
• entries()：返回 [value, value] 的迭代器（因为键名与键值相同）。
• forEach(callback)：使用回调函数遍历每个元素。

示例：

const set = new Set(['a', 'b', 'c']);

// for...of 遍历 values()
for (const value of set.values()) {
  console.log(value); // 'a' 'b' 'c'
}

// forEach 遍历
set.forEach((value) => {
  console.log(value); // 'a' 'b' 'c'
});

// 扩展运算符转为数组
const arr = [...set];
console.log(arr); // ['a', 'b', 'c']

Set 的典型应用场景

1. 数组去重：利用 Set 的唯一性快速去重。

   const arr = [1, 2, 2, 3, 3, 3];
   const uniqueArr = [...new Set(arr)]; // [1, 2, 3]

2. 判断元素是否存在：has 方法的性能优于数组的 indexOf 或 includes（尤其数据量大时）。

3. 存储不重复的集合数据：如用户ID、标签等需要唯一标识的数据。

4. 实现交集、并集、差集：

   const setA = new Set([1, 2, 3]);
   const setB = new Set([2, 3, 4]);
   
   // 并集
   const union = new Set([...setA, ...setB]); // {1, 2, 3, 4}
   
   // 交集
   const intersection = new Set([...setA].filter(x => setB.has(x))); // {2, 3}
   
   // 差集（setA 有而 setB 没有）
   const difference = new Set([...setA].filter(x => !setB.has(x))); // {1}

与数组的区别

特性	Set	数组（Array）
元素唯一性	自动去重，无重复值	允许重复值
索引访问	无索引，无法通过下标访问	有索引，可通过 [index] 访问
常用操作	增删查效率高（哈希表实现）	增删查效率受位置影响
适用场景	存储唯一值、集合运算	有序数据、需要索引访问

总结

Set 是一种高效的集合数据结构，核心优势是自动去重和快速的增删查操作。它弥补了传统数组在处理“唯一值集合”时的不足，常用于数组去重、集合运算等场景。在需要存储不重复数据且无需索引的场景中，Set 是比数组更合适的选择。