哈希表：近乎瞬时的查找

存衣处的灵感

在存衣处，你不会把每个挂钩都翻一遍来找外套——你的票号*就是*挂钩号，你径直走过去。哈希表对数据做同样的事：它根据你的键算出该看哪个槽位，完全无需扫描整个集合。

其核心是哈希函数：一段小小的计算，把键（字符串、数字，任何东西）变成一个数组下标。同一个键输入，每次都输出同一个下标。

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.

把每个字符都揉进去，再 % nBuckets 得到一个范围内的下标。

如果哈希把键均匀地散布到各个桶里，那么存（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)

std::unordered_map：按键插入、查找、删除，平均常数时间。