目录unordered_mapunordered_map是什么unordered_map底层实现unordered_map核心特点哈希冲突详解1. 哈希冲突概念2. unordered_map冲突解决方案3. 冲突带来的影响4. 负载因子与扩容5. 简单演示代码unordered_map常用接口unordered_map基础使用示例查找与删除操作[]下标访问注意坑点unordered_map与map效率对比简单总结unordered_mapunordered_map是什么unordered_map是C STL中的哈希表容器用来存储键值对数据。前面讲解了哈希基础概念本篇就来介绍一下基于哈希实现的映射容器。它以key-value形式存放数据key具有唯一性依靠key快速查找对应value。和有序的map不同unordered_map内部元素存储顺序无序。unordered_map底层实现unordered_map底层由哈希表结构实现开散式哈希采用数组链表的形式处理数据这也叫做哈希桶。通过哈希函数计算key对应的数组下标把数据存放至对应位置。出现多个key算出相同下标时就会产生哈希冲突依靠链地址法解决冲突。对比mapmap底层是红黑树中序遍历元素默认按键从小到大有序排列。unordered_map核心特点存储无序遍历取出的数据顺序和插入顺序不一致key值唯一不允许重复键重复插入会覆盖原有数据根据key查找、插入、删除数据速度极快O1时间复杂度key一旦确定无法修改只能增删替换键值对哈希冲突详解1. 哈希冲突概念不同key经过哈希函数运算后得到相同的数组下标该现象即为哈希冲突。冲突无法彻底消除只能通过算法规避、合理处理来降低对性能的影响。2. unordered_map冲突解决方案STL中unordered_map默认采用链地址法处理冲突。哈希数组的每个位置作为哈希桶冲突的数据会以链表形式挂载在对应桶位后方。感兴趣的朋友可以自行在网上深入了解3. 冲突带来的影响冲突越多链表长度越长查找元素时需要遍历链表比对键值查询效率会从理想O(1)逐步下降。在极端哈希冲突的情况下效率由O1降为ON容器内置扩容缩容机制负载因子达到临界值时会重新开辟空间、重算哈希下标打散数据缩减链表长度恢复性能。4. 负载因子与扩容负载因子 元素总个数 / 哈希桶数量负载因子数值越高冲突发生概率越大。数学家们发现当负载因子在0.7左右时哈希表的效率最高而且也没有造成过多的空间浪费一旦超出默认阈值哈希表自动扩容甚至缩容并重新映射所有数据减少扎堆冲突问题。5. 简单演示代码#includeiostream#includeunordered_mapusingnamespacestd;intmain(){unordered_mapint,intump;// 插入易产生哈希冲突的键ump[2]20;ump[12]120;ump[22]220;// 遍历无序输出体现哈希存储特性for(autop:ump){coutp.first : p.secondendl;}// 查看当前哈希桶数量cout哈希桶总数ump.bucket_count()endl;return0;}unordered_map常用接口头文件#include unordered_map接口作用insert()插入键值对erase()删除指定键的数据find()查找指定key返回迭代器[]下标访问、修改、插入数据size()获取容器元素个数empty()判断容器是否为空clear()清空所有数据unordered_map基础使用示例#includeiostream#includeunordered_mapusingnamespacestd;intmain(){unordered_mapint,stringump;// 三种插入方式ump[1]张三;ump.insert({2,李四});ump.insert(make_pair(3,王五));// 下标访问取值coutump[1]endl;// 范围遍历for(autop:ump){coutp.first : p.secondendl;}return0;}查找与删除操作#includeiostream#includeunordered_mapusingnamespacestd;intmain(){unordered_mapint,intump;ump[10]100;ump[20]200;ump[30]300;// 查找key为20的数据autoitump.find(20);if(it!ump.end()){cout找到数据it-secondendl;}else{cout未找到该键endl;}// 删除指定keyump.erase(30);return0;}[]下标访问注意坑点使用[]访问不存在的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依托哈希表实现主打高效增删查改。核心存储形式为键值对键唯一无序查询速度是最大优势。日常刷题、业务开发高频查询场景优先选用该容器。使用时规避下标自动插入的问题根据有序需求选择对应映射容器。