`unordered_map` 详解

1. 基本概念std::unordered_map是基于哈希表的键值容器。#includeunordered_map特性每个键唯一键关联一个值元素不保证顺序平均查找、插入、删除复杂度为 O(1)最坏情况下可能退化为 O(n)。2. 基本用法#includeiostream#includestring#includeunordered_mapintmain(){std::unordered_mapstd::string,intscores;scores[Alice]90;scores.emplace(Bob,85);scores.insert({Carol,95});for(constauto[name,score]:scores){std::coutname: score\n;}}遍历顺序不固定。3. 常用接口map.empty();map.size();map.clear();map.insert({key,value});map.emplace(key,value);map.try_emplace(key,constructor_args...);map.insert_or_assign(key,value);map.find(key);map.contains(key);// C20map.count(key);map.erase(key);map.erase(iterator);map[key];map.at(key);4.operator[]与at()的区别operator[]std::unordered_mapstd::string,intcounts;intvaluecounts[unknown];若键不存在会插入{unknown,0}因此operator[]不适合纯查询场景。at()intvaluecounts.at(camera);若键不存在抛出std::out_of_range。find()autoitcounts.find(camera);if(it!counts.end()){intvalueit-second;}只查询时通常推荐find()或 C20contains()。5. 插入接口区别5.1insert键存在时不覆盖。auto[it,inserted]map.insert({camera,1});5.2emplace原地构造键值对。map.emplace(camera,1);键已存在时参数仍可能已经参与临时对象构造。5.3try_emplace键存在时不构造值对象。map.try_emplace(camera,expensive_constructor_arg);当值对象构造昂贵时更合适。5.4insert_or_assign键不存在则插入存在则覆盖值。map.insert_or_assign(camera,2);5.5operator[]适合计数和确保键存在。word_count[word];6. 典型计数场景#includestring#includeunordered_map#includevectorstd::unordered_mapstd::string,intcountWords(conststd::vectorstd::stringwords){std::unordered_mapstd::string,intcounts;counts.reserve(words.size());for(constautoword:words){counts[word];}returncounts;}7. 哈希表基础unordered_map通常包含桶数组根据哈希值分配到桶中的节点桶内冲突处理结构。查找过程通常是计算键的哈希值根据桶数量定位桶在桶内使用相等比较器寻找目标键。8. 装载因子与扩容std::unordered_mapint,std::stringdevices;devices.reserve(1000);devices.max_load_factor(0.75f);常用状态devices.bucket_count();devices.load_factor();devices.max_load_factor();装载因子定义load_factor size / bucket_count当元素数量增大到一定程度容器会 rehash增加桶数量重新分配所有元素到新桶使迭代器失效产生一次较明显的性能开销。提前调用reserve()可以减少扩容次数。9. 自定义键类型#includefunctional#includestring#includeunordered_mapstructSensorKey{intdevice_id;intchannel;booloperator(constSensorKeyother)const{returndevice_idother.device_idchannelother.channel;}};structSensorKeyHash{std::size_toperator()(constSensorKeykey)const{std::size_t h1std::hashint{}(key.device_id);std::size_t h2std::hashint{}(key.channel);returnh1^(h21);}};std::unordered_mapSensorKey,std::string,SensorKeyHashsensors;必须满足若 key1 key2则 hash(key1) hash(key2)10. 组合哈希函数简单组合std::size_tcombineHash(std::size_t seed,std::size_t value){seed^value0x9e3779b9(seed6)(seed2);returnseed;}使用structPointHash{std::size_toperator()(constPointp)const{std::size_t seed0;seedcombineHash(seed,std::hashint{}(p.x));seedcombineHash(seed,std::hashint{}(p.y));returnseed;}};哈希组合需要兼顾分布均匀计算速度与相等规则一致对输入模式不敏感。11. 值类型为复杂对象structDeviceState{intstatus;std::string message;};std::unordered_mapint,DeviceStatestates;states.try_emplace(1001,DeviceState{1,online});通过结构化绑定遍历for(auto[id,state]:states){state.status0;}只读遍历for(constauto[id,state]:states){}12. 值类型为智能指针#includememorystd::unordered_mapint,std::unique_ptrDevicedevices;devices.emplace(1,std::make_uniqueDevice());这可以清晰表达容器拥有对象元素删除时对象自动析构避免手动delete。13. 迭代器失效规则插入未触发 rehash 时已有迭代器通常保持有效触发 rehash 后所有迭代器失效。删除指向被删除元素的迭代器、指针、引用失效其他元素通常不受影响。reserve和rehash可能使所有迭代器失效。不要在遍历时无条件插入大量新键除非已提前reserve()或正确处理迭代器失效。14. 遍历中安全删除for(autoitmap.begin();it!map.end();){if(shouldErase(it-first,it-second)){itmap.erase(it);}else{it;}}C20std::erase_if(map,[](constautoitem){returnitem.second.expired();});15. 与map的区别对比项unordered_mapmap底层结构哈希表平衡搜索树元素顺序无序按键有序平均查找O(1)O(log n)最坏查找O(n)O(log n)范围查询不支持支持哈希函数需要不需要比较器相等比较顺序比较迭代顺序不稳定稳定有序内存特点桶数组和节点树节点指针16. 常见应用字符串词频统计ID 到对象映射缓存配置项查询状态表图的邻接表去重并附加属性消息类型到处理函数映射稀疏数据索引。处理函数映射#includefunctional#includeunordered_mapusingHandlerstd::functionvoid();std::unordered_mapint,Handlerhandlers;handlers.emplace(1,[]{// process type 1});17. 性能优化建议已知规模时调用reserve()。设计分布良好的哈希函数。避免在热点路径反复构造临时字符串键。对字符串可考虑异构查找。复杂值类型优先使用try_emplace()。更新已有值可使用insert_or_assign()。不依赖遍历顺序。对强实时、极端最坏复杂度敏感的场景评估map或专用哈希容器。小数据集先进行基准测试vector线性查找可能更快。不要通过过低的max_load_factor盲目换取速度以免内存显著增加。18. 常见错误18.1 查询时意外插入if(map[key]1){}若键不存在会创建新元素。推荐autoitmap.find(key);if(it!map.end()it-second1){}18.2 修改键键在容器中视为const不能直接修改否则会破坏哈希结构。需要修改键时删除旧键插入新键或使用 C17 节点句柄。autonodemap.extract(old_key);if(!node.empty()){node.key()new_key;map.insert(std::move(node));}18.3 假设哈希冲突不会发生哈希值相同不代表键相等。容器仍需调用相等比较器。18.4 暴露不稳定顺序序列化、测试和日志如果要求确定顺序应先排序键或使用map。19. 面试总结unordered_map是哈希键值容器平均查找、插入和删除复杂度为 O(1)但不保证遍历顺序最坏情况可能退化为 O(n)。其性能受哈希函数、桶数量和装载因子影响。使用时应注意operator[]会在键不存在时插入默认值提前知道规模时可调用reserve()复杂值构造建议使用try_emplace()。