111 std::unordered_map (哈希表实现)

作者Lou Xiao, deepseek创建时间2025-04-02 17:44:58更新时间2025-04-02 17:44:58

1. 基本概念

1.1 定义与特性

关联容器：存储键值对(key-value)的容器
无序性：元素不以任何特定顺序排序
哈希表实现：基于哈希表数据结构实现
唯一键：每个键只能出现一次
快速访问：平均情况下O(1)的查找复杂度

1.2 头文件

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            #include <unordered_map>

2. 模板参数

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            template<
                        
                                class Key,
                        
                                class T,
                        
                                class Hash = std::hash<Key>,
                        
                                class KeyEqual = std::equal_to<Key>,
                        
                                class Allocator = std::allocator<std::pair<const Key, T>>
                        
                            > class unordered_map;

Key：键类型
T：值类型
Hash：哈希函数对象类型（默认std::hash<Key>）
KeyEqual：键比较函数对象类型（默认std::equal_to<Key>）
Allocator：分配器类型

3. 构造函数与初始化

3.1 构造方法

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 1. 默认构造函数
                        
                            std::unordered_map<std::string, int> map1;
                        
                            // 2. 范围构造函数
                        
                            std::vector<std::pair<std::string, int>> vec = {{"a", 1}, {"b", 2}};
                        
                            std::unordered_map<std::string, int> map2(vec.begin(), vec.end());
                        
                            // 3. 初始化列表构造函数
                        
                            std::unordered_map<std::string, int> map3 = {{"apple", 3}, {"banana", 5}};
                        
                            // 4. 拷贝构造函数
                        
                            std::unordered_map<std::string, int> map4(map3);
                        
                            // 5. 移动构造函数
                        
                            std::unordered_map<std::string, int> map5(std::move(map4));
                        
                            // 6. 指定桶数量的构造函数
                        
                            std::unordered_map<std::string, int> map6(10); // 初始桶数为10

3.2 赋值操作

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            map1 = map2;            // 拷贝赋值
                        
                            map1 = std::move(map2); // 移动赋值
                        
                            map1 = {{"a",1}, {"b",2}}; // 初始化列表赋值

4. 元素访问

4.1 直接访问

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 使用[]运算符访问（不存在时会插入）
                        
                            int val = map["key"];
                        
                            // 使用at()访问（不存在时抛出std::out_of_range异常）
                        
                            int val = map.at("key");

4.2 迭代器访问

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 遍历所有元素
                        
                            for (const auto& pair : map) {
                        
                                std::cout << pair.first << ": " << pair.second << std::endl;
                        
                            }
                        
                            // 使用迭代器
                        
                            for (auto it = map.begin(); it != map.end(); ++it) {
                        
                                std::cout << it->first << ": " << it->second << std::endl;
                        
                            }

5. 容量查询

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            bool empty = map.empty();  // 是否为空
                        
                            size_t size = map.size();  // 元素数量
                        
                            size_t max_size = map.max_size(); // 最大可能元素数量

6. 修改操作

6.1 插入元素

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 1. 使用insert
                        
                            map.insert({"key", 42});
                        
                            map.insert(std::make_pair("key", 42));
                        
                            // 2. 使用emplace
                        
                            map.emplace("key", 42); // 直接构造元素，避免临时对象
                        
                            // 3. 使用try_emplace (C++17)
                        
                            map.try_emplace("key", 42); // 只在键不存在时插入
                        
                            // 4. 使用insert_or_assign (C++17)
                        
                            map.insert_or_assign("key", 42); // 存在则更新，不存在则插入

6.2 删除元素

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 1. 通过键删除
                        
                            size_t count = map.erase("key"); // 返回删除的元素数量(0或1)
                        
                            // 2. 通过迭代器删除
                        
                            auto it = map.find("key");
                        
                            if (it != map.end()) {
                        
                                map.erase(it);
                        
                            }
                        
                            // 3. 删除范围
                        
                            map.erase(map.begin(), map.end()); // 删除所有元素
                        
                            // 4. 清空容器
                        
                            map.clear();

7. 查找操作

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 1. 使用find
                        
                            auto it = map.find("key");
                        
                            if (it != map.end()) {
                        
                                // 找到元素
                        
                            }
                        
                            // 2. 使用count
                        
                            if (map.count("key") > 0) {
                        
                                // 键存在
                        
                            }
                        
                            // 3. 使用contains (C++20)
                        
                            if (map.contains("key")) {
                        
                                // 键存在
                        
                            }

8. 桶接口

8.1 桶管理

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            size_t bucket_count = map.bucket_count(); // 桶数量
                        
                            size_t max_bucket_count = map.max_bucket_count(); // 最大桶数量
                        
                            size_t bucket_size = map.bucket_size(n); // 第n个桶中的元素数量
                        
                            size_t bucket = map.bucket("key"); // 键所在的桶索引

8.2 哈希策略

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            float load_factor = map.load_factor(); // 当前负载因子
                        
                            float max_load = map.max_load_factor(); // 最大负载因子
                        
                            map.max_load_factor(0.7f); // 设置最大负载因子
                        
                            map.rehash(100); // 设置桶数量至少为100
                        
                            map.reserve(100); // 预留空间至少容纳100个元素

9. 观察器

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 获取哈希函数
                        
                            auto hash_func = map.hash_function();
                        
                            // 获取键比较函数
                        
                            auto key_eq = map.key_eq();
                        
                            // 获取分配器
                        
                            auto alloc = map.get_allocator();

10. 非成员函数

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            // 比较运算符
                        
                            bool equal = (map1 == map2);
                        
                            // 交换两个unordered_map
                        
                            std::swap(map1, map2);
                        
                            // 特化swap算法
                        
                            swap(map1, map2);

11. 性能与优化

11.1 性能特点

平均时间复杂度：
- 插入：O(1)
- 删除：O(1)
- 查找：O(1)
最坏时间复杂度：O(n)（所有元素哈希冲突时）

11.2 优化建议

选择合适的哈希函数：对于自定义类型，提供良好的哈希函数
预分配空间：使用reserve()减少重新哈希次数
调整负载因子：根据场景调整max_load_factor
避免频繁插入删除：批量操作更高效

12. 自定义类型作为键

12.1 要求

必须提供哈希函数
必须提供相等比较函数

12.2 示例

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            struct MyKey {
                        
                                std::string first;
                        
                                std::string second;
                        
                            };
                        
                            // 自定义哈希函数
                        
                            struct MyHash {
                        
                                std::size_t operator()(const MyKey& k) const {
                        
                                    return std::hash<std::string>()(k.first) ^ 
                        
                                           (std::hash<std::string>()(k.second) << 1);
                        
                                }
                        
                            };
                        
                            // 自定义相等比较
                        
                            struct MyEqual {
                        
                                bool operator()(const MyKey& lhs, const MyKey& rhs) const {
                        
                                    return lhs.first == rhs.first && lhs.second == rhs.second;
                        
                                }
                        
                            };
                        
                            std::unordered_map<MyKey, int, MyHash, MyEqual> my_map;

13. 与std::map的比较

特性	std::unordered_map	std::map
实现	哈希表	红黑树
排序	无序	按键排序
查找复杂度	平均O(1)，最坏O(n)	O(log n)
插入复杂度	平均O(1)，最坏O(n)	O(log n)
内存使用	通常更高	通常更低
迭代器稳定性	插入/删除可能使所有迭代器失效	除删除元素外保持稳定
适用场景	需要快速查找，不关心顺序	需要有序或稳定迭代器

14. 实际应用示例

14.1 词频统计

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            std::unordered_map<std::string, int> word_count;
                        
                            std::string word;
                        
                            while (std::cin >> word) {
                        
                                ++word_count[word];
                        
                            }
                        
                            for (const auto& pair : word_count) {
                        
                                std::cout << pair.first << ": " << pair.second << std::endl;
                        
                            }

14.2 缓存实现

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            template<typename Key, typename Value>
                        
                            class LRUCache {
                        
                            private:
                        
                                std::unordered_map<Key, typename std::list<std::pair<Key, Value>>::iterator> cache_map;
                        
                                std::list<std::pair<Key, Value>> cache_list;
                        
                                size_t capacity;
                        
                            public:
                        
                                LRUCache(size_t capacity) : capacity(capacity) {}
                        
                                Value get(const Key& key) {
                        
                                    auto it = cache_map.find(key);
                        
                                    if (it == cache_map.end()) {
                        
                                        throw std::out_of_range("Key not found");
                        
                                    }
                        
                                    cache_list.splice(cache_list.begin(), cache_list, it->second);
                        
                                    return it->second->second;
                        
                                }
                        
                                void put(const Key& key, const Value& value) {
                        
                                    auto it = cache_map.find(key);
                        
                                    if (it != cache_map.end()) {
                        
                                        cache_list.splice(cache_list.begin(), cache_list, it->second);
                        
                                        it->second->second = value;
                        
                                        return;
                        
                                    }
                        
                                    if (cache_map.size() == capacity) {
                        
                                        auto last = cache_list.back();
                        
                                        cache_map.erase(last.first);
                        
                                        cache_list.pop_back();
                        
                                    }
                        
                                    cache_list.emplace_front(key, value);
                        
                                    cache_map[key] = cache_list.begin();
                        
                                }
                        
                            };

15. 注意事项

迭代器失效：
- 插入操作可能导致所有迭代器失效（重新哈希时）
- 删除操作只使指向被删除元素的迭代器失效
自定义哈希函数：
- 应尽量均匀分布哈希值
- 对于相同输入必须产生相同输出
- 性能敏感场景需要优化哈希函数
线程安全：
- 标准库容器不是线程安全的
- 多线程访问需要外部同步机制
异常安全：
- 基本保证：操作失败时容器保持有效状态
- 强保证：某些操作如insert提供强异常保证
内存使用：
- 哈希表通常比基于树的实现使用更多内存
- 负载因子影响内存使用和性能

std::unordered_map 常用 API 的整理表格

名称	用途	原型	代码示例	注释
构造函数	创建空的 `unordered_map` 或从其他容器初始化	`unordered_map()` `unordered_map(InputIt first, InputIt last)`	`cpp<br>std::unordered_map<int, std::string> map1;<br>std::unordered_map<int, std::string> map2({{1, "a"}, {2, "b"}});<br>`	默认构造或通过迭代器范围初始化。
insert	插入键值对	`pair<iterator, bool> insert(const value_type& value)`	`cpp<br>auto ret = map1.insert({3, "c"});<br>`	返回插入结果的迭代器和是否成功的布尔值。
emplace	原地构造键值对（避免拷贝）	`pair<iterator, bool> emplace(Args&&... args)`	`cpp<br>auto ret = map1.emplace(4, "d");<br>`	效率高于 `insert`，直接传递构造参数。
operator[]	访问或插入元素（若键不存在则默认构造）	`mapped_type& operator[](const key_type& key)`	`cpp<br>map1[5] = "e";<br>`	若键不存在会自动插入，值类型需有默认构造函数。
at	安全访问元素（键不存在时抛出异常）	`mapped_type& at(const key_type& key)`	`cpp<br>try {<br> auto val = map1.at(5);<br>} catch(...) {}<br>`	比 `operator[]` 更安全，但需处理异常。
find	查找键对应的迭代器（未找到返回 `end()`）	`iterator find(const key_type& key)`	`cpp<br>auto it = map1.find(3);<br>if (it != map1.end()) { /.../ }<br>`	查找时间复杂度为平均 O(1)，最坏 O(n)。
erase	删除元素（通过键或迭代器）	`size_type erase(const key_type& key)` `iterator erase(iterator pos)`	`cpp<br>map1.erase(3);<br>auto it = map1.find(4);<br>if (it != map1.end()) map1.erase(it);<br>`	返回删除的元素数量（0 或 1）。
clear	清空所有元素	`void clear()`	`cpp<br>map1.clear();<br>`	容器大小变为 0，但保留原有桶数量。
size	返回元素数量	`size_type size() const`	`cpp<br>size_t count = map1.size();<br>`	时间复杂度 O(1)。
empty	检查容器是否为空	`bool empty() const`	`cpp<br>if (map1.empty()) { /.../ }<br>`	等价于 `size() == 0`。
bucket_count	返回哈希桶的数量	`size_type bucket_count() const`	`cpp<br>size_t buckets = map1.bucket_count();<br>`	桶数量通常大于 `size()` 以保持低冲突率。
load_factor	返回当前负载因子（元素数/桶数）	`float load_factor() const`	`cpp<br>float lf = map1.load_factor();<br>`	负载因子超过 `max_load_factor()` 时会触发 rehash。
rehash	调整桶的数量以优化性能	`void rehash(size_type count)`	`cpp<br>map1.rehash(100);<br>`	若 `count > size() / max_load_factor()`，桶数量会增加。
reserve	预留空间以避免重复 rehash	`void reserve(size_type count)`	`cpp<br>map1.reserve(100);<br>`	等价于 `rehash(std::ceil(count / max_load_factor()))`。

补充说明

键值类型要求：键类型必须支持 std::hash 和 operator==。
迭代器失效：除 erase 被调用元素的迭代器外，其他迭代器在 rehash 时可能失效。
自定义哈希/比较函数：可通过模板参数指定：

 1.双击鼠标左键复制此行；2.单击复制所有代码。 
                                
                            struct MyHash { size_t operator()(const Key& k) const { /*...*/ } };
                        
                            std::unordered_map<Key, Value, MyHash> custom_map;

文章目录

1	template<
2	class Key,
3	class T,
4	class Hash = std::hash<Key>,
5	class KeyEqual = std::equal_to<Key>,
6	class Allocator = std::allocator<std::pair<const Key, T>>
7	> class unordered_map;

1	// 1. 默认构造函数
2	std::unordered_map<std::string, int> map1;
3
4	// 2. 范围构造函数
5	std::vector<std::pair<std::string, int>> vec = {{"a", 1}, {"b", 2}};
6	std::unordered_map<std::string, int> map2(vec.begin(), vec.end());
7
8	// 3. 初始化列表构造函数
9	std::unordered_map<std::string, int> map3 = {{"apple", 3}, {"banana", 5}};
10
11	// 4. 拷贝构造函数
12	std::unordered_map<std::string, int> map4(map3);
13
14	// 5. 移动构造函数
15	std::unordered_map<std::string, int> map5(std::move(map4));
16
17	// 6. 指定桶数量的构造函数
18	std::unordered_map<std::string, int> map6(10); // 初始桶数为10

1	map1 = map2; // 拷贝赋值
2	map1 = std::move(map2); // 移动赋值
3	map1 = {{"a",1}, {"b",2}}; // 初始化列表赋值

1	// 使用[]运算符访问（不存在时会插入）
2	int val = map["key"];
3
4	// 使用at()访问（不存在时抛出std::out_of_range异常）
5	int val = map.at("key");

1	// 遍历所有元素
2	for (const auto& pair : map) {
3	std::cout << pair.first << ": " << pair.second << std::endl;
4	}
5
6	// 使用迭代器
7	for (auto it = map.begin(); it != map.end(); ++it) {
8	std::cout << it->first << ": " << it->second << std::endl;
9	}

1	bool empty = map.empty(); // 是否为空
2	size_t size = map.size(); // 元素数量
3	size_t max_size = map.max_size(); // 最大可能元素数量

1	// 1. 使用insert
2	map.insert({"key", 42});
3	map.insert(std::make_pair("key", 42));
4
5	// 2. 使用emplace
6	map.emplace("key", 42); // 直接构造元素，避免临时对象
7
8	// 3. 使用try_emplace (C++17)
9	map.try_emplace("key", 42); // 只在键不存在时插入
10
11	// 4. 使用insert_or_assign (C++17)
12	map.insert_or_assign("key", 42); // 存在则更新，不存在则插入

1	// 1. 通过键删除
2	size_t count = map.erase("key"); // 返回删除的元素数量(0或1)
3
4	// 2. 通过迭代器删除
5	auto it = map.find("key");
6	if (it != map.end()) {
7	map.erase(it);
8	}
9
10	// 3. 删除范围
11	map.erase(map.begin(), map.end()); // 删除所有元素
12
13	// 4. 清空容器
14	map.clear();

1	// 1. 使用find
2	auto it = map.find("key");
3	if (it != map.end()) {
4	// 找到元素
5	}
6
7	// 2. 使用count
8	if (map.count("key") > 0) {
9	// 键存在
10	}
11
12	// 3. 使用contains (C++20)
13	if (map.contains("key")) {
14	// 键存在
15	}

1	size_t bucket_count = map.bucket_count(); // 桶数量
2	size_t max_bucket_count = map.max_bucket_count(); // 最大桶数量
3	size_t bucket_size = map.bucket_size(n); // 第n个桶中的元素数量
4	size_t bucket = map.bucket("key"); // 键所在的桶索引

1	float load_factor = map.load_factor(); // 当前负载因子
2	float max_load = map.max_load_factor(); // 最大负载因子
3	map.max_load_factor(0.7f); // 设置最大负载因子
4	map.rehash(100); // 设置桶数量至少为100
5	map.reserve(100); // 预留空间至少容纳100个元素

1	// 获取哈希函数
2	auto hash_func = map.hash_function();
3
4	// 获取键比较函数
5	auto key_eq = map.key_eq();
6
7	// 获取分配器
8	auto alloc = map.get_allocator();

1	// 比较运算符
2	bool equal = (map1 == map2);
3
4	// 交换两个unordered_map
5	std::swap(map1, map2);
6
7	// 特化swap算法
8	swap(map1, map2);

1	struct MyKey {
2	std::string first;
3	std::string second;
4	};
5
6	// 自定义哈希函数
7	struct MyHash {
8	std::size_t operator()(const MyKey& k) const {
9	return std::hash<std::string>()(k.first) ^
10	(std::hash<std::string>()(k.second) << 1);
11	}
12	};
13
14	// 自定义相等比较
15	struct MyEqual {
16	bool operator()(const MyKey& lhs, const MyKey& rhs) const {
17	return lhs.first == rhs.first && lhs.second == rhs.second;
18	}
19	};
20
21	std::unordered_map<MyKey, int, MyHash, MyEqual> my_map;

1	std::unordered_map<std::string, int> word_count;
2	std::string word;
3	while (std::cin >> word) {
4	++word_count[word];
5	}
6
7	for (const auto& pair : word_count) {
8	std::cout << pair.first << ": " << pair.second << std::endl;
9	}

1	template<typename Key, typename Value>
2	class LRUCache {
3	private:
4	std::unordered_map<Key, typename std::list<std::pair<Key, Value>>::iterator> cache_map;
5	std::list<std::pair<Key, Value>> cache_list;
6	size_t capacity;
7
8	public:
9	LRUCache(size_t capacity) : capacity(capacity) {}
10
11	Value get(const Key& key) {
12	auto it = cache_map.find(key);
13	if (it == cache_map.end()) {
14	throw std::out_of_range("Key not found");
15	}
16	cache_list.splice(cache_list.begin(), cache_list, it->second);
17	return it->second->second;
18	}
19
20	void put(const Key& key, const Value& value) {
21	auto it = cache_map.find(key);
22	if (it != cache_map.end()) {
23	cache_list.splice(cache_list.begin(), cache_list, it->second);
24	it->second->second = value;
25	return;
26	}
27
28	if (cache_map.size() == capacity) {
29	auto last = cache_list.back();
30	cache_map.erase(last.first);
31	cache_list.pop_back();
32	}
33
34	cache_list.emplace_front(key, value);
35	cache_map[key] = cache_list.begin();
36	}
37	};

1	struct MyHash { size_t operator()(const Key& k) const { /.../ } };
2	std::unordered_map<Key, Value, MyHash> custom_map;