[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); }); ~~~