先講一下何謂雜湊（Hash）。這個是 Hash Brown，中文叫做薯餅：

可是不是我們要的主題。我們要的是 雜湊（Hash）！先來看維基百科的定義：

簡單來說，就是讓一個很難表示的東西透過某個函數變成一個比較好表示的東西！假設想要紀錄一些人的生日，那一個生日可能是像 2002/11/05 的格式，不好處理，那我可能會壓縮成一個字串 "20021105" 表示，或者是只留後面的數字 021105。當然，這樣代表 1902/11/05 也會變成 021105，但是我們可能比較不在乎這種情況發生。

顯然，如果 Hash 出來的東西不一樣，則兩個東西一定不一樣；但是如果 Hash 出來的東西一樣，不代表是一樣的。雖然如此，但是如果好好選 Hash Function，就可以避免 Hash 值一樣時發生的碰撞（Collision）了。

現在想像有一個資料結構要支援兩種操作：加入一個在 $[0, 10^9)$ 之間的數字，跟詢問數字 $x$ 是否存在。除了用前面的 set 來達成之外，還有另一種方法。對於每個數字 $x$，我們用某種雜湊函數算出 $h(x)$，使得雜湊之後的值在 $[0, 10^6)$ 之間，然後維護 $10^6$ 個陣列 （像是 vector），把 $x$ 加進編號為 $h(x)$ 的陣列。遇到詢問時，直接看 $x$ 是否出現在 $h(x)$ 的陣列中。如果雜湊函數是足夠「亂」的，那加入 $n$ 個數字後，平均每個陣列就有 $n / 10^6$ 個數字，那麼查詢速度就可以很快。

接下來講的 unordered_set 和 unordered_map，就是用上述的概念實作的資料結構。

STL 的 hash table 叫做 unordered_set，它與 set 一樣，都支援了插入、查詢、刪除的功能，唯一有差別的是因為它的實作原理是 hash，對於每次操作的複雜度都可以當成是 $O(1)$，但是這樣一來就會沒有二元搜尋樹的良好性質，所以不能按照大小順序遍歷輸出。

unordered_set<int> use; // 宣告一個元素型別為 int 的集合
use.reserve(N); //reserve N 個記憶體可以加速程式
use.insert(1); // 插入元素 1
use.insert(2);
use.insert(5);
cout << use.count(1) << endl; // 查找元素，true
cout << use.count(3) << endl; // false
use.erase(1); // 刪除元素，若雜湊表內不含此元素則回傳 false
// 不支援 upper_bound, lower_bound, find 等二分查找功能
for (auto &val: use)
    cout << val << ' ';
// 可以遍歷，但不會照順序

unordered_map 的用法與一般的 map 也差不多，實作原理也是個雜湊表。大部分的成員函數以及運算子都與 map 一樣，複雜度是 $O(1)$。

unordered_map<string,int> umapp;
// 宣告一個由 string 雜湊到 int 的 unordered_map
umapp.insert({"apple", 1});
umapp["book"] = 2;
umapp["apple"] = 3;
cout << umapp.count("apple") << endl; // true
cout << umapp.count("my girlfriend") << endl; // false

for (auto &val: umapp)
    cout << val.first << ' ' << val.second << endl;
// 支援遍歷，一樣是無序的

注意，雜湊函式也可以自己寫！這是 unordered_map 的定義範例（假設是把 string 透過雜湊函數變成 unsigned long）：

unordered_map<std::string, //key
    unsigned long, //value
    std::function<unsigned long(std::string)>, //雜湊函數
    std::function<bool(std::string, std::string)> //比較兩元素是否相等的函數
    > mymap(n, hashing_func, key_equal_fn<std::string>);
    //mymap初始大小，雜湊函數，key的比較函數`

unordered_set 和 unordered_map 的常數通常較大，有一些題目需要一些優化和巧思才能在時限內通過！