关于map和unordered_map的相关知识。

map和unordered_map的底层数据结构

map

map的底层数据结构是使用红黑树来实现的。主要是一种多路自平衡搜索树。

特征有：

• 平衡的规则，平衡黑节点的高度
• 通过比较key的大小来保持有序
• 通过key来区分不同节点
• O(1)复杂度拿到最小和最大的节点

unordered_map

unordered_map的底层数据结构是使用散列表来实现的。主要是一个指针数组。

特征有：

• 所有的key都会经过hash运算，来定义数组所在的位置
• 通过key是否相等来区分不同的节点
• 当存储的数据多于 负载因子（used实际存储元素的个数 / size数组长度）默认为 0.7 时，就会进行扩容
• 默认没有缩容，但可以自己实现

关于 map和unordered_map的常见面试题

底层采用红黑树的容器有哪些？

主要有 map、set、multimap、multiset

底层采用散列表的容器有哪些？

同理，主要有 unordered_map、unordered_set、unordered_multimap、unordered_multiset

AVL树与红黑树之间的区别

主要区别有：

左右子树高度差不同

AVL树的左右子树高度差最大为1；

红黑树的左右子树的黑节点高度相同。

平衡代价不同

AVL树提供更严格的平衡，查找性能更优，提供O(log_2{n})也就是二分查找的搜索时间复杂度；

红黑树较小的平衡代价，插入和删除的效率更高。

故而，
插入和删除操作较为频繁，使用红黑树；
查询操作较为频繁，使用AVL树，能够提供更稳定的查询性能。

unordered_map是否有缩容的操作

负载因子超过阈值，有扩容操作，但是不会自动缩容减少内存使用。

但是提供了接口，可以组装实现：

• bucket_count() 哈希桶的个数
• load_factor() 获取当前的负载因子
• rehash(n) 将哈希桶个数设置为n，并执行rehash操作
• reserve(n) 分配容纳n个元素的适当桶数 并rehash

缩容的代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

template<typename Key, typename Value>
class CustomUnoderedMap{
 public:
    void erase(const Key& key){
      map.erase(key);
      checkShrink();
    }

 private:
    std::unordered_map<Key, Value> map;
    // 检查是否需要缩容
    void checkShrink(){
      if (map.bucket_count() > 1 && map.load_factor() < 0.1){
        map.reserve(map.size()); // 底层调用了rehash
      }
    }
};

unordered_map的性能优化

主要有：

• 预估元素并设置桶的数量
• 合适的哈希函数，避免大量冲突
• 合适的负载因子 max_load_factor

map和unordered_map的区别

时间复杂度

map：O(log_2{n})
unordered_map：平均O(1)，最差O(n)

内存使用

map：由于底层是红黑树，故而基本没有空间的浪费
unordered_map：提前需要分配数组，故而可能会存在空间浪费

适用场景

map：需要有序，并要范围查询，例如定时器等
unordered_map：不需要有序，更多是单点查询，如用户登录数据

key为字符串，且不区分大小，map和unordered_map分别需要怎么处理

map中，我需要去重新实现key比较的逻辑，因为在map中，我需要根据key的大小来区别不同的节点，故而需要重载大小运算符。
unordered_map中，我需要重载哈希函数和相等比较函数

key作为结构体或类对象，map和unordered_map分别需要怎么处理

与上同理