JavaScript中的Set和Map数据结构

JavaScript中的Set数据结构

Set的基本概念与创建

在JavaScript中，Set是一种新的数据结构，它类似于数组，但成员的值都是唯一的，没有重复的值。Set本身是一个构造函数，用于创建Set数据结构的实例。

创建一个空的Set实例非常简单，只需使用new关键字调用Set构造函数：

let mySet = new Set();

也可以在创建Set实例时传入一个可迭代对象（如数组），该可迭代对象的所有元素会被添加到新创建的Set中：

let arr = [1, 2, 3, 3, 4];
let setFromArr = new Set(arr);
console.log(setFromArr); // Set {1, 2, 3, 4}

这里，数组arr中的重复元素3在Set中只会出现一次，这体现了Set数据结构成员唯一性的特点。

Set的常用方法

1. add(value)：向Set实例中添加一个新的值。如果该值已经存在，则不会重复添加，Set的大小不会改变。

let set = new Set();
set.add(1);
set.add(2);
set.add(1);
console.log(set.size); // 2

2. delete(value)：从Set实例中删除指定的值。如果该值存在并被成功删除，返回true；否则返回false。

let set = new Set([1, 2, 3]);
console.log(set.delete(2)); // true
console.log(set.has(2)); // false

3. has(value)：判断Set实例中是否存在指定的值。如果存在返回true，否则返回false。

let set = new Set([1, 2, 3]);
console.log(set.has(2)); // true
console.log(set.has(4)); // false

4. clear()：清空Set实例中的所有成员，使其变为一个空的Set。

let set = new Set([1, 2, 3]);
set.clear();
console.log(set.size); // 0

5. size：返回Set实例的成员数量。

let set = new Set([1, 2, 3]);
console.log(set.size); // 3

Set的遍历

1. for...of循环：Set实例实现了iterable接口，所以可以使用for...of循环进行遍历。在遍历过程中，会按插入顺序依次访问Set中的每个值。

let set = new Set([1, 2, 3]);
for (let value of set) {
    console.log(value);
}
// 输出：
// 1
// 2
// 3

2. forEach()方法：Set实例也有forEach()方法，用于对Set中的每个成员执行一个给定的回调函数。与数组的forEach()类似，但Set的forEach()回调函数只接受两个参数：当前值和当前值本身（因为Set没有索引）。

let set = new Set([1, 2, 3]);
set.forEach((value, sameValue) => {
    console.log(`${value} : ${sameValue}`);
});
// 输出：
// 1 : 1
// 2 : 2
// 3 : 3

3. keys()、values()、entries()方法：Set实例的keys()和values()方法都返回一个新的迭代器对象，该对象按插入顺序包含Set实例中每个值的键（在Set中键和值是相同的）。entries()方法同样返回一个迭代器对象，不过每个迭代的值是一个包含键值对的数组，其中键和值相同。

let set = new Set([1, 2, 3]);
let keys = set.keys();
let values = set.values();
let entries = set.entries();
console.log(Array.from(keys)); // [1, 2, 3]
console.log(Array.from(values)); // [1, 2, 3]
console.log(Array.from(entries)); // [[1, 1], [2, 2], [3, 3]]

Set的应用场景

1. 数组去重：这是Set最常见的应用场景之一。由于Set会自动去除重复值，我们可以利用这一特性轻松实现数组去重。

function uniqueArray(arr) {
    return Array.from(new Set(arr));
}
let arr = [1, 2, 2, 3, 3, 3];
console.log(uniqueArray(arr)); // [1, 2, 3]

2. 交集运算：假设有两个数组，我们可以借助Set来计算它们的交集。

function intersection(arr1, arr2) {
    let set1 = new Set(arr1);
    let set2 = new Set(arr2);
    return Array.from(set1).filter(value => set2.has(value));
}
let arr1 = [1, 2, 3];
let arr2 = [2, 3, 4];
console.log(intersection(arr1, arr2)); // [2, 3]

3. 并集运算：同样利用Set的特性可以计算两个数组的并集。

function union(arr1, arr2) {
    return Array.from(new Set([...arr1, ...arr2]));
}
let arr1 = [1, 2, 3];
let arr2 = [2, 3, 4];
console.log(union(arr1, arr2)); // [1, 2, 3, 4]

4. 差集运算：计算两个数组的差集也可以通过Set实现。

function difference(arr1, arr2) {
    let set1 = new Set(arr1);
    let set2 = new Set(arr2);
    return Array.from(set1).filter(value =>!set2.has(value));
}
let arr1 = [1, 2, 3];
let arr2 = [2, 3, 4];
console.log(difference(arr1, arr2)); // [1]

JavaScript中的Map数据结构

Map的基本概念与创建

Map是JavaScript中的另一种重要数据结构，它是一种键值对的集合。与普通对象不同，Map的键可以是任意类型，而不仅仅是字符串或符号。

创建一个空的Map实例可以使用new关键字调用Map构造函数：

let myMap = new Map();

也可以在创建Map实例时传入一个可迭代对象，该可迭代对象的元素必须是包含两个元素的数组，第一个元素作为键，第二个元素作为值。

let arr = [
    ['name', 'John'],
    ['age', 30]
];
let mapFromArr = new Map(arr);
console.log(mapFromArr); // Map { 'name' => 'John', 'age' => 30 }

Map的常用方法

1. set(key, value)：向Map实例中设置一个新的键值对。如果键已经存在，则会更新其对应的值。

let map = new Map();
map.set('name', 'John');
map.set('age', 30);
map.set('name', 'Jane');
console.log(map.get('name')); // 'Jane'

2. get(key)：获取Map实例中指定键对应的值。如果键不存在，则返回undefined。

let map = new Map([['name', 'John'], ['age', 30]]);
console.log(map.get('name')); // 'John'
console.log(map.get('city')); // undefined

3. has(key)：判断Map实例中是否存在指定的键。如果存在返回true，否则返回false。

let map = new Map([['name', 'John'], ['age', 30]]);
console.log(map.has('name')); // true
console.log(map.has('city')); // false

4. delete(key)：从Map实例中删除指定键及其对应的值。如果键存在并被成功删除，返回true；否则返回false。

let map = new Map([['name', 'John'], ['age', 30]]);
console.log(map.delete('age')); // true
console.log(map.has('age')); // false

5. clear()：清空Map实例中的所有键值对，使其变为一个空的Map。

let map = new Map([['name', 'John'], ['age', 30]]);
map.clear();
console.log(map.size); // 0

6. size：返回Map实例的键值对数量。

let map = new Map([['name', 'John'], ['age', 30]]);
console.log(map.size); // 2

Map的遍历

1. for...of循环：Map实例实现了iterable接口，所以可以使用for...of循环进行遍历。在遍历过程中，会按插入顺序依次访问Map中的每个键值对。

let map = new Map([['name', 'John'], ['age', 30]]);
for (let [key, value] of map) {
    console.log(`${key} : ${value}`);
}
// 输出：
// name : John
// age : 30

2. forEach()方法：Map实例也有forEach()方法，用于对Map中的每个键值对执行一个给定的回调函数。回调函数接受三个参数：当前值、当前键和Map实例本身。

let map = new Map([['name', 'John'], ['age', 30]]);
map.forEach((value, key, mapObj) => {
    console.log(`${key} : ${value}`);
});
// 输出：
// name : John
// age : 30

3. keys()、values()、entries()方法：Map实例的keys()方法返回一个新的迭代器对象，该对象按插入顺序包含Map实例中每个键。values()方法返回一个迭代器对象，按插入顺序包含Map实例中每个值。entries()方法返回一个迭代器对象，按插入顺序包含Map实例中每个键值对（以数组形式）。

let map = new Map([['name', 'John'], ['age', 30]]);
let keys = map.keys();
let values = map.values();
let entries = map.entries();
console.log(Array.from(keys)); // ['name', 'age']
console.log(Array.from(values)); // ['John', 30]
console.log(Array.from(entries)); // [['name', 'John'], ['age', 30]]

Map与Object的比较

1. 键的类型：普通对象的键只能是字符串或符号类型，而Map的键可以是任意类型。

let obj = {};
let func = function() {};
obj[func] = 'function as key'; // 这里会将函数转换为字符串作为键
console.log(obj[func.toString()]); // 'function as key'

let map = new Map();
map.set(func, 'function as key');
console.log(map.get(func)); // 'function as key'

2. 键值对数量：普通对象没有直接获取自身属性数量的方法（需要使用Object.keys()等方法间接获取），而Map有size属性可以直接获取键值对数量。

let obj = {name: 'John', age: 30};
console.log(Object.keys(obj).length); // 2

let map = new Map([['name', 'John'], ['age', 30]]);
console.log(map.size); // 2

3. 遍历顺序：普通对象的属性遍历顺序是不确定的（在ES6之前），而Map的键值对遍历顺序是按照插入顺序。

let obj = {b: 2, a: 1};
for (let key in obj) {
    console.log(key); // 可能输出 'a' 然后 'b'，也可能相反
}

let map = new Map([['b', 2], ['a', 1]]);
for (let [key, value] of map) {
    console.log(key); // 输出 'b' 然后 'a'
}

4. 性能：在频繁添加、删除和查询操作时，Map通常比普通对象性能更好，尤其是当键不是字符串类型时。这是因为Map内部的实现机制更适合这种频繁操作的场景。

Map的应用场景

1. 缓存数据：Map可以用于缓存一些计算结果，提高程序的运行效率。例如，在一个函数中，如果相同的输入会得到相同的输出，我们可以使用Map来缓存这些输入输出对。

function expensiveCalculation(x) {
    let cache = new Map();
    if (cache.has(x)) {
        return cache.get(x);
    }
    let result = x * x;
    cache.set(x, result);
    return result;
}

2. 分组数据：假设我们有一个包含学生信息的数组，每个学生对象包含姓名和班级信息，我们可以使用Map来按班级分组学生。

let students = [
    {name: 'John', class: 'A'},
    {name: 'Jane', class: 'B'},
    {name: 'Bob', class: 'A'}
];
let classMap = new Map();
students.forEach(student => {
    if (!classMap.has(student.class)) {
        classMap.set(student.class, []);
    }
    classMap.get(student.class).push(student.name);
});
console.log(classMap);
// Map {
//     'A' => ['John', 'Bob'],
//     'B' => ['Jane']
// }

Set和Map的深入理解

Set和Map的内部实现原理

1. Set的实现：JavaScript引擎在实现Set时，通常会使用哈希表（Hash Table）来存储数据。哈希表是一种基于哈希函数的数据结构，它可以快速地插入、删除和查找元素。当向Set中添加一个元素时，引擎会计算该元素的哈希值，然后根据哈希值找到对应的存储位置。如果该位置为空，则直接插入元素；如果该位置已有元素，且与要插入的元素相同（通过Object.is()比较），则不插入；如果该位置已有不同元素，则可能会发生哈希冲突，此时通常会使用链地址法（Chaining）等方式来处理冲突。在遍历Set时，实际上是按照哈希表的存储顺序进行遍历（虽然在ES6规范中保证了遍历顺序与插入顺序一致，但具体实现可能因引擎而异）。
2. Map的实现：Map同样基于哈希表来实现键值对的存储。与Set不同的是，Map不仅要存储值，还要存储键以及它们之间的对应关系。当设置一个键值对时，引擎会计算键的哈希值，根据哈希值找到存储位置，然后将键值对存储在该位置。在获取值时，先计算键的哈希值，找到对应的位置，然后根据键来查找具体的值。如果发生哈希冲突，也会采用类似链地址法等方式处理。遍历Map时，也是按照哈希表的存储顺序（遵循插入顺序）进行遍历。

Set和Map与其他数据结构的关系

1. 与数组的关系：数组是JavaScript中最基本的数据结构之一，它以数字索引来存储元素。而Set和Map提供了不同的存储和访问方式。Set强调元素的唯一性，适合用于去重等场景；Map以键值对的形式存储数据，适合用于需要根据键快速查找值的场景。虽然数组也可以模拟Set和Map的部分功能，但Set和Map在实现这些功能时更加高效和方便。例如，数组去重可以通过遍历数组并使用indexOf()等方法来实现，但这种方法的时间复杂度较高，而使用Set则可以更简洁高效地完成去重。
2. 与对象的关系：普通对象也是以键值对的形式存储数据，但对象的键只能是字符串或符号类型，而Map的键可以是任意类型。在遍历方面，对象的属性遍历顺序在ES6之前是不确定的，而Map的遍历顺序与插入顺序一致。此外，对象没有直接获取属性数量的方法，而Map有size属性。在一些需要严格控制键的类型和遍历顺序的场景下，Map比普通对象更适用。

Set和Map在实际项目中的优化策略

1. 内存优化：在使用Set和Map时，如果存储的元素或键值对数量非常大，可能会占用较多的内存。为了优化内存使用，可以考虑在不再需要某些数据时，及时调用clear()方法清空Set或Map。例如，在一个缓存功能中，当缓存的有效期已过，就可以清空缓存对应的Map。

let cache = new Map();
// 缓存数据
cache.set('key1', 'value1');
// 缓存有效期已过
cache.clear();

2. 性能优化：由于Set和Map基于哈希表实现，在进行大量操作时，哈希冲突可能会影响性能。为了减少哈希冲突，可以尽量选择分布均匀的哈希函数（虽然JavaScript引擎会提供默认的哈希函数，但在某些特定场景下可能需要自定义）。另外，在遍历Set和Map时，尽量避免在遍历过程中进行添加或删除操作，因为这可能会导致哈希表结构的调整，影响性能。如果确实需要在遍历过程中修改Set或Map，可以考虑先将需要修改的操作记录下来，遍历结束后再统一进行修改。

let set = new Set([1, 2, 3]);
let toAdd = [4, 5];
let toDelete = [2];
// 遍历记录操作
set.forEach(value => {
    if (toDelete.includes(value)) {
        // 这里不直接删除，记录下来
    }
});
// 遍历结束后统一操作
toDelete.forEach(value => set.delete(value));
toAdd.forEach(value => set.add(value));

Set和Map的兼容性与Polyfill

1. 兼容性：Set和Map是ES6（ES2015）引入的新数据结构，虽然现代浏览器大多都已经支持，但在一些旧版本浏览器（如IE浏览器）中可能不支持。在开发项目时，如果需要兼容旧版本浏览器，就需要考虑使用Polyfill。
2. Polyfill实现：对于Set，可以通过模拟Set的功能来实现Polyfill。例如，使用对象来模拟Set的存储，通过自定义的方法来实现add、delete、has等功能。

// Set Polyfill
function PolyfillSet() {
    let data = {};
    this.add = function(value) {
        if (!this.has(value)) {
            data[value] = true;
            return this;
        }
        return this;
    };
    this.delete = function(value) {
        if (this.has(value)) {
            delete data[value];
            return true;
        }
        return false;
    };
    this.has = function(value) {
        return Object.prototype.hasOwnProperty.call(data, value);
    };
    this.size = function() {
        return Object.keys(data).length;
    };
    this.clear = function() {
        data = {};
    };
}

对于Map，也可以采用类似的方式，使用对象嵌套来模拟键值对的存储，并实现set、get、has等方法。

// Map Polyfill
function PolyfillMap() {
    let data = {};
    this.set = function(key, value) {
        if (!data[key]) {
            data[key] = {};
        }
        data[key].value = value;
        return this;
    };
    this.get = function(key) {
        return data[key]? data[key].value : undefined;
    };
    this.has = function(key) {
        return Object.prototype.hasOwnProperty.call(data, key);
    };
    this.delete = function(key) {
        if (this.has(key)) {
            delete data[key];
            return true;
        }
        return false;
    };
    this.size = function() {
        return Object.keys(data).length;
    };
    this.clear = function() {
        data = {};
    };
}

通过这些Polyfill，我们可以在不支持Set和Map的环境中使用类似的功能。但需要注意的是，Polyfill实现的功能可能无法完全等同于原生的Set和Map，在性能和一些细节上可能存在差异。

Set和Map在不同编程范式中的应用

1. 函数式编程：在函数式编程中，Set和Map非常有用。例如，在纯函数中，如果需要处理不重复的数据集合，Set是一个很好的选择。Set的不可变性（一旦创建，其成员不会轻易改变，除非通过明确的方法修改）符合函数式编程的理念。Map也常用于函数式编程中，例如在一个函数需要根据不同的输入返回不同的输出时，可以使用Map来存储这些输入输出对，使得函数更加简洁和可维护。

// 函数式编程中使用Set
function uniqueElements(arr) {
    return Array.from(new Set(arr));
}

// 函数式编程中使用Map
function lookupValue(map, key) {
    return map.get(key);
}

2. 面向对象编程：在面向对象编程中，Set和Map可以作为类的成员变量，用于存储对象的相关数据。例如，一个班级类可以使用Set来存储班级中的学生（确保学生不重复），使用Map来存储学生的成绩（以学生姓名为键，成绩为值）。

class Class {
    constructor() {
        this.students = new Set();
        this.scores = new Map();
    }
    addStudent(student) {
        this.students.add(student);
    }
    setScore(student, score) {
        this.scores.set(student, score);
    }
    getScore(student) {
        return this.scores.get(student);
    }
}

3. 事件驱动编程：在事件驱动编程中，Map可以用于存储事件和对应的处理函数。例如，在一个简单的DOM事件处理场景中，可以使用Map来存储不同元素的不同事件及其处理函数。

let eventMap = new Map();
function addEventHandler(element, eventType, handler) {
    if (!eventMap.has(element)) {
        eventMap.set(element, new Map());
    }
    eventMap.get(element).set(eventType, handler);
}
function triggerEvent(element, eventType) {
    if (eventMap.has(element)) {
        let typeMap = eventMap.get(element);
        if (typeMap.has(eventType)) {
            typeMap.get(eventType)();
        }
    }
}

通过对Set和Map数据结构的深入理解，我们可以在JavaScript编程中更加灵活和高效地处理数据，无论是在简单的脚本编写还是大型项目开发中，都能充分发挥它们的优势。同时，了解它们与其他数据结构的关系、内部实现原理以及在不同编程范式中的应用，有助于我们编写更优质、更高效的代码。