数组与线性结构
哈希表
哈希表存放键值对，让你能凭键几乎瞬间查到值。诀窍在于：把键交给一个哈希函数变成一个数字，再用这个数字（对数组大小取模）作为一个桶数组的下标。与其去扫描「alice」，不如算出「alice」必然落在哪里，然后直奔过去。
平均而言，插入、查找和删除都是 O(1)——哈希一步就把你指到正确的桶。麻烦在于冲突：两个不同的键可能哈希到同一个桶。哈希表用链地址法（每个桶挂一条小链表）或开放定址法（探查邻近槽位）来处理。配上好的哈希函数和合理的装载因子（太满时会扩容重哈希），冲突就很少见，O(1) 得以保持。在极坏的最坏情况下——大量冲突——操作会退化为 O(n)。
这份速度的代价是哈希表没有顺序：遍历得到的键是任意的、依赖哈希的次序，你也无法廉价地问「最小的键是谁」。当你需要有序时，平衡树（如 std::map）是替代方案；当你只需要按键快速查找时，哈希表更胜一筹。
#include <unordered_map>
#include <string>
std::unordered_map<std::string, int> age;
age["alice"] = 30; // average O(1) insert
age["bob"] = 25;
int a = age["alice"]; // average O(1) lookup -> 30
// buckets: [0] -> ...
// [3] -> ("alice",30) -> ("bob",25) <- a collision, chained
bool has = age.count("carol"); // 0 (not present)hash(key) % buckets 选出一个桶；冲突在桶内以链表相连。
平均 O(1) 的前提是好的哈希函数和有界的装载因子；若键是对抗性的或哈希很差，查找可能退化为 O(n)。
又称
另见