面试数据结构：哈希表

哈希表通过哈希函数把 key 映射到桶。

C++ 容器

std::unordered_map<std::string, int> count;
std::unordered_set<int> seen;

平均情况下，插入、查找、删除接近 O(1)。

常见题型

• 两数之和。
• 字符频次统计。
• 去重。
• 判断集合关系。
• 前缀和 + 哈希表。

注意

哈希表不是有序结构。如果需要顺序，考虑 std::map 或排序。

两数之和为什么用哈希表

暴力做法要枚举两个数，复杂度是 O(n^2)。哈希表的做法是边遍历边记录已经见过的值：

for (int i = 0; i < nums.size(); ++i) {
    int need = target - nums[i];
    if (pos.contains(need)) return {pos[need], i};
    pos[nums[i]] = i;
}

它把“找另一个数”的过程从线性扫描变成哈希查找。

前缀和 + 哈希表

很多子数组问题都可以转成前缀和问题。比如寻找和为 k 的子数组数量，可以统计之前出现过多少次 prefix - k。

这类题的关键是把“连续区间”转成“两个前缀和的差”。

工程注意

哈希表平均复杂度很好，但最坏情况并不总是 O(1)。工程里如果 key 很复杂，要关注哈希函数质量和内存占用。