当前位置： 首页 > news >正文

C++ 哈希概念版

news 2025/8/29 8:38:00

C++ 哈希概念详解

这一篇的内容主要是先让大家知道哈希的概念，先了解一下，有概念后再去通过写代码学习。

哈希（Hash）是一种将任意长度的输入（键，key）通过一个哈希函数（Hash Function） 映射为固定长度的输出（哈希值，hash value）的过程。这个输出通常是一个整数值。哈希的核心思想是提供一种快速的数据访问机制，理想情况下，其插入、删除和查找操作的时间复杂度都可以接近 O(1)。

C++中哈希的核心实现是无序关联容器（Unordered Associative Containers），即 std::unordered_map, std::unordered_set 以及它们的多键和无重复版本。

目录
  1. 核心概念：哈希函数、冲突与桶
  2. C++ 标准库中的无序容器
  3. 哈希函数
  4. 处理哈希冲突
  5. 自定义类型作为键
  6. 性能与复杂度
  7. 进阶话题：内存与迭代器

1. 核心概念：哈希函数、冲突与桶

a. 哈希函数 (Hash Function)

一个好的哈希函数应该：

  • 确定性：相同的键必须总是产生相同的哈希值。
  • 高效性：计算速度要快。
  • 均匀分布：键的哈希值应尽可能均匀地分布在所有可能的输出值上，以减少冲突。
b. 哈希冲突 (Hash Collision)

当两个不同的键 key1 和 key2 经由哈希函数计算后得到了相同的哈希值，即 hash(key1) == hash(key2)，这就发生了哈希冲突。这是不可避免的，因此需要有解决冲突的机制。

c. 桶 (Buckets)

C++的无序容器内部使用一个数组（哈希表）来存储数据。这个数组的每一个元素称为一个“桶”（Bucket）。哈希值决定了键值对应该被放入哪个桶中。

// 概念上的简化表示
std::vector<std::list<std::pair<Key, T>>> buckets; // 哈希表是一个向量，每个元素是一个链表（桶）

键的哈希值经过模运算（hash_value % bucket_count）得到桶的索引。

2. C++ 标准库中的无序容器

C++11引入了四种无序容器，位于 <unordered_map> 和 <unordered_set> 头文件中。

容器描述示例
std::unordered_map键值对集合，键唯一std::unordered_map<std::string, int>
std::unordered_multimap键值对集合，键可重复std::unordered_multimap<std::string, int>
std::unordered_set键的集合，键唯一std::unordered_set<int>
std::unordered_multiset键的集合，键可重复std::unordered_multiset<int>

代码示例：std::unordered_map 的基本使用

#include <iostream>
#include <unordered_map>
#include <string>int main() {// 初始化std::unordered_map<std::string, int> ageMap = {{"Alice", 30},{"Bob", 25},{"Charlie", 28}};// 插入元素ageMap["David"] = 22; // 方式一：使用下标运算符ageMap.insert({"Eve", 26}); // 方式二：使用insert方法// 访问元素std::cout << "Alice is " << ageMap["Alice"] << " years old.\n"; // 使用下标（如果键不存在，会创建它）// 使用 at() 更安全，键不存在时会抛出 std::out_of_range 异常try {std::cout << "Frank is " << ageMap.at("Frank") << " years old.\n";} catch (const std::out_of_range& e) {std::cout << "Frank not found in the map.\n";}// 查找元素 (推荐，避免意外插入)auto it = ageMap.find("Bob");if (it != ageMap.end()) {std::cout << "Found Bob, age: " << it->second << '\n';} else {std::cout << "Bob not found.\n";}// 遍历元素std::cout << "\nAll entries:\n";for (const auto& pair : ageMap) { // 范围for循环std::cout << pair.first << ": " << pair.second << '\n';}// 桶接口查看（调试用）std::cout << "\nNumber of buckets: " << ageMap.bucket_count() << '\n';std::cout << "Load factor: " << ageMap.load_factor() << '\n'; // 元素数/桶数return 0;
}

3. 哈希函数

C++标准库为所有基本类型（int, char, std::string 等）提供了默认的哈希函数 std::hash<T>。

代码示例：使用 std::hash

#include <iostream>
#include <functional> // 包含 std::hash
#include <string>int main() {std::hash<std::string> string_hasher;std::hash<int> int_hasher;std::string name = "Alice";int number = 42;size_t hash_value_string = string_hasher(name); // size_t 是无符号整数类型，用于表示大小和哈希值size_t hash_value_int = int_hasher(number);std::cout << "Hash of '" << name << "' is: " << hash_value_string << '\n';std::cout << "Hash of " << number << " is: " << hash_value_int << '\n';// 可以直接用在 unordered_map 的模板参数中（默认就是它）std::unordered_map<std::string, int, std::hash<std::string>> myMap; // 显式写出第三个模板参数return 0;
}

4. 处理哈希冲突：链地址法 (Separate Chaining)

C++标准库无序容器默认使用链地址法来解决冲突。每个桶不是一个直接存储元素的位置，而是一个链表（或其它类似结构）的头节点。所有哈希到同一个桶的键值对都会被放入这个链表中。

  • 插入：计算哈希，找到桶，将新元素添加到链表中。
  • 查找：计算哈希，找到桶，在链表中进行线性搜索。

当链表过长时，性能会从 O(1) 退化为 O(n)。因此，容器需要重新哈希（Rehashing）。

5. 自定义类型作为键

如果你想使用自定义的类或结构体作为 unordered_map 或 unordered_set 的键，你需要做两件事：

  1. 自定义哈希函数：告诉容器如何计算你的类型的哈希值。
  2. 重载 operator==：告诉容器如何判断两个键是否相等（用于解决冲突时的链表比较）。

代码示例：将 Person 类作为键

#include <iostream>
#include <unordered_map>
#include <string>class Person {
public:std::string name;int id;Person(std::string n, int i) : name(std::move(n)), id(i) {}// 1. 重载相等运算符 == (必须的)bool operator==(const Person& other) const {// 判断两个Person是否“相等”的逻辑// 作为键，如果id和name都相同，我们认为他们是同一个键return (id == other.id) && (name == other.name);}
};// 2. 自定义哈希函数
// 通过重载 std::hash 的函数调用运算符
namespace std {template<>struct hash<Person> {size_t operator()(const Person& p) const {// 一个好的做法是结合所有参与判断“相等”的成员的哈希值// 可以使用异或、加法等组合，但要小心避免总是产生相同结果（如 a ^ a = 0）size_t h1 = std::hash<std::string>{}(p.name);size_t h2 = std::hash<int>{}(p.id);// 一个常见的组合方式return h1 ^ (h2 << 1); // 将h2左移一位再与h1异或}};
}// 另一种方式：将自定义哈希函数作为独立的函数对象，并作为模板参数传入
struct PersonHasher {size_t operator()(const Person& p) const {return std::hash<std::string>{}(p.name) ^ std::hash<int>{}(p.id);}
};// 注意：如果使用独立的 PersonHasher，定义map时需要显式指定：
// std::unordered_map<Person, std::string, PersonHasher> personMap;int main() {// 因为我们特化了 std::hash<Person>，所以可以直接使用，无需第三个模板参数std::unordered_map<Person, std::string> personMap;Person alice("Alice", 1);Person bob("Bob", 2);personMap[alice] = "CEO";personMap[bob] = "Engineer";// 查找测试Person searchKey("Alice", 1);auto it = personMap.find(searchKey);if (it != personMap.end()) {std::cout << "Found Alice: " << it->second << '\n'; // 输出: Found Alice: CEO}return 0;
}

6. 性能与复杂度

无序容器的性能严重依赖于：

  1. 哈希函数的质量：分布越均匀，冲突越少。
  2. 桶的数量：桶越多，冲突概率越低，但内存占用越大。

容器会自动管理桶的数量。当负载因子（Load Factor）（size() / bucket_count()）超过最大负载因子（Max Load Factor） 时，容器会执行“重新哈希”（Rehash）：

  • 分配一个更大的桶数组（通常是大约两倍大小）。
  • 重新计算每个元素的哈希，并将其放入新的桶中。
  • 这是一个相对昂贵的 O(n) 操作。

你可以手动控制这个过程：

std::unordered_map<std::string, int> myMap;// 设置最大负载因子
myMap.max_load_factor(0.7); // 默认通常是 1.0// 预留特定数量的桶，避免后续插入时多次rehash
myMap.reserve(100); // 预分配至少能容纳100个元素的桶数（C++11后推荐）
// 或者
myMap.rehash(100); // 直接确保桶数至少为100

7. 进阶话题

a. 内存开销

无序容器由于其内部结构（指针数组、链表节点），内存开销通常比有序容器（如 std::map）更大。每个元素都需要额外的开销来存储链表指针。

b. 迭代器失效
  • 插入操作：可能引起重新哈希，导致所有迭代器失效（但引用不会失效）。
  • 删除操作：只会使指向被删除元素的迭代器失效。
c. std::string_view 作为键 (C++17)

为了避免复制整个字符串，可以使用 std::string_view 作为键。但需要特别注意：它所引用的原始字符串的生命周期必须比 unordered_map 长。

#include <iostream>
#include <unordered_map>
#include <string>
#include <string_view>// 为 string_view 特化哈希（C++17已提供，无需自己实现）
// 但需要自定义哈希和比较器，或者确保C++20（默认支持）
int main() {std::string longString = "This is a very long string that we don‘t want to copy.";// 传统方式：map 会复制一份字符串// std::unordered_map<std::string, int> mapWithCopy;// 使用 string_view：不复制字符串，只记录视图std::unordered_map<std::string_view, int> mapWithView;mapWithView[longString] = 42; // 这里不会复制longString的内容// 但longString必须一直存在！std::cout << mapWithView["This is a very long string that we don‘t want to copy."] << '\n'; // 输出 42return 0;
}
// 危险示例：如果mapWithView的生命周期超过了longString，那么访问将是未定义行为！

总结与选择

特性std::unordered_map/setstd::map/set (有序容器)
底层结构哈希表红黑树
平均复杂度O(1)O(log n)
最坏复杂度O(n) (所有键冲突)O(log n)
元素顺序无序按键排序（基于 <）
自定义键要求需要 std::hash 和 operator==需要 operator< 或自定义比较器
内存使用通常更高（指针开销）通常更低
适用场景需要极快查找，不关心顺序需要元素有序，或按顺序遍历

黄金法则：

  • 需要快速查找、插入、删除且不关心顺序时，用 unordered_*。
  • 需要元素自然有序，或者需要按顺序遍历，或者无法定义良好的哈希函数时，用 map/set。
http://www.xdnf.cn/news/1380529.html

相关文章：

  • 【实战笔记】OCI Ubuntu 24.04 + TigerVNC + XFCE + Chrome 开机自启全记录
  • 错误模块路径: C:\Windows\Microsoft.NET\Framework64\v4.0.30319\clr.dll
  • 从卡顿到丝滑：大型前端项目 CSS 优化全攻略
  • [高并发系统设计] - 搭建高并发高可用的系统 - 学习与探究
  • 【大前端】React useEffect 详解：从入门到进阶
  • Shi-Tomasi 算法和 Harris 角点检测算法都是经典的角点检测方法，但它们在理论基础和实现细节上有一些区别。下面我将详细对比这两种算法。
  • List＜Map＜String, String＞＞最简单的遍历方式
  • 【传奇开心果系列】Flet框架带图标带交互动画的办公用品费用占比统计饼图自定义模板
  • GitHub 热榜项目 - 日榜(2025-08-28)
  • 达梦数据库-重做日志文件（一）
  • 云计算学习100天-第30天
  • 09- AI大模型-docker部署dify以及 dify的使用案例:公司智能助手(构建知识库)(上篇)
  • TDengine 数据订阅支持 MQTT 协议用户手册
  • 【SQL】计算一年内每个月份的周数据
  • 上海控安：WiFi网络安全攻击
  • SONiC 之 Testbed（2）Ansible
  • GeoScene Maps 完整入门指南：从安装到实战
  • Android稳定性问题的常见原因是什么
  • 【python】@staticmethod装饰器
  • 同一个栅格数据，为何在QGIS和ArcGIS Pro中打开后显示的数值范围不同？
  • 苍穹外卖项目笔记day01
  • 【VSCode】使用VSCode打开md文件以及转化为PDF
  • uni-app 网络请求与后端交互完全指南：从基础到实战
  • ckman部署的clickhouse，节点迁移
  • Logstash数据迁移之es-to-kafka.conf详细配置
  • 用 Docker 玩转 Kafka 4.0镜像选型、快速起步、配置持久化与常见坑
  • 让模糊物体变清晰的视频AI：快速提升画质指南
  • 三维视频融合驱动视频孪生创新：智汇云舟引领数字孪生产业新范式
  • Runway Gen-2 深度技术解析：AI视频生成的范式变革
  • RAGFlow