1.set是什么set的底层是红黑树一种平衡搜索二叉树树形结构而且只有key没有value,也就是说set只能做key在不在这种场景比如说在机场对乘客是不是黑名单中的一员进行查找的时候就可以用到set,进行查找对应的身份证号是否存在不需要知道这个身份证号对应的姓名是什么也就是说不需要value这也是set和map的区别2.set和红黑树的关系set是容器而红黑树是set的底层逻辑是一种数据结构set对红黑树的底层逻辑做了封装提供了我们使用的上层接口3.set的特点① 红黑树天生自动维护顺序所以 set 里的元素永远是排好序的。② set可以进行去重也就是说set中没有重复的元素这是因为set这个容器在进行插入数据的时候会进行判断将重复的元素进行去除std::set的设计目标是集合set数学上集合的定义就是不重复元素的无序聚集。这也是set和list的区别之一4.unordered_set是什么unordered的意思是无序的所以unordered_set的意思就是无序集合底层使用的是哈希表为什么unordered底层使用的是hash表而不是红黑树呢因为业务需求不同set需要有序红黑树天然有序unordered_set只需要快速哈希表天然最快。这是根据要什么选用什么的经典案例。5.hash是怎么将元素放到对应的桶中的步骤操作具体做了什么第 1 步计算哈希值调用std::hashKey()(x)得到一个size_t类型的整数比如123456789第 2 步计算桶号索引用哈希值对桶数量取模bucket_index hash_value % bucket_count()得到要去的桶的编号比如5号桶第 3 步查重遍历桶内链表去对应的桶遍历桶里的链表用operator逐一比较所有元素。如果有相等的插入失败直接返回第 4 步检查是否需要扩容如果没找到重复检查当前元素个数是否超过bucket_count * max_load_factor默认 1.0。如果超过了触发 Rehash扩容重新分配更大的桶数组所有旧元素重新计算桶号并搬过去第 5 步插入元素把新元素挂在对应桶的链表头部或尾部元素个数sizevoid unordered_set::insert(int x) { // 第 1 步算哈希 size_t hash_val hash_function(x); // 第 2 步算桶号 size_t bucket_index hash_val % bucket_count; // 第 3 步查重 Node* cur buckets[bucket_index]; while (cur ! nullptr) { if (cur-value x) { // 用 operator 比较 return; // 重复了拒绝插入 } cur cur-next; } // 第 4 步检查负载因子 if (size bucket_count * max_load_factor) { rehash(bucket_count * 2); // 扩容翻倍全部重新哈希 bucket_index hash_val % bucket_count; // 重新计算桶号 } // 第 5 步插入 Node* new_node new Node(x); new_node-next buckets[bucket_index]; buckets[bucket_index] new_node; size; }① rehash的什么时候进行扩容rehash的时间复杂度是O(n),而因为负载因子是1意思就是当元素个数和桶的数量相同的时候需要进行扩容② 为什么要重新计算hash值因为并不是所有数据都是整数能让你直接取模哈希值存在的核心目的就是把乱七八糟的任何东西统一转化成整数这样计算机才能处理。场景 1如果原始值是字符串std::unordered_setstd::string mySet; mySet.insert(hello); mySet.insert(world);问题来了你没法对字符串取模hello % 13; // ❌ 编译报错C 不支持对字符串取模你必须先把字符串转成一个整数然后才能取模。这个转成整数的过程就是哈希函数做的事。场景 2如果原始值是自定义对象struct Person { std::string name; int age; }; std::unordered_setPerson mySet; // 编译报错没有哈希函数问题Person不是整数不能直接取模。你必须告诉 C 怎么把Person转成整数这就是自定义哈希函数struct PersonHash { size_t operator()(const Person p) const { return std::hashstring()(p.name) ^ std::hashint()(p.age); } };6.set和unordered_set的区别是什么值得注意的是set和unordered_set都是去重的对比维度std::setstd::unordered_set底层数据结构红黑树自平衡二叉搜索树哈希表数组 链表元素顺序自动升序排序完全无序不保证任何顺序查找时间复杂度O(log n)O(1) 平均最坏 O(n)插入时间复杂度O(log n)O(1) 平均最坏 O(n)删除时间复杂度O(log n)O(1) 平均最坏 O(n)迭代器稳定性✅ 插入/删除时已有迭代器不失效❌ 扩容Rehash时所有迭代器失效是否支持范围查询✅ 支持lower_bound/upper_bound❌ 不支持内存开销每个节点额外存 3 个指针父、左、右 颜色位约 32 字节桶数组预分配空桶也占内存 链表节点指针自定义类型要求必须重载operator必须特化std::hash 重载operator适用场景需要排序、范围查询、迭代器长期持有只关心快速增删查改不关心顺序实际开发使用频率较少特定场景极高绝大多数场景首选为什么set的查找、插入、删除的时间复杂度是Ologn,而unordered_set的时间复杂度是O(1)这是因为set是需要排序的而unordered_set是不需要排序所以查找效率最高为什么unordered_set的时间复杂度最坏情况是O(N)?因为unordered_set是hash,而哈希函数可能把所有元素都映射到同一个桶Bucket里导致查找时退化成遍历链表复杂度从 O(1) 变成 O(n)。7.什么是mapmap 是一种容器存的是键值对Key-Value通过 Key 快速查找对应的 Value。就像通讯录输入名字Key查到手机号Value。set的名字叫做集合map叫做映射。map和set一样map的底层使用也是红黑树也是有序的map和set的区别是map从set的单个元素变成了键值对map是按照key排序。8.map在面试中常有的面试问题①map和set的区别是什么set只存key只关心元素在不在而map存了key和value的键值对可以通过key查找value;②map和unordered_map的区别对比维度std::mapstd::unordered_map底层红黑树哈希表顺序按 Key 自动排序完全无序查找O(log n)O(1) 平均最坏 O(n)迭代器稳定性插入不失效扩容时失效适用场景需要排序、范围查询只关心快速查找③map 的 [] 操作符和 insert 有什么区别操作行为返回值map[key] valueKey 不存在则插入Key 存在则覆盖Value返回 Value 的引用map.insert({key, value})Key 不存在则插入Key 存在则什么都不做返回pairiterator, boolbool表示是否插入成功[]操作符有个陷阱即使你只是读取map[不存在]它也会自动插入一个默认构造的 Value这可能不是你想要的。所以查找时建议用find()而不是[];// 错误方式 if (map[key] value) { ... } // 如果 key 不存在会插入一个空值 // 正确方式 auto it map.find(key); if (it ! map.end() it-second value) { ... }④map 的迭代器会失效吗什么时候失效容器插入操作删除操作std::map✅不失效红黑树链式结构✅只失效被删除的那个迭代器std::unordered_map❌可能失效触发 Rehash 时全部失效✅只失效被删除的那个迭代器正确的处理方法// 正确先获取下一个迭代器再删除 for (auto it myMap.begin(); it ! myMap.end(); ) { if (it-second 0) { it myMap.erase(it); // C11 后 erase 返回下一个迭代器 } else { it; } }⑤map 的 Value 可以是任意类型吗可以Value 可以是任意类型int、string、vector、甚至另一个map或自定义类。因为 Map 的排序和查找只依赖KeyValue 只是跟着 Key 走的附加数据不参与任何比较操作所以没有任何限制。⑥map 和 unordered_map 怎么选场景推荐原因需要 Key 有序如排行榜、范围查询std::map红黑树天然有序数据量小 100 个都可以差别不大-数据量大且只做查找std::unordered_map快得多需要迭代器长期持有std::map插入不失效担心哈希攻击std::map红黑树复杂度稳定 O(log n)⑦为什么std::map的 Key 不能修改因为修改 Key 会破坏红黑树的有序结构。如果允许修改树可能不再满足左 根 右的规则导致查找和遍历结果错误。正确做法是先删除修改完再插入。// 错误禁止 auto it myMap.find(张三); it-first 张四; // ❌ 编译报错Key 是 const // 正确 auto it myMap.find(张三); int age it-second; myMap.erase(it); myMap[张四] age; // 重新插入⑧multimap 和 map 的区别multimap允许重复 Key即一个 Key 可以对应多个 Value。使用时注意multimap不支持[]操作符因为不知道你要访问的是哪一个 Value。std::multimapstd::string, int scores; scores.insert({张三, 90}); scores.insert({张三, 95}); // 允许现在 张三 有两个成绩 // 遍历所有 张三 的成绩 auto range scores.equal_range(张三); for (auto it range.first; it ! range.second; it) { cout it-second ; // 输出90 95 }9.map和set的常用接口操作Setstd::setintMapstd::mapstring, int插入insert(x)insert({key, value})或map[key] value查找find(x)find(key)删除erase(x)或erase(it)erase(key)或erase(it)获取大小size()size()判空empty()empty()清空clear()clear()遍历for (auto x : s)for (auto p : m)p.first是 Keyp.second是 Value检查存在count(x)返回 0 或 1count(key)返回 0 或 1获取元素❌ 没有map[key]或map.at(key)