unordered_map

unordered_map是什么？

unordered_map 是C++ STL中的哈希表容器，用来存储键值对数据。
前面讲解了哈希基础概念，本篇就来介绍一下基于哈希实现的映射容器。
它以key-value形式存放数据，key具有唯一性，依靠key快速查找对应value。
和有序的map不同，unordered_map内部元素存储顺序无序。

unordered_map底层实现

unordered_map底层由哈希表结构实现，开散式哈希采用数组+链表的形式处理数据（这也叫做哈希桶）。
通过哈希函数计算key对应的数组下标，把数据存放至对应位置。
出现多个key算出相同下标时，就会产生哈希冲突，依靠链地址法解决冲突。
对比map：map底层是红黑树，中序遍历元素默认按键从小到大有序排列。

unordered_map核心特点

1. 存储无序，遍历取出的数据顺序和插入顺序不一致
2. key值唯一，不允许重复键，重复插入会覆盖原有数据
3. 根据key查找、插入、删除数据速度极快O（1）时间复杂度
4. key一旦确定无法修改，只能增删替换键值对

哈希冲突详解

1. 哈希冲突概念

不同key经过哈希函数运算后，得到相同的数组下标，该现象即为哈希冲突。
冲突无法彻底消除，只能通过算法规避、合理处理来降低对性能的影响。

2. unordered_map冲突解决方案

STL中unordered_map默认采用链地址法处理冲突。
哈希数组的每个位置作为哈希桶，冲突的数据会以链表形式挂载在对应桶位后方。
感兴趣的朋友可以自行在网上深入了解

3. 冲突带来的影响

冲突越多，链表长度越长
查找元素时需要遍历链表比对键值，查询效率会从理想O(1)逐步下降。在极端哈希冲突的情况下效率由O（1）降为O（N）
容器内置扩容缩容机制，负载因子达到临界值时，会重新开辟空间、重算哈希下标打散数据，缩减链表长度恢复性能。

4. 负载因子与扩容

负载因子 = 元素总个数 / 哈希桶数量
负载因子数值越高，冲突发生概率越大。数学家们发现当负载因子在0.7左右时，哈希表的效率最高，而且也没有造成过多的空间浪费
一旦超出默认阈值，哈希表自动扩容甚至缩容并重新映射所有数据，减少扎堆冲突问题。

5. 简单演示代码

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
    unordered_map<int, int> ump;
    // 插入易产生哈希冲突的键
    ump[2] = 20;
    ump[12] = 120;
    ump[22] = 220;

    // 遍历无序输出，体现哈希存储特性
    for (auto& p : ump)
    {
        cout << p.first << " : " << p.second << endl;
    }

    // 查看当前哈希桶数量
    cout << "哈希桶总数：" << ump.bucket_count() << endl;
    return 0;
}

unordered_map常用接口

头文件：#include <unordered_map>

接口	作用
insert()	插入键值对
erase()	删除指定键的数据
find()	查找指定key，返回迭代器
[]	下标访问、修改、插入数据
size()	获取容器元素个数
empty()	判断容器是否为空
clear()	清空所有数据

unordered_map基础使用示例

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
    unordered_map<int, string> ump;

    // 三种插入方式
    ump[1] = "张三";
    ump.insert({2, "李四"});
    ump.insert(make_pair(3, "王五"));

    // 下标访问取值
    cout << ump[1] << endl;

    // 范围遍历
    for (auto& p : ump)
    {
        cout << p.first << " : " << p.second << endl;
    }

    return 0;
}

查找与删除操作

#include <iostream>
#include <unordered_map>
using namespace std;

int main()
{
    unordered_map<int, int> ump;
    ump[10] = 100;
    ump[20] = 200;
    ump[30] = 300;

    // 查找key为20的数据
    auto it = ump.find(20);
    if (it != ump.end())
    {
        cout << "找到数据：" << it->second << endl;
    }
    else
    {
        cout << "未找到该键" << endl;
    }

    // 删除指定key
    ump.erase(30);

    return 0;
}

[]下标访问注意坑点

使用[]访问不存在的key时，不会报错，反而会自动插入一组默认键值对。
日常查询数据优先使用find()，避免无意新增冗余数据。

注意：如果不用unordered_map的find去查找，而是去用stl算法的find去查找
1.效率大幅下降
自带 find 哈希定位，均摊 O (1)；STL find 只能逐个遍历，复杂度 O (n)，数据越多差距越明显。
2.查询逻辑受限
STL 的 find 只能匹配完整键值对，没法单独根据 key 检索，使用灵活性大打折扣。
3.违背容器设计初衷
舍弃哈希快速查找的特性，相当于把哈希表当成普通遍历容器使用，白白浪费性能优势

unordered_map与map效率对比

操作	unordered_map(哈希表)	map(红黑树)
插入	O(1)	O(logn)
查找	O(1)	O(logn)
删除	O(1)	O(logn)

业务只需要快速存取查找，不要求有序，优先使用unordered_map
需要按键排序遍历数据，选择map容器

简单总结

unordered_map依托哈希表实现，主打高效增删查改。
核心存储形式为键值对，键唯一无序，查询速度是最大优势。
日常刷题、业务开发高频查询场景，优先选用该容器。
使用时规避下标自动插入的问题，根据有序需求选择对应映射容器。