Hash Table（ㄧ）為什麼要有雜湊表？

為什麼要有 Hash Table?

先想一下，若有 10 幾筆資料，記錄了棒球員的編號、姓名與年薪。
如果需要搜尋編號 100 的球員年薪，要如何做搜尋？

一、線性搜索（sequentail search）：

最簡單且最直接的就是把資料存進陣列裡，從索引 1 開始逐一搜尋，直到找到編號 100 的球員。
這樣的做法可說是暴力，會花費的時間複雜度為 O(n)，但佔用較少的記憶體空間。

索引	姓名	編號	年薪（萬美金）
1	Ricky	38	50
2	Rock	4	90
3	Johnson	222	92
4	Jack	1	22
5	Rebacca	5	44
6	Tom	99	65
7	Nick	100	43
8	Jason	555	93
9	Peter	666	92
10	Lulu	49	67
11	Vincent	77	101
12	Peggy	333	42
13	George	664	26

二、使編號與索引相同：

將資料整理成 Array 的格式，將編號與索引對在一起，如編號 99 就放在 索引 99 的位置。這個方法可以提高搜尋的速度，**時間複雜度：O(1)**，直接透過 index 就可以取得資料，如: Arr[100] 可得到編號 100 的球員資料。

但這樣，各個球員索引中間的空間也都被佔用了，會花費相當大的記憶體空間，如下方表格，雖然球員資料只有 13 筆，但卻佔用了 666 個空間。

索引	姓名	編號	年薪（萬美金）
1	Jack	1	22
…..	……	……	..
4	Rock	4	90
5	Rebacca	5	44
…..	……	……	..
38	Ricky	38	50
…..	……	……	..
49	Lulu	49	67
…..	……	……	..
77	Vincent	77	101
…..	……	……	..
99	Tom	99	65
100	Nick	100	43
…..	……	……	..
222	Johnson	222	92
…..	……	……	..
333	Peggy	333	42
…..	……	……	..
555	Jason	555	93
…..	……	……	..
664	George	664	26
…..	……	……	..
666	Peter	666	92

總結

Hash Table 兼顧快與節省空間。

上述的兩個方法，都會導致不如意的情況：

1. 速度快，但記憶體佔用多
2. 記憶體佔用少，但速度快

Hash Table 就是用來解決這個兩難的情況，他可以同時節省空間的佔用，也可以節省時間。