C++ 数据结构:哈希表原理与 STL 实现详解
哈希表基础
首先需要明确哈希(Hash)与哈希表(Hash Table)的区别。哈希是一种映射算法思想,而哈希表则是基于这种思想构建的数据结构。
哈希表的核心流程是统一的:获取一个 Key,通过哈希函数计算 Hasher(Key),得到存储位置并存放 Value;或者从该位置取出对应的 Value。
理解哈希表的三个层次
要深入理解哈希表,建议从以下三个层面递进学习:
- 哈希值:这是最基础的整数表示。
- 哈希函数:将哈希值映射到具体空间位置的方法。
- 哈希冲突:当多个 Key 映射到同一位置时的处理机制。
STL 底层哈希函数的本质是对哈希值进行二次 Hash。无论 Key 是 string、vector 还是其他自定义类型,最终都需要转换为整形哈希值才能被处理。因此,先获得哈希值,再使用哈希函数确定映射位置,是理解的关键逻辑链。
此外,哈希表在逻辑上可视为数组。数组有大小限制,当数据量超过容量或不同自定义类型的哈希值相同,必然产生哈希冲突。哈希是功能,冲突是结果,两者存在因果关系。
哈希值与转换策略
哈希函数通常针对整形数据进行操作(如除留余数法)。在使用 STL 时,若要对自定义类型进行哈希,必须提供将其转换为哈希值的策略(仿函数)。
转换策略需满足速度快、离散度高的要求。常见的策略包括:
- BKDR 哈希:适用于字符串。
- 异或组合:适用于简单容器。
- hash_combine:适用于多成员复杂结构。
BKDR 哈希
优点是实现简单、计算快、离散度高。通过选取种子(如 131),对字符串每个字符进行处理。
size_t BKDRHash(const std::string &str) {
size_t seed = 131; // 常用种子:31, 131, 1313...
size_t hash = 1;
for (auto e : str) {
hash *= seed;
hash += e;
}
return hash & 0x7FFFFFFF; // 确保返回正数
}
异或组合
适用于 vector<int> 等简单场景,实现简单但冲突率相对较高。
struct PointHash {
size_t operator()(const std::vector<int> &vec) {
hash = ;
( e : vec) {
hash ^= (e << );
}
hash;
}
};



