前面幾篇，我們其實一直在討論同一類操作需求：

下一個要拿哪一筆資料？

• Queue 的答案是最早進來的那一筆。
• Priority Queue 的答案是現在最重要的那一筆。
• Stack 的答案則是最後放進去的那一筆。

這些資料結構保存的可能都是一群資料。
差別在於：

下一次操作時，應該先拿哪一筆？

但生活中還有另一類完全不同的問題，有時候我們不是不知道下一個要拿誰。
反而是：

我已經知道自己要找誰了，能不能直接找到他？

如果我要找的是某一個人呢？

想像你的手機通訊錄裡有五個人：

Alice
Bob
Carol
David
Eric

今天你想找 David。
最直覺的方法，可以從第一個開始檢查：

Alice → 不是
Bob   → 不是
Carol → 不是
David → 找到了

如果只有五個人，這當然沒什麼問題。
但如果今天不是五個人，而是：

100 人
1,000 人
10,000 人
1,000,000 人

而且你每次查詢都得：

第一筆
↓
第二筆
↓
第三筆
↓
第四筆
↓
...
↓
直到找到目標

事情就開始麻煩了，假設我們有一群使用者：

const users = [
  { id: 10001, name: "Alice" },
  { id: 10002, name: "Bob" },
  { id: 10003, name: "Carol" },
  { id: 12345, name: "David" }
];

如果我們要找：

userId = 12345

最直接的方法就是：

const user = users.find(
  user => user.id === 12345
);

程式本身沒有問題。
但它描述的搜尋方式其實是：

10001？
不是

10002？
不是

10003？
不是

12345？
找到了

還是一筆一筆檢查。

資料越多，要檢查的資料也可能越多

假設目標剛好在最後面。
當資料只有 10 筆時，我們最多可能檢查 10 筆。
有 1,000 筆時：1,000 筆；
有 1,000,000 筆時：1,000,000 筆；

如果把 Day 1 提過的 Big-O 直覺拿回來看：

當資料數量增加時，搜尋成本也可能跟著資料量一起增加。

這類逐筆尋找的方式，通常會被描述成：

O(n)

這裡的 n 就是資料數量。

問題是我們其實已經知道 userId = 12345。
既然都知道要找誰了，有沒有辦法不要從第一個人開始問？

如果可以用「編號」直接找資料呢？

現實生活中其實到處都是這種設計。
例如你去飯店櫃檯說：
我要找 207 號房。

櫃檯人員通常不需要：

先去 101 看看
再去 102 看看
再去 103 看看
...

因為 207 本身就是找到某個房間的識別方式。
又例如學生資料：

學號 → 學生

商品系統：

商品編號 → 商品

會員系統：

userId → User

DNS 也有類似的味道：

domain → 對應資料

它們共同存在一種關係：

key → value

Key → Value

假設我們把使用者改成這樣描述：

10001 → Alice
10002 → Bob
10003 → Carol
12345 → David

現在要找 12345。

問題就不再是：

David 在第幾筆？

而變成：

12345 對應的資料是什麼？

原本我們在乎的是資料的位置：

第 1 筆
第 2 筆
第 3 筆
第 4 筆

現在我們在乎的是資料的 identity：

userId = 12345

也就是：

不是問「資料放在哪裡」，而是問「這個 identity 對應哪一筆資料」。

這種操作有時可以稱作 identity lookup。

Hash Table

為了支援這種 key → value 的查找方式，其中一種非常常見的資料結構就是 Hash Table。
它背後的想法是：

不要每次都從頭搜尋，而是根據 key 推算資料應該去哪裡找。

例如：

12345
↓
某種計算
↓
位置 7
↓
找到 David

負責把 key 轉換成某個位置資訊的計算，通常稱為 hash function。
可以先把它想像成：

key
↓
hash function
↓
應該去哪裡找

我們這篇不需要知道 hash function 到底怎麼設計。
重要的是理解它帶來的操作差異。

從「一筆一筆找」變成「根據 key 找」

如果使用 Array：

Alice
Bob
Carol
David
Eric

我要找 David，可能需要：

Alice？
Bob？
Carol？
David？

但 Hash Table 想做的事情比較接近：

David 的 key
↓
算出應該去哪裡
↓
直接去那裡找

所以在一般情況下，Hash Table 的 lookup 通常會被描述成 average O(1)，也就是：

平均而言，查找成本不需要隨著資料數量等比例增加。

這裡的 O(1) 不代表：

永遠只執行一個 CPU instruction

也不是：

不管任何情況都一定一樣快

它真正想表達的是：

資料量增加時，平均查找成本不會像逐筆搜尋那樣跟著 n 一起成長。

這也是為什麼 Hash Table 是非常常見的資料結構。
因為軟體裡大量存在「我已經知道 identity，現在只想拿到對應資料」這種需求。

Hash Map 又是什麼？

你也很常看到另一個名字 Hash Map。
在日常開發語境裡，Hash Map 通常指的是一種 key → value 形式的 Map，而且底層使用 hashing 技術實作，所以你可以先建立這個直覺：

• Hash Table：一種利用 hash 組織與查找資料的資料結構
• Hash Map：使用這種機制來建立 key → value mapping

不同語言、library 和教材對名稱的使用方式可能稍有不同。
這篇真正需要記住的不是這些名詞，而是它想解決的問題：

當我已經知道 key 時，我希望能快速找到對應的 value。

JavaScript 裡的 Map

在 JavaScript 裡，我們可以使用 Map 表達非常接近的操作語意：

const users = new Map();

users.set(12345, {
  name: "Alice"
});

現在資料的關係變成：

12345
  ↓
{
  name: "Alice"
}

要找這個使用者時：

const user = users.get(12345);

不需要自己寫：

users.find(...)

也不用表達從第一筆開始找，我們直接告訴資料結構：我的 key 是 12345。
然後問：它對應的 value 是什麼？

Array 和 Map 描述的問題不同

例如 Array：

const users = [
  { id: 10001, name: "Alice" },
  { id: 10002, name: "Bob" },
  { id: 12345, name: "Carol" }
];

它主要描述的是一組有順序的資料。
所以我們很自然會操作：

users[0];
users[1];
users[2];

也就是在講第幾個？
但 Map：

const users = new Map([
  [10001, { name: "Alice" }],
  [10002, { name: "Bob" }],
  [12345, { name: "Carol" }]
]);

我們會操作：

users.get(12345);

講的是這個 key 對應誰？
兩者保存的資料甚至可以完全相同。

真正不同的是：

我們準備怎麼找到它。

但為什麼不能保證永遠直接找到？

前面把 hashing 簡化成：

key
↓
hash
↓
位置

很方便也很完美，但這裡存在一個數學上無法完全避免的問題。
假設我們只有幾個可用位置：

0
1
2
3
4

但可能出現的 key 卻非常多：

Alice
Bob
Carol
David
Eric
Frank
Grace
...

我們必須把大量可能的 key：非常大的輸入空間，映射到有限的位置空間。
那麼遲早可能出現：

key A
   ↓
位置 3

key B
   ↓
位置 3

也就是：

不同的 key 得到了相同的位置。

這種情況稱為 collision。

Collision 不是 bug

第一次看到 collision 時，很容易直覺認為：

那是不是 hash function 寫壞了？

不一定，因為只要：

可能的 key 數量 > 可以映射的位置數量

不同 key 映射到相同位置這件事，在理論上就無法完全避免。
所以真正的問題從來不是：

如何保證 collision 永遠不發生？

而是：

發生 collision 之後，要怎麼正確處理？

實際的 Hash Table 會有不同策略處理這件事情。
例如有些設計會讓同一個位置繼續保存多個候選資料，有些則會尋找其他可用位置。
但那些就是 Hash Table implementation 的細節了。
這篇暫時不用深入。
我們現在只需要知道：

hash 不是 key → 絕對唯一的位置

因此 collision 是 Hash Table 設計必須考慮的一部分。

Hash Table 改變的是「怎麼找到資料」

回頭看前面的幾種資料結構。

• Queue 關心的是：誰最早進來？
• Priority Queue 關心的是：誰現在最重要？
• Stack 關心的是：誰最後進來？

而 Hash Table 對應的是完全不同的問題：

我已經知道 key 了，它對應的資料在哪裡？

所以可以把前幾天的概念整理成：

Queue
→ 最早加入的先處理

Priority Queue
→ 最重要的先處理

Stack
→ 最晚加入的先處理

Hash Table
→ 根據 key 找到對應資料

前三者主要改變的是：

下一個拿誰？

Hash Table 改變的則是：

怎麼找到我要的那一筆？

這也是我們在理解資料結構時很重要的一個轉折。

資料結構不只是不同形狀的容器

我們很容易把：

Array
Queue
Stack
Hash Table

想成四種不同形狀的盒子。
但如果只是這樣理解，很容易開始背：

Stack 是 LIFO
Queue 是 FIFO
Hash Table 查找很快

然後變成一串彼此無關的名詞。
其實真正值得記住的是它們各自對應什麼問題。

Queue
→ 我希望按照抵達順序處理

Priority Queue
→ 我希望按照重要程度處理

Stack
→ 我希望從最後發生的事情往回處理

Hash Table
→ 我已經知道 identity，希望快速找到對應資料

因此選擇資料結構以前，該問的不是：

哪個資料結構比較厲害？

得看你的需求去想：

我的問題需要什麼操作？

下一個問題：如果資料之間有上下關係呢？

目前看到的資料結構，大多還可以想像成一群資料。
然後我們決定誰先處理？
或者怎麼找到其中一筆？
但現實世界還有很多資料不是單純的一群東西。
例如公司的組織：

CEO
├─ 技術部
│  ├─ 前端
│  └─ 後端
└─ 行銷部

或者電腦裡的資料夾：

Documents
├─ Work
│  ├─ report.pdf
│  └─ budget.xlsx
└─ Personal
   └─ photo.jpg

這時候資料之間開始出現：

上層
↓
下層
↓
更下層

我們面對的問題就不只是誰先？或怎麼找？
而是：

資料彼此之間，到底存在什麼關係？

當資料本身存在明確的上下層關係時，我們就會遇到下一種非常重要的資料結構：

Tree