Hash Map & Set

資料結構與演算法學習 01

2026-05-10

資料結構與演算法學習 01：Hash Map & Set

1. Map 與 Set 解決什麼問題？

Map：用 key 快速存取資料，適合查找、索引、分組與快取。
Set：儲存唯一值，適合去重、判斷是否存在與集合運算。

兩者常用來降低陣列反覆查找的成本。當資料量變大或查找次數變多時，先建立 Map 或 Set，通常能把接近 O(n²) 的流程降到 O(n)。

2. Map / Set / Object / Array 怎麼選？

`Map`

儲存形式：Key-Value 鍵值對
特性：Key 可以是任何型別，Key 唯一，Value 可重複
常見用途：快速查找、資料索引、分組、快取

`Set`

儲存形式：Value 集合
特性：只存 value，沒有 key-value 對，Value 唯一
常見用途：去重、判斷是否存在、集合運算

`Object`

儲存形式：Key-Value 鍵值對
特性：Key 通常是 string 或 symbol，數字 key 會轉成字串
常見用途：描述結構化資料、JSON 資料、設定物件

`Array`

儲存形式：有順序的元素列表
特性：用 index 存取，value 可以是任何型別，不保證唯一
常見用途：有序列表、排序、迭代、渲染清單

快速判斷：

需要 key-value 快速查找：用 Map
需要唯一值或去重：用 Set
需要描述固定結構資料：用 Object
需要保留順序並逐筆處理：用 Array

3. 常見操作與平均時間複雜度

操作	Map	Set	Object	Array
插入	O(1)	O(1)	O(1)	O(1)
查找	O(1)	O(1)	O(1)	O(n)
刪除	O(1)	O(1)	O(1)	O(n)
遍歷	O(n)	O(n)	O(n)	O(n)
去重	N/A	O(n)	O(n)	O(n²)

表格中的 O(1) 指平均情況。Array 插入若是 push 通常是 O(1)，插入中間或開頭則是 O(n)。

4. 用 Map 避免巢狀 find

如果在 users.map() 裡反覆對 groups.find()，時間複雜度會是 O(n * m)。

const users = [
  { id: 1, name: 'Alice', groupId: 1 },
  { id: 2, name: 'Bob', groupId: 2 },
  { id: 3, name: 'Charlie', groupId: 1 },
]

const groups = [
  { id: 1, name: 'Group A' },
  { id: 2, name: 'Group B' },
]

const result = users.map((user) => {
  const group = groups.find((g) => g.id === user.groupId)
  return { ...user, groupName: group ? group.name : null }
})

先把 groups 轉成 Map，每次查找就能降為平均 O(1)。

const groupMap = new Map(groups.map((group) => [group.id, group.name]))

const result = users.map((user) => {
  const groupName = groupMap.get(user.groupId) ?? null
  return { ...user, groupName }
})

整體複雜度從 O(n * m) 降為 O(n + m)。

5. 用 Set 處理去重與 selected state

Set 會自動保留唯一值，很適合處理基本型別去重。

const items = [1, 2, 3, 2, 4, 1]
const uniqueItems = [...new Set(items)]

console.log(uniqueItems) // [1, 2, 3, 4]

也可以用來管理選取狀態。

const selectedIds = new Set()

function toggleSelect(id) {
  if (selectedIds.has(id)) {
    selectedIds.delete(id)
  } else {
    selectedIds.add(id)
  }
}

toggleSelect(1)
toggleSelect(2)
toggleSelect(1)

console.log(selectedIds) // Set { 2 }

6. TypeScript Utility：indexBy、groupBy、uniqueBy

indexBy

把陣列轉成以 key 查找的 Map，常用於 API response normalization。

function indexBy<T, K extends string | number | symbol>(
  items: T[],
  getKey: (item: T) => K,
): Map<K, T> {
  const result = new Map<K, T>()

  for (const item of items) {
    result.set(getKey(item), item)
  }

  return result
}

const users = [
  { id: 1, name: 'Alice', groupId: 1 },
  { id: 2, name: 'Bob', groupId: 2 },
  { id: 3, name: 'Charlie', groupId: 1 },
]

const userMap = indexBy(users, (user) => user.id)

console.log(userMap.get(2)) // { id: 2, name: 'Bob', groupId: 2 }

groupBy

依 key 分組，適合把列表整理成分類資料。

function groupBy<T, K extends string | number | symbol>(
  items: T[],
  getKey: (item: T) => K,
): Map<K, T[]> {
  const result = new Map<K, T[]>()

  for (const item of items) {
    const key = getKey(item)
    const group = result.get(key) ?? []

    group.push(item)
    result.set(key, group)
  }

  return result
}

uniqueBy

依指定 key 去重，適合處理 object array。

function uniqueBy<T, K extends string | number | symbol>(items: T[], getKey: (item: T) => K): T[] {
  const seen = new Set<K>()
  const result: T[] = []

  for (const item of items) {
    const key = getKey(item)

    if (seen.has(key)) continue

    seen.add(key)
    result.push(item)
  }

  return result
}

7. 常見錯誤與注意事項

7-1. 在迴圈中反覆 find

避免在 map、forEach、for...of 中反覆對另一個陣列 find。如果是用某個欄位查找資料，通常可以先建立 Map。

7-2. 用 Set 對 object array 去重

Set 會用物件參考判斷唯一性。兩個內容相同的物件，只要參考不同，就會被視為不同值。

const items = [
  { id: 1, name: 'Alice' },
  { id: 2, name: 'Bob' },
  { id: 1, name: 'Alice' },
]

const uniqueItems = [...new Set(items)]

console.log(uniqueItems) // 仍然有 3 筆

物件陣列應改用穩定 key 去重。

const uniqueItems = uniqueBy(items, (item) => item.id)

7-3. 用物件當 Map key

Map 也會用物件參考判斷 key 是否相同。

const map = new Map()
const key1 = { id: 1 }
const key2 = { id: 1 }

map.set(key1, 'value1')

console.log(map.get(key1)) // 'value1'
console.log(map.get(key2)) // undefined

如果要用物件內容查找，通常應改用穩定的 primitive key，例如 id。

7-4. 混淆 Map 和 Record

如果 key 是固定集合，用 Record 通常更清楚；如果 key 是動態產生，或需要頻繁新增、刪除、查找，用 Map 較適合。

type User = { id: number; name: string }
type UserRecord = Record<number, User>

const userRecord: UserRecord = {
  1: { id: 1, name: 'Alice' },
  2: { id: 2, name: 'Bob' },
}

console.log(userRecord[1]) // { id: 1, name: 'Alice' }

8. 總結

Map 和 Set 的重點不是取代 Array 或 Object，而是在需要快速查找、去重、分組或快取時，提供更適合的資料結構。

實務上常見的做法是保留 Array 作為原始順序資料，再依需求建立輔助結構：

用 Map 把列表轉成索引，避免在迴圈中反覆 find
用 Set 記錄已看過的值、已選取的 id，或快速判斷資料是否存在
用 groupBy 把扁平列表整理成依分類查找的資料
用 uniqueBy 對 object array 做穩定去重

如果資料量很小、只查找一次，直接使用 Array 通常就足夠；當查找會重複發生、資料量變大，或邏輯開始出現多層迴圈時，就可以考慮引入 Map 或 Set。好的資料結構選擇，能讓程式碼更直觀，也能降低不必要的時間複雜度。