STL:map与unordered_map

张开发
• 2026/4/16 3:38:14 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

STL:map与unordered_map
底层数据结构本质区别map底层是红黑树平衡二叉搜索树特点自动按 key 排序默认升序插入后依然保持有序mapint, int m; m[3] 30; m[1] 10; m[2] 20;输出顺序1 2 3unordered_map底层是哈希表特点无序存储元素位置由 hash 函数决定unordered_mapint, int m; m[3] 30; m[1] 10; m[2] 20;输出顺序不确定2 3 1可能是任何顺序时间复杂度操作mapunordered_map查找O(log n)O(1)平均插入O(log n)O(1)平均删除O(log n)O(1)平均注意unordered_map最坏情况 O(n)哈希冲突严重map始终稳定 O(log n)是否有序容器是否有序map有序unordered_map无序多线程下的性能差异unordered_map 插入查找快但线程安全性差需加锁或使用concurrent_unordered_mapmap插入较慢但访问结构清晰适合在多线程并发读的场景下做共享读锁写锁总之在多线程环境下map 的结构更适合读多写少的场景配合shared_mutex可以实现并发读。而 unordered_map 虽然查找快但并不适合直接并发写操作除非我们通过分桶加锁或者使用像 TBB 提供的 concurrent_unordered_map 这样的专业并发容器unordered_map 发生哈希冲突会怎么处理当 unordered_map 发生哈希冲突时会将多个哈希值相同的元素存入同一个哈希桶中通常通过链表链式地址法或开放寻址法来解决C STL 中一般采用链表方式即发生冲突的元素会插入到该桶对应链表的末尾查找时需要遍历该链表冲突多时会降低查找性能。为什么 unordered_map 最坏情况是 O(n)因为unordered_map 底层是哈希表结构理论上查找和插入都是 O(1)但在最坏情况下所有键的哈希值都一样哈希冲突极端严重所有元素都被插入到同一个桶中退化成了链表结构此时查找、插入、删除都变成了线性查找时间复杂度退化为 O(n)。map 和 unordered_map 的内存占用对比map 由于基于红黑树实现每个节点需要存储指针父节点、左右子节点和颜色位结构更紧凑且稳定而 unordered_map 基于哈希表实现需要额外存储哈希桶数组包含大量空位、链表指针等结构为了降低冲突还要预留扩容空间因此在元素量相同时unordered_map 的内存占用通常比 map 更高但也换来了更快的查找效率平均 O(1)。哈希表的负载因子是啥扩容机制如何哈希表的负载因子Load Factor是元素个数N与桶个数B之比公式为α N / B表示哈希表的“拥挤程度”当负载因子超过某个阈值例如 0.75就会触发扩容机制即重新分配更大的桶数组并对所有元素重新哈希rehash以减少冲突、保持插入和查找的效率但扩容过程代价较大会导致性能瞬时下降。

更多文章