ThinkChat2.0新版上线,更智能更精彩,支持会话、画图、阅读、搜索等,送10W Token,即刻开启你的AI之旅 广告
[TOC] > `Map`和`Set`是ES6标准新增的数据类型,请根据浏览器的支持情况决定是否要使用。 JavaScript的默认对象表示方式`{}`可以视为其他语言中的`Map`或`Dictionary`的数据结构,即一组键值对。 但是JavaScript的对象有个小问题,就是键必须是字符串。但实际上Number或者其他数据类型作为键也是非常合理的。 为了解决这个问题,最新的ES6规范引入了新的数据类型`Map`。要测试你的浏览器是否支持ES6规范,请执行以下代码,如果浏览器报ReferenceError错误,那么你需要换一个支持ES6的浏览器: ~~~ 'use strict'; var m = new Map(); var s = new Set(); alert('你的浏览器支持Map和Set!'); // 直接运行测试 ~~~ # Map `Map`是一组键值对的结构,具有极快的查找速度。 举个例子,假设要根据同学的名字查找对应的成绩,如果用`Array`实现,需要两个`Array`: ~~~ var names = ['Michael', 'Bob', 'Tracy']; var scores = [95, 75, 85]; ~~~ 给定一个名字,要查找对应的成绩,就先要在names中找到对应的位置,再从scores取出对应的成绩,Array越长,耗时越长。 如果用Map实现,只需要一个“名字”-“成绩”的对照表,直接根据名字查找成绩,无论这个表有多大,查找速度都不会变慢。用JavaScript写一个Map如下: ~~~ var m = new Map([['Michael', 95], ['Bob', 75], ['Tracy', 85]]); m.get('Michael'); // 95 ~~~ 初始化`Map`需要一个二维数组,或者直接初始化一个空`Map`。`Map`具有以下方法: ```javascript var m = new Map(); // 空Map m.set('Adam', 67); // 添加新的key-value m.set('Bob', 59); m.has('Adam'); // 是否存在key 'Adam': true m.get('Adam'); // 67 m.delete('Adam'); // 删除key 'Adam' m.get('Adam'); // undefined ``` 由于一个key只能对应一个value,所以,多次对一个key放入value,后面的值会把前面的值冲掉: ~~~ var m = new Map(); m.set('Adam', 67); m.set('Adam', 88); m.get('Adam'); // 88 ~~~ # Set `Set`和`Map`类似,也是一组key的集合,但不存储value。由于key不能重复,所以,在`Set`中,没有重复的key。 要创建一个`Set`,需要提供一个`Array`作为输入,或者直接创建一个空`Set`: ~~~ var s1 = new Set(); // 空Set var s2 = new Set([1, 2, 3]); // 含1, 2, 3 ~~~ 重复元素在`Set`中自动被过滤: ~~~ var s = new Set([1, 2, 3, 3, '3']); s; // Set {1, 2, 3, "3"} ~~~ 注意数字`3`和字符串`'3'`是不同的元素。 通过`add(key)`方法可以添加元素到`Set`中,可以重复添加,但不会有效果: ~~~ >>> s.add(4) >>> s {1, 2, 3, 4} >>> s.add(4) >>> s {1, 2, 3, 4} ~~~ 通过`delete(key)`方法可以删除元素: ~~~ var s = new Set([1, 2, 3]); s; // Set {1, 2, 3} s.delete(3); s; // Set {1, 2} ~~~ ## Set 有什么不同之处? 最根本的区别是数组是一个索引集合。 这意味着数组中的数据值按索引排序。 ~~~js const arr = [A, B, C, D]; console.log(arr.indexOf(A)); // Result: 0 console.log(arr.indexOf(C)); // Result: 2 ~~~ 相比之下,Set 是键控集合。它使用键对数据进行排序,而不是索引。Set 集合的元素可以按照插入顺序进行迭代,而且它不包含任何重复的数据。换句话说,所有 Set 集合中的每一元素都必须不同。 ## 它的主要好处是什么? 在直接比较中,Set 相对数组有一些优势,特别是它具有更快的运行时间: * **查找元素:** 在数组中使用`indexOf()`或`includes()`检查元素是否存在比较慢。 * **删除元素:** 在 Set 中,你可以通过值删除一个元素。等价于在数组中,基于索引的`splice()`功能。正如前面的观点,依赖索引查找比较慢。 * **插入元素:** 在 Set 中添加元素比在数组中通过`push()`、`unshift()`或其他同类操作要快。 * **去重:** Set 对象仅能存储不同的值。如果你想避免存储重复的值,这会比数组具有更大的优势。在数组中你需要一些额外的代码来做去重。 ## 时间复杂度对比 数组中用于搜索元素的方法具有 O(N) 的线性时间复杂度。换句话说,运行时间随着数据大小而增长。相对而言,Set 搜索、删除和插入元素的方法时间复杂度都为 O(1),这意味着数据的大小几乎不影响这些方法的运行时间。 ## Set 到底快了多少? 虽然运行时间可能会有很大差异,具体取决于所使用的系统、所提供数据的大小以及其他变量。但我希望我的测试结果能够让你真实地了解Set 的速度。我将分享三个简单的测试和我得到的结果。 ### 测试准备 在进行测试前,我们先创建一个数组和一个 Set 集合,它们都包含一百万个元素。为了简单,我将使用 0 到 999999 。 ~~~js let arr = [], set = new Set(), n = 1000000; for (let i = 0; i < n; i++) { arr.push(i); set.add(i); } ~~~ ### 测试 1: 搜索元素 首先,我们搜索一个已知存在的数字`123123`。 ~~~js console.time('Array'); result = checkArr(arr, 123123); console.timeEnd('Array'); console.time('Set'); result = checkSet(set, 123123); console.timeEnd('Set'); ~~~ * Array: 0.173ms,Set: 0.023ms * Set 比数组快了 7.54 倍。 ### 测试 2: 添加元素 现在我们为每个集合添加一个元素 ~~~js console.time('Array'); arr.push(n); console.timeEnd('Array'); console.time('Set'); set.add(n); console.timeEnd('Set'); ~~~ * Array: 0.018ms,Set: 0.003ms * Set 比数组快了 6.73 倍。 ### 测试 3: 删除元素 最后,让我们从每个集合移除一个元素。因为没有内置的数组方法可以使用,所以我们创建一个 helper 函数来保持整洁: ~~~js const deleteFromArr = (arr, item) => { let index = arr.indexOf(item); return index !== -1 && arr.splice(index, 1); }; ~~~ 这儿是测试代码: ~~~js console.time('Array'); deleteFromArr(arr, n); console.timeEnd('Array'); console.time('Set'); set.delete(n); console.timeEnd('Set'); ~~~ * Array: 1.122ms,Set: 0.015ms * 在这个测试中,Set 比数组快了 74.13 倍。 总之,使用 Set 来代替数组我们可以看到显著的运行时间提升。现在让我们看一些集合可能有用的实际例子。 ## 场景 1: 数组去重 如果你想快速的从数组中移除重复的值,你可以将它转化成 Set。这是目前最简洁的筛选不同值的方法: ~~~js const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C']; // 如果你想将数组转化成 Set let uniqueCollection = new Set(duplicateCollection); console.log(uniqueCollection) // 结果: Set(4) {"A", "B", "C", "D"} // 如果你仍然想保持使用数组存储数据 let uniqueCollection = [...new Set(duplicateCollection)]; console.log(uniqueCollection) // 结果: ["A", "B", "C", "D"] ~~~ ## 场景 2: Google 面试题 ### 问题 给定一个无序整数数组和一个值`sum`,如果存在其中两个元素的之和等于`sum`,返回`true`。否则,返回`false`。 所以,如果我们给定一个数组`[3, 5, 1, 4]`和一个值`9`,我们的函数需要返回`true`,因为`4 + 5 = 9`。 ### 解决方案 解决这个问题一个好的方法是迭代整个数组,并将迭代到的元素的匹配值的添加到 Set 集合。 让我们将这种思路用到上面的例子中。当我们遇到`3`时,将`6`添加到 Set 集合中,因为我们知道我们要找的是和为`9`的另外一个元素。然后,每次我们迭代到数组中的一个新的元素,我们检查和它匹配的值是否在 Set 中。当我们迭代到`5`的时候,我们将将添加`4`到我们的 Set 集合中。接着,我们最终迭代到`4`,我们将发现它的匹配值已经在我们的 Set 中,因此我们返回`true`。 代码如下: ~~~js const findSum = (arr, val) => { let searchValues = new Set(); searchValues.add(val - arr[0]); for (let i = 1, length = arr.length; i < length; i++) { let searchVal = val - arr[i]; if (searchValues.has(arr[i])) { return true; } else { searchValues.add(searchVal); } }; return false; }; ~~~ 这儿是更简洁的版本: ~~~js const findSum = (arr, sum) => arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set)); ~~~ 因为`Set.prototype.has()`的时间复杂度仅为 O(1) ,所以使用`Set`存储匹配值而不是数组,帮助我们整体解决方案达到线性运行时间 O(N)。 如果我们依赖于`Array.prototype.indexOf()`或`Array.prototype.includes()`,这两个方法的时间复杂度都为 O(N),那么整体运行时间的时间复杂度为 O(N²)。慢太多了! # **Map及Set的遍历**  Array可以采用下标进行循环遍历,Map和Set就无法使用下标。为了统一集合类型,ES6标准引入了iterable类型,Array、Map、Set都属于iterable类型。 ## for ... of遍历 > 具有`iterable`类型的集合可以通过新的`for ... of`循环来遍历 ~~~javascript var a = ['A', 'B', 'C']; var s = new Set(['A', 'B', 'C']); var m = new Map([[1, 'x'], [2, 'y'], [3, 'z']]); for (var x of a) { // 遍历Array alert(x); } for (var x of s) { // 遍历Set alert(x); } for (var x of m) { // 遍历Map alert(x[0] + '=' + x[1]); } ~~~ ## forEach forEach是iterable内置的方法,它接收一个函数,每次迭代就自动回调该函数。 ~~~javascript var a = ['A', 'B', 'C']; a.forEach(function (element, index, array) { // element: 指向当前元素的值 // index: 指向当前索引 // array: 指向Array对象本身 alert(element); }); ~~~ `Set`与`Array`类似,但`Set`没有索引,因此回调函数的前两个参数都是元素本身: ~~~javascript var s = new Set(['A', 'B', 'C']); s.forEach(function (element, sameElement, set) { alert(element); }); ~~~  `Map`的回调函数参数依次为`value`、`key`和`map`本身: ~~~javascript var m = new Map([[1, 'x'], [2, 'y'], [3, 'z']]); m.forEach(function (value, key, map) { alert(value); }); ~~~