前言

這篇文章要來了解 ES6 新增的兩種資料結構: Set & Map。

Set(集合)

語法

new Set([iterable]);

Set 可以傳入一個可迭代的值當作參數，並且會回傳一個 Set 物件。

特性

1. Set 內儲存的元素內容沒有型別限制
2. 元素不會有重複值，傳入的元素也不會型轉，所以可能會看到 '1' 和 1 都在 Set 內

應用

關於 Set 的相關函式在 MDN 的文件就說明的相當清楚，所以就不多做講解。

1. 移除重複的值

Set 很好用的一個地方就是它可以移除傳入物件中重複的值，所以若要移除陣列內重複的值可以靠它加上 Array.from 或是展開運算子做處理:

透過這個特性，在計算多個值中出現了幾種類的值時特別好用。

例如: 三角形三個邊，符合兩邊和大於第三邊時，若傳入的三個邊透過 Set 處理後只剩一個就是正三角形，若剩兩個就是等邊三角形。

2. 集合相關操作

此外，Set 也可以延伸去做一些集合的操作。

const setA = new Set([1, 2, 3, 4]);
const setB = new Set([2, 3]);
const setC = new Set([3, 4, 5, 6]);

// 判斷超集 & 子集
Set.prototype.isSuperset = function(subset) {
  for (const ele of subset) {
    if (!this.has(ele)) return false;
  }
  return true;
}

console.log(setA.isSuperset(setB)); // true

// 聯集，也就是兩個 Set 所有的元素組成的集合
Set.prototype.union = function(setParam) {
  const union = new Set(this); // 避免改到 setA
  for (const ele of setParam) {
    union.add(ele);
  }
  return union;
}

console.log(setA.union(setC)); // [1, 2, 3, 4, 5, 6]

// 交集，回傳兩個 Set 共同元素組成的集合
Set.prototype.intersection = function(setParam) {
  const intersection = new Set();
  for (const ele of setParam) {
    if (this.has(ele)) intersection.add(ele);
  }
  return intersection;
}

console.log(setA.intersection(setC)); // [3, 4]

// 差集，回傳只包含 SetA 但不存在於 setParam 的元素所組成的集合
Set.prototype.difference = function(setParam) {
  const diff = new Set(this);
   for (const ele of setParam) {
    diff.delete(ele);
  }
  return diff;
}

console.log(setA.difference(setC)); // [1, 2]

交集 intersection 的部分有在 Leetcode 出現過: 349. Intersection of Two Arrays

3. 補充: Set 也能做解構賦值

let [one, two, three] = new Set([1, 2, 3]);

Map

Map 是一種資料結構，存入的每組資料都有對應的 key 值(索引值)與 value 值(資料值)，而且 key 可以是各種資料型態的值(字串/數字/物件...等)，這是和 Object 很重要的不同之處。

這種 Key-Value 對應的關係和 Hash Table 非常相似，兩種資料結構在操作資料的時間複雜度也相同。

Hash Table(雜湊表)會呼叫一個雜湊函數將 key & value 值建立一對映射關係，相同的 key 會產生相同的 hash 值，進而直接查詢資料在記憶體儲存位置，加快查找資料的速度。

Map 時間複雜度

插入、刪除、搜尋、取得在平均狀況下都是 O(1)，最差情況則是都是 O(n)

Map 和陣列互轉換

Map 轉為陣列

我們可以將二維陣列當作 Map 的參數產生 Map 物件，並且可加上 Array.from 或是展開運算子轉回二維陣列:

const arrMap = new Map([["key1", "value1"], ["key2", "value2"]]);

console.log(arrMap);
console.log(Array.from(arrMap));
console.log([...arrMap]);

陣列轉為 Map

const arr = [
  {key: 'name', value: 'bobby hadz'},
  {key: 'country', value: 'Chile'},
];

const map1 = new Map(
  arr.map(obj => {
    return [obj.key, obj.value];
  }),
);

// ️Map(2) { 'name' => 'bobby hadz', 'country' => 'Chile' }
console.log(map1);

Map 和物件互轉換

Map 轉為 Object:

function mapToObj(map) {
  let obj = Object.create(null);
  for (let [key, value] of map) {
    obj[key] = value;
  }
  return obj;
}
const map = new Map().set('name', 'Harry').set('age', 24);
mapToObj(map)  // {name: "Harry", age: 24}

Object 轉為 Map:

function objToMap(obj) {
  let map = new Map();
  for (let key of Object.keys(obj)) {
    map.set(key, obj[key]);
  }
  return map;
}

objToMap({'name': 'An', 'des': 'JS'}); // Map {"name" => "An", "des" => "JS"}

應用

Object & Map

以下做個 Object 和 Map 的比較，透過這樣的比較可以知道什麼時候更適合使用哪個資料結構。

應用於程式解題

相信很多人都有看過這個 leetcode 的第一道題目 Two Sum，這題就可以用 Map 解決，而且時間複雜度和暴力解相比更好，只有 O(n)。

function twoSum(numbers, target) {
  const map = new Map();
  for (let i = 0; i < numbers.length; i++) {
    if (map.has(numbers[i])) {
      return [map.get(numbers[i]), i];
    }
    map.set(target - numbers[i], i);
  }
}

這段程式碼的邏輯是假如目前有這樣的參數: twoSum([7, 2, 5, 4], 9)

1. 那在進行 for 迴圈時，首先碰到的值是 7，會去查找 map 裡面有沒有 7，沒有就將要和 7 相加後等於目標值 9 的數字 2 以及當前的索引值存起來，所以 map 變成以下內容

map = { 2: 0 }

2: 接下來迴圈要尋找的值
0: 迴圈遍歷到 7 時的索引

2. 接著 for 迴圈跑到 2，檢查看看 map 內有沒有和 2 一模一樣的值，這樣和之前碰過的數字，也就是 7 相加就等於目標值了
3. 所以就可以回傳一開始 7 的索引值 0(map = { 2: 0 }) 和 2 的索引值 1

參考資料 & 推薦閱讀

MDN Set

MDN Map

【Day9】[資料結構]-雜湊表Hash Table