面灵AI→

第四范式 C++ 一面:虚表、智能指针、容器选型与手写哈希表

轮次
一面
时间
2026-11
来源
牛客网

《面试题目》

  1. 封装、继承、多态,你在平台代码里哪一块真正用到了多态?
  2. 虚函数表存在哪?为什么基类析构必须是虚的?
  3. unique_ptr、shared_ptr、weak_ptr 三者到底怎么选?
  4. vector、deque、list、unordered_map 怎么选?迭代器失效的规则能总结一下吗?
  5. struct 里成员的顺序会影响 sizeof 吗?为什么要内存对齐?
  6. 手撕:实现一个简单的哈希表,支持 insert、find、erase。
  7. 追问:冲突除了拉链还能怎么做?负载因子为什么定 0.75?
  8. 多线程同步你常用哪几种?条件变量为什么要配 while 而不是 if?

《参考解析》

多态的真实用法与代价。 存储后端抽象成接口(本地盘、HDFS、S3 三套实现,上层只认 path 与流对象)是典型的多态场景;任务执行器基类定义 run(),训练、评测、导出三种任务派生,调度器只持有基类指针。代价是虚调用每次多几纳秒且无法内联,所以数据面(序列化循环、逐字节处理)通常不用多态,改用模板在编译期分发或 CRTP。回答时最好给出「为什么这里用、那里不用」的判断依据,而不只是背定义。

虚表与虚析构。 虚表是只读数据,通常放在 .rodata 段,每个类一份;对象的 vptr 在构造时写入,指向所属类的虚表。基类析构必须是虚的,因为通过基类指针 delete 时,非虚析构只会调用基类版本,派生类的成员(堆上的 string、vector、句柄)不会被释放,造成泄漏与资源未回收。例外是类标记 final、或析构函数为 protected 且不通过基类指针删除,这时可以省掉虚析构。还要提醒:构造/析构函数里调用虚函数不会呈现多态(构造基类时派生类尚未构造完成),这是常见陷阱。

智能指针选型。 unique_ptr 是默认选择:独占所有权、大小与裸指针相同、零运行时开销、只能移动不能拷贝,适合「明确只有一个持有者」的场景(工厂返回值、成员持有资源)。shared_ptr 用于共享所有权,引用计数在堆上的控制块里、原子增减,拷贝有开销(一次原子操作 + 可能的分配),且要注意循环引用——两个对象互相持有时计数永不归零。weak_ptr 不增加计数,只观察,用来打破循环引用(例如 DAG 节点的父子互指、缓存里保存对象的弱引用),使用前要 lock() 提升为 shared_ptr 并判空。

容器与迭代器失效。 随机访问与遍历优先 vector(连续内存、缓存友好);头尾都插入用 deque;中间频繁插入且元素较大才考虑 list,否则链表指针跳转的成本可能高于搬移。unordered_map 适合频繁查找、不要求顺序;需要有序遍历用 map(红黑树)。失效规则:vector 扩容时全部迭代器、指针、引用失效,不扩容时插入点之后的失效;deque 头尾插入只失效迭代器、引用仍有效,中间插入全失效;关联容器只有被删除节点的迭代器失效。工程建议是跨模块传下标而不是迭代器——缓存层存 vector 迭代器、扩容后全线崩溃是很典型的线上事故。

内存对齐。 成员顺序直接影响 sizeof:char、int、char 在 4 字节对齐下占 12 字节,改成 int、char、char 只占 8 字节。原因是 CPU 按字或 cache line 访存,跨边界访问需要两次访存,某些架构上直接触发总线错误;编译器按成员中最大的对齐要求补齐。优化原则是按对齐要求从大到小排列成员,必要时用 alignas 指定、或把热字段集中到同一个 cache line 以减少伪共享。

手写哈希表与冲突处理。 结构用桶数组 + 链地址法:每个桶挂一个单链表,节点存 key、value、next。insert 先算 hash 取模定位桶,遍历链表查重,不存在则头插;find 同理;erase 要处理头节点与中间节点两种情况(用二级指针或记录前驱)。扩容在负载因子超过阈值时进行:桶数翻倍、所有节点 rehash,单次 O(n) 但均摊 O(1)。析构时要逐桶释放节点,不能只 delete[] 数组,否则整表泄漏。冲突的替代方案是开放寻址:线性探测缓存友好但容易聚集,二次探测或 Robin Hood 更均匀,缺点是删除要打墓碑标记、负载因子不能太高。0.75 是工程折中:拉链法下平均查找长度约 1 + α/2,0.75 时约 1.375 次;再高冲突上升很快,再低则浪费内存。实际系统里 0.7 到 0.8 之间性能差异不大,但超过 1.0 后尾延迟会显著恶化。

条件变量为什么要 while。 wait 存在虚假唤醒(没有通知也可能返回),也可能被多个线程竞争后只有一个真正满足条件。用 if 判断谓词,被唤醒后不再检查就继续执行,会在条件不成立时进入临界区,破坏不变量;while 会在每次唤醒后重新检查谓词,不满足就继续等。配套要注意「丢失唤醒」:必须在持锁状态下修改状态再 notify,否则通知可能发生在等待之前而丢失,导致 worker 永久挂起。