寄物處的靈感
在寄物處，你不會把每個掛鉤都翻一遍來找外套——你的票號*就是*掛鉤號，你徑直走過去。雜湊表對資料做同樣的事：它根據你的鍵算出該看哪個槽位，完全無需掃描整個集合。
其核心是雜湊函式：一段小小的計算，把鍵（字串、數字，任何東西）變成一個陣列索引。同一個鍵輸入，每次都輸出同一個索引。
key "cat" --hash--> 37 --% 8--> bucket 5
key "dog" --hash--> 12 --% 8--> bucket 4
buckets (an array):
[ 0 | 1 | 2 | 3 |dog| cat| 6 | 7 ]
4 5
look up "cat": hash it -> go straight to bucket 5從鍵到桶：用 C++ 看
底層就是一個普通的"桶"陣列。要存一個鍵，先把它雜湊成一個數，再對陣列大小取模，落到一個合法索引上。一個迷你的字串雜湊器能把這個想法講實：
// A simple (illustrative) hash for a string:
size_t hashKey(const std::string& s, size_t nBuckets) {
size_t h = 0;
for (char c : s)
h = h * 31 + c; // mix each character in
return h % nBuckets; // fold into a valid index
}
// hashKey("cat", 8) always returns the same bucket.如果雜湊把鍵均勻地散布到各個桶裡，那麼存（put）和取（get）各自大約只碰一個桶——這就是著名的平均 O(1)。無論你有 100 個鍵還是 1 億個鍵，都一樣。
衝突：兩個鍵想要同一個槽
漏氣就在這裡。兩個不同的鍵可能雜湊到同一個桶——這叫衝突。桶的數量有限而鍵無限，衝突在所難免。最常見的解法是鏈結法（chaining）：每個桶裡掛一個小鏈結串列，存放所有落到這裡的條目。
bucket 5: cat -> hat -> bat -> / (all hashed to 5) bucket 4: dog -> / look up "hat": hash -> bucket 5, then walk the short list comparing keys until found.
實戰：std::unordered_map
你幾乎從不需要手寫雜湊表。C++ 提供 `std::unordered_map<Key, Value>`——一個插入、查找、刪除平均都是 O(1) 的雜湊表。（它的表親 `std::map` 會讓鍵保持有序，但是 O(log n)；當你只需要快速查找、不需要順序時，就選 `unordered_map`。）
#include <unordered_map>
#include <string>
std::unordered_map<std::string, int> age;
age["alice"] = 30; // put
age["bob"] = 25;
if (age.count("alice")) // membership test, ~O(1)
std::cout << age["alice"]; // get -> 30
age.erase("bob"); // remove, ~O(1)