map映射和哈希映射

一、map 是怎么存储的？（map所用的时间和空间复杂度都会很低）

map的核心是存储「键值对」（key-value pair），但它不是简单的 “同时存一对数”，而是有更严谨的结构和规则：

1. 存储的基本单元：键值对（本质是 pair）

map<LL, LL> m中，每一个存入的元素（比如m[100] = 5），在map内部都会被封装成一个pair<const LL, LL>类型的对象：

• 第一个值：const LL类型的键（key）→ 例子中是100（map的键是只读的，不能修改）；
• 第二个值：LL类型的值（value）→ 例子中是5（可以修改）。

换句话说，map内部存储的每一个元素，本身就是一个pair，但map会对这些pair做额外的管理。

2. map 的底层实现：红黑树（有序 + 平衡）

map不是把pair随便存起来，而是用红黑树（一种自平衡的二叉搜索树）来组织这些pair：

• 所有pair会按照键（key）的大小自动排序（比如按数字从小到大）；
• 红黑树保证了map的查询、插入、删除操作的时间复杂度都是O(logn)；
• 这种有序性是map的核心特征（和unordered_map区分的关键）

3.自动排序示例：

map<LL, LL> m; m[5] = 2; // 存入键5，值2 → 内部是 pair<const LL, LL>(5, 2) m[2] = 3; // 存入键2，值3 → 内部是 pair<const LL, LL>(2, 3) m[8] = 1; // 存入键8，值1 → 内部是 pair<const LL, LL>(8, 1)

map内部会把这 3 个pair按键的大小排序，实际存储顺序是：(2,3)→(5,2)→(8,1)（而不是插入的 5→2→8 顺序）。

维度	map	pair
本质	关联式容器（存储多个键值对）	数据结构体（存储两个任意类型的值）
存储数量	可以存储 0~n 个键值对	只能存储 2 个值（一组）
有序性	自动按键排序（红黑树特性）	无有序性，两个值的顺序由你定义
唯一性 / 索引	键（key）唯一，可通过键查找值	无 “键” 的概念，两个值地位平等，只能通过first/second访问
适用场景	统计、映射、查找（多组数据）	存储一组相关联的两个值（比如坐标 (x,y)、年龄 + 姓名）

二、哈希映射（unordered_map）

unordered_map 核心本质

unordered_map是 C++ STL 中的哈希表（Hash Table）实现，核心是「用哈希函数将键映射到存储位置」，从而实现平均 O (1) 的插入 / 查询 / 删除效率。

1. 底层结构（通俗理解）

• 哈希函数：把键（比如字符串、数字）转换成一个整数（哈希值），这个整数对应哈希表的「桶（bucket）」下标；
• 桶：哈希表的存储单元，每个桶里放哈希值相同的键值对（解决哈希冲突）；
• 冲突解决：默认用「链地址法」—— 同一个桶里的键值对用链表 / 红黑树连接（C++11 后，冲突多的桶会自动转红黑树，优化性能）。

2.与map对比与选择

维度	map（红黑树）	unordered_map（哈希表）
底层实现	自平衡二叉搜索树（红黑树）	哈希表 + 桶（解决冲突）
有序性	按键自动升序排序	无序（哈希值随机分布）
时间复杂度（平均）	插入 / 查询 / 删除 O (logn)	插入 / 查询 / 删除 O (1)
时间复杂度（最坏）	O (logn)（稳定）	O (n)（哈希冲突极端情况）
内存开销	中等（红黑树节点）	稍大（哈希表桶 + 冗余空间）
支持的操作	有序遍历、找前驱 / 后继、区间查询	仅支持单个键的增删查
适用数据类型	所有可比较的类型（如 int/string）	需支持哈希函数（默认支持 int/string，自定义类型需手动写哈希）

三、相对于数组的优势

方式	实现逻辑	适用场景	这里为什么不行？
数组	cnt[x]++（x 是数组下标）	x 的范围小且连续（比如0~1e5）	x 可能是1e18或-1e9，数组下标无法表示
map/unordered_map	m[x]++（x 是键）	x 范围极大、离散、甚至负数	完美适配题目中 的数值特征

当题目明确给出a[i]的数值范围很小（比如0 ≤ a[i] ≤ 1e5）时，才能用数组

例题：

AcWing 835. Trie字符串统计

#include <bits/stdc++.h> using namespace std; const int N = 20010; map<string, int> m;//动态数组 int main(){ ios::sync_with_stdio(false); //关闭 C++ 标准流（cin/cout）和 C 标准流（stdio 的 scanf/printf）之间的同步 cin.tie(nullptr); //解除 cin 和 cout 的绑定关系。 int n; cin >> n; while(n--){ char opt; string s; cin >> opt >> s; if(opt == 'I'){ m[s]++; }else if(opt =='Q'){ cout << m[s] << endl; } } return 0; }

P1102 A-B 数对

#include <iostream> #include <unordered_map> // 替换为unordered_map using namespace std; typedef long long LL; LL a[200001]; unordered_map<LL,LL> m; // 哈希表，查询更快 int main() { int n; LL c; LL ans=0; cin >> n >> c; for(int i=1;i<=n;i++) { cin >> a[i]; m[a[i]]++; a[i]-=c; } for(int i=1;i<=n;i++) ans+=m[a[i]]; cout << ans << endl; return 0; }