[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(N2)。慢太多了！ # **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); }); ~~~