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

為什麼要有 Hash Table?

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

一、線性搜索（sequentail search）

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

二、使編號與索引相同

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

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

總結

Hash Table 兼顧快與節省空間。

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

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

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