面经

select/poll/epoll ，常见的有哪些输入事件?
- 针对 epoll，常见的有：读事件（EPOLLIN）、写事件（EPOLLPUT）、异常事件（EPOLLPRI）
环形缓冲区 解决了哪些问题？
- 环形缓冲区 通过 首尾相接 的方式，让读写指针循环移动，在 固定大小内存 里反复利用空间，这样可以减少数据搬移、减少频繁内存申请释放的开销。
编程常用的数据结构（数组 vector、链表 list、红黑树 map、哈希表 unordered_map）
链表环的检测方法？（快慢指针）
如何解决哈希冲突？
- 链地址法： 把哈希表的每个桶设计成一个链表，发生冲突时，就把元素挂到同一个桶后面。
- 开放定址法： 冲突后，不用链表，而是继续在表里找别的空位置存放。
  - 线性探测： 冲突了就往后 一个一个 找；
  - 二次探测： 冲突后按 平方步长 去找：
- rehash： 冲突太多，往往说明 表太小了。
  - 这时通常会 申请更大的哈希表把原来的元素重新哈希后搬过去
常见排序算法？（快排、归并、堆排序）
map 的底层数据结构（红黑树）
红黑树和二叉搜索树的区别？
- 二叉搜索树（BST）：只要求左小右大；
- 红黑树（RBT）：除了左小右大，还要求满足一系列颜色和平衡规则；
  - 每个节点是红色或黑色；
  - 根节点是黑色；
  - 所有叶子空节点 NIL 都是黑色；
  - 红色节点的孩子必须是黑色；
  - 从任意节点到其所有后代叶子节点的路径上，黑色节点数相同；
cpp 面向对象的思想体现在哪里？（C++ 面向对象思想主要体现在：用类和对象建模，用封装隐藏细节，用继承复用代码，用多态统一接口，用抽象提炼本质）
多态底层实现？（vptr + vtable）
vtable 的底层数据结构？（vtable 通常就是一块 只读静态内存区域 中的 函数指针数组）
tcp 和 udp 的区别？
- tcp 是面向连接的、可靠的、面向字节流的传输层协议；
- udp 是无连接的、不可靠的、面向数据报的传输层协议；
tcp服务端客户端绑定的是同一个端口吗？
- TCP 连接里，客户端和服务端一般不是绑定同一个端口，而是靠一个 四元组 来唯一标识一条连接
- 服务端通常绑定固定监听端口；
- 客户端一般使用操作系统分配的临时端口去连接服务端；
cpp 智能指针？（unique_ptr、shared_ptr、weak_ptr）
如何解决数据竞争？（1. 加锁保护临界区；2. 用原子操作；3. 减少共享，改成线程私有）
cpp 学习过程中的难点？（对计算机系统架构要非常了解）
服务端和客户端连接过程？
- 应用层：
  - 服务端： 创建 socket、绑定地址 bind、监听连接 listen、从完成队列中取出连接 accept
  - 客户端： 创建 socket、绑定地址 bind、连接服务器 connect
- 传输层：
  - 第一次握手： 客户端发送连接建立报文，同步位 SYN = 1，初始化序号 seq = x；
  - 第二次握手： 服务端发送确认报文，同步位 SYN = 1，确认位 ACK = 1，初始化序号 seq = y，确认号 ack = x + 1；
  - 第三次握手： 客户端发送连接确认报文，确认位 ACK = 1，初始化序号 seq = x + 1，确认号 ack = y + 1；
- 内核层：
  - 服务端： 内核会为监听 socket 维护队列
    - 半连接队列： 收到客户端 SYN，回复 SYN + ACK，但还没收到最后 ACK 的连接先放这里；
    - 全连接队列： 三次握手完成的连接放这里，等应用调用 accept() 取走；
操作系统如何解决碎片问题？（分段、分页、段页式）
系统分页/页表机制？
手撕 LRU