unordered_map

unordered_map 介绍

• unordered_map 中所有元素都是 pair 键值对
• pair 中第一个元素为 key（键），起索引作用，第二个元素为 value（实值）
• 元素不会排序，存储顺序由哈希函数决定
• unordered_map 属于关联式容器，底层结构用哈希表实现
• 根据 key 快速找到 value（时间复杂度 O(1) 平均，O(n) 最坏）

与 map 相同的方法

map

• size()
• empty()
• swap()
• insert()
• clear()
• erase()
• find()
• count()

以上方法的用法与 map 完全相同，不再重复举例。

---

unordered_map 特有的方法

bucket_count

bucket_count() - 获取桶的数量

unordered_map<int, string> mp = {{1, "a"}, {2, "b"}, {3, "c"}};
cout << mp.bucket_count(); // output: 取决于实现（例如 8）

bucket_size

bucket_size() - 获取指定桶中的元素个数

unordered_map<int, string> mp = {{1, "a"}, {2, "b"}, {3, "c"}};
for (int i = 0; i < mp.bucket_count(); i++) {
    cout << "桶 " << i << " 有 " << mp.bucket_size(i) << " 个元素" << endl;
}

bucket

bucket() - 获取元素所在的桶编号

unordered_map<int, string> mp = {{1, "a"}, {2, "b"}, {3, "c"}};
cout << "key 1 在桶: " << mp.bucket(1) << endl;
cout << "key 2 在桶: " << mp.bucket(2) << endl;

load_factor

load_factor() - 获取当前负载因子

unordered_map<int, string> mp = {{1, "a"}, {2, "b"}, {3, "c"}};
cout << "负载因子: " << mp.load_factor() << endl;
// 负载因子 = 元素个数 / 桶数

max_load_factor

max_load_factor() - 获取或设置最大负载因子

unordered_map<int, string> mp;
 
// 获取最大负载因子
cout << "默认最大负载因子: " << mp.max_load_factor() << endl;
 
// 设置最大负载因子
mp.max_load_factor(0.75);
cout << "修改后: " << mp.max_load_factor() << endl;

rehash

rehash() - 设置桶数（重新哈希）

unordered_map<int, string> mp;
cout << "初始桶数: " << mp.bucket_count() << endl;
 
mp.rehash(20);  // 设置桶数为 20
cout << "rehash 后桶数: " << mp.bucket_count() << endl;

reserve

reserve() - 预留空间（避免多次 rehash）

unordered_map<int, string> mp;
mp.reserve(100);  // 预留至少 100 个元素的空间
cout << "预留后桶数: " << mp.bucket_count() << endl;
// 桶数 >= 100 / max_load_factor

hash_function

hash_function() - 获取哈希函数

unordered_map<string, int> mp;
auto hash_fn = mp.hash_function();
cout << "hash(\"hello\") = " << hash_fn("hello") << endl;

key_eq

key_eq() - 获取键相等比较函数

unordered_map<string, int> mp;
auto eq = mp.key_eq();
cout << "是否相等: " << eq("apple", "apple") << endl;  // output: 1
cout << "是否相等: " << eq("apple", "banana") << endl; // output: 0

---

unordered_map 与 map 核心区别

特性	map	unordered_map
底层结构	红黑树	哈希表
查找速度	O(log n)	O(1) 平均
元素顺序	自动排序	无序
特有方法	无（排序相关通过仿函数实现）	bucket_*, load_factor, rehash, reserve 等
适用场景	需要有序遍历	只需要快速查找

---

完整示例

（突出 unordered_map 特性）

#include <iostream>
#include <unordered_map>
using namespace std;
 
int main() {
    // 创建并插入数据
    unordered_map<int, string> mp;
    mp[1] = "apple";
    mp[2] = "banana";
    mp[3] = "orange";
    mp[4] = "grape";
    
    // 查看桶的信息
    cout << "桶的数量: " << mp.bucket_count() << endl;
    cout << "负载因子: " << mp.load_factor() << endl;
    
    // 查看每个 key 所在的桶
    for (const auto& [key, value] : mp) {
        cout << "key " << key << " 在桶 " << mp.bucket(key) << endl;
    }
    
    // 预留空间
    mp.reserve(50);
    cout << "reserve 后桶数: " << mp.bucket_count() << endl;
    
    return 0;
}

---

py vs C++

Python dict 与 C++ unordered_map 对比

操作	C++ unordered_map	Python dict
创建	unordered_map<int,string> mp;	mp = {}
插入	mp[1] = "a"	mp[1] = "a"
访问	mp[1]	mp[1]
存在检查	mp.find(1) != mp.end()	1 in mp
删除	mp.erase(1)	del mp[1]
大小	mp.size()	len(mp)
清空	mp.clear()	mp.clear()
桶相关	bucket_count(), bucket() 等	无直接对应