图详解（DFS、BFS、最短路径）
图由顶点和边组成，可有向或无向、带权或无权。邻接矩阵占 O(V²)，判断两点是否有边很直接；邻接表占 O(V+E)，更适合稀疏图。选表示方式前应看图的密度以及遍历边和查询边哪个更频繁。 DFS 用栈深入路径，适合连通块、环检测和路径枚举；BFS 用队列按层展开，在无权图中首次到达某点即得到最少边数。两者都必须维护访问状态，邻接表下时间为 O(V+E)。有向无环图可用入度为零的队列执行拓扑排序；若最终处理节点少于 V，说明存在环。 带权最短路要依据边权选择。Dijkstra 反复确定当前距离最小的未定节点，并松弛出边，适合非负权；优先队列实现常为 O((V+E)log V)。存在负权边可用 Bellman-Ford，它多轮松弛所有边，并能检测可达负环，但成本约 O(VE)。所有点对问题则另有 Floyd 等方法。 123456dist[start]=0; push(start,0)while heap not empty: (d,u)=popMin() if d != dist[u]: continue for (u,v,w): if d+w < dist[v...
布隆过滤器详解（原理、实现、应用场景）
布隆过滤器是一种概率型集合，用很小空间回答“某元素是否可能存在”。它由长度为 m 的位图和 k 个哈希位置组成。插入时把对应位设为 1；查询时检查这些位，只要有一位为 0，就能确定元素不存在；全部为 1，只能说可能存在。 误判来自不同元素共享位：从未插入的元素也可能碰巧命中所有 1。标准布隆过滤器不会假阴性，前提是位图未被错误清除、哈希规则一致。随着元素增加，1 的比例升高，误判率随之上升；容量规划要结合预计元素数 n 与可接受误判率选择 m 和 k，而不是任意开一块位图。 123456add(x): for each hash h: bits[h(x) mod m] = 1contains(x): for each hash h: if bits[h(x) mod m] == 0: return false return true 单次插入和查询为 O(k)，位图空间 O(m)，通常把 k 视为小常数。普通版本不能安全删除，因为清掉共享位会让其他元素产生假阴性；需要删除时可使用计数布隆过滤器，但每个位置存计数会增加空间并需处理溢出。 它适合缓存穿透防护、爬虫 ...
数据结构知识体系：数组、链表、哈希表、树、图、堆与面试
数据结构是数据的组织方式，也是对操作成本的取舍。数组连续存储，随机访问 O(1)，中间移动昂贵；链表靠指针连接，已知节点附近插删方便，却不能常数时间按下标定位。栈和队列限制访问端点，从而清晰表达后进先出与先进先出。 哈希表把键映射到桶，平均查找 O(1)，代价是额外空间、冲突处理和无序性。树表达层级：二叉搜索树支持按序查找，平衡树控制高度，B+ 树适合外存范围访问；堆只维护父子偏序，能以 O(log n) 插入删除并快速读取极值。图用于一般关系，邻接表节省稀疏图空间，邻接矩阵则让边查询简单。 选择结构前应列出工作负载：读多还是写多，按键还是按序访问，是否需要范围查询、极值、前缀、连通性，数据能否全部驻留内存。例如缓存淘汰常组合哈希表和双向链表，使定位与移动都为 O(1)；前缀检索可用 Trie；动态连通可用并查集。 复杂度不是单个 API 标签。动态数组追加是摊还 O(1)，扩容那一次仍要复制；哈希表平均常数不等于最坏常数；普通搜索树可能退化成链表。还要考虑缓存局部性、对象开销、并发和持久化。 误区是认为结构越高级越好，或只背复杂度而忽略前提。小结：先描述需要高频执行的操作和...
线性数据结构详解（数组、链表、栈、队列）
线性结构中的元素具有前后次序，但实现方式不同。数组连续存储，可通过地址偏移 O(1) 访问下标，缓存局部性好；中间插删通常要移动元素，为 O(n)。动态数组容量不足时申请更大空间并复制，追加因此是摊还 O(1)。 链表把节点分散存放并用指针连接。已知插入位置的前驱时，插删可为 O(1)，但查找第 i 个元素需顺序走 O(n)。双向链表多一个前驱指针，便于从节点本身删除和双向遍历，代价是更多空间与连接维护。 栈限制在同一端压入弹出，体现后进先出，适合函数调用、括号匹配、撤销和 DFS。队列从尾部加入、头部移除，体现先进先出，适合任务缓冲与 BFS。循环队列用固定数组和首尾索引复用空间，需要明确“空”和“满”的区分规则；双端队列允许两端操作，可实现滑动窗口。 这些结构的端点操作通常 O(1)，但基于数组的队列若每次删除首元素都整体搬移，就会退化；实践中应使用环形索引。链式实现无需整体扩容，却有节点对象和指针开销。 误区是说链表插入永远 O(1) 而忽略定位成本、用普通数组首删模拟队列、混淆栈顶和队尾，以及忽略迭代时修改结构的规则。小结：数组优化定位与局部性，链表优化已知位置连接，...
零拷贝详解：mmap、sendfile 与 splice
传统文件发送常先把磁盘数据读入内核页缓存，再复制到用户缓冲，随后写回 Socket 缓冲，最后由设备传输。零拷贝不是承诺完全没有物理搬运，而是尽量避免 CPU 在用户态与内核态之间复制同一批数据。 mmap 把文件页映射到进程地址空间，应用可直接访问页缓存，省去 read 到用户缓冲的一次复制，但首次访问可能缺页，映射生命周期、截断和一致性需要谨慎处理。sendfile 让内核直接把文件描述符的数据送往 Socket，适合应用不需要修改内容的静态传输。支持页引用或 DMA 聚合时，还可进一步减少内核缓冲间复制。 splice 在支持的文件描述符之间借助管道移动或引用页，适合构建内核内数据通路。不同操作系统、文件系统、设备与加密路径支持程度不同；TLS 若在用户态处理，数据仍可能需要进入用户空间，内核 TLS 或硬件卸载则是另一套权衡。 收益取决于数据大小和是否需要变换。小数据可能被系统调用与映射管理开销抵消；压缩、解析、加密或修改内容时，用户态缓冲仍有必要。评估应测 CPU 使用、吞吐、延迟和上下文切换，而非只数理论复制次数。 误区是把零拷贝理解为磁盘到网卡没有任何复制、认为...
I/O 多路复用详解：select、poll、epoll 原理与区别
I/O 多路复用让一个线程等待多个文件描述符的就绪事件。它没有让一次读写变快，而是避免为每个连接都安排一个阻塞线程，适合连接多、单连接事件稀疏的网络服务。 select 每次传入描述符集合，返回后应用扫描集合找就绪项，集合大小受实现限制且需反复复制；poll 用数组描述事件，去掉固定编号上限，但仍要线性扫描。Linux epoll 把关注集合注册在内核，等待时主要返回已就绪事件，避免每轮重传完整集合，更适合大量连接。 事件触发有两种语义。水平触发只要仍可读写就会继续通知，容易编写；边缘触发只在状态变化时提醒，应用通常必须把非阻塞描述符循环读到 EAGAIN，否则剩余数据可能长时间得不到新通知。就绪不等于业务消息完整，TCP 仍是字节流，需要应用层处理半包与粘连。 从接口观察，select/poll 每轮工作与监控数量相关，epoll 等待返回成本更接近就绪数量，但注册、回调、内核实现与场景都会影响实际性能，小规模下差异未必重要。 误区是把 epoll 说成完全 O(1)、认为就绪后读写绝不阻塞、边缘触发只读一次、关闭描述符后仍复用旧事件，以及把多路复用等同异步 I&...
操作系统常见面试题总结（下）
虚拟内存为每个进程提供独立地址空间。页表完成虚拟页到物理页映射，TLB 缓存近期转换；缺页可能是正常的按需分配，也可能需要磁盘 I/O。页面置换在内存压力下选择回收对象，频繁换入换出会造成抖动。 文件系统中，目录把名字映射到 inode，inode 保存元数据和数据位置。文件描述符是进程打开文件表的索引，不是文件本身。Page Cache 加速读写，write 返回通常只说明数据进入内核缓冲；需要持久化保证时必须理解同步写和 fsync 的边界。 I/O 可分阻塞与非阻塞、同步与异步，这两组概念维度不同。多路复用让线程等待多个描述符就绪，事件到来后仍由应用执行读写；异步 I/O 则关注操作完成通知。零拷贝减少用户态与内核态之间不必要搬运，但不意味着物理层完全没有复制。 性能题应从资源队列出发：CPU 高看热点与运行队列，load 高而 CPU 低看 I/O 或不可中断等待，内存压力看回收和 Swap，磁盘看延迟与队列，网络看丢包、重传和连接状态。单个指标不能直接给根因。 误区是把空闲内存少判为泄漏、认为删除文件立即释放、把 epoll ...
虚拟内存详解：地址转换、TLB、缺页异常与页面置换
虚拟内存让每个进程看到独立连续的地址空间，实际物理页可以分散、共享或暂未分配。地址由虚拟页号和页内偏移组成，页表把页号翻译成物理页框，偏移保持不变，并同时检查读写执行权限。 多级页表只为使用到的地址范围分配下级结构，节省稀疏空间；TLB 缓存近期页表项，命中时避免多次内存访问。上下文切换可能影响 TLB，但地址空间标识等机制可减少完全刷新。 当页表项不在内存时产生缺页异常。内核先判断地址是否合法：若合法，可分配零页、从映射文件读取，或从 Swap 换入；必要时选择受害页，脏页先写回，再更新页表和 TLB，最后重新执行原指令。轻微缺页不需磁盘，重大缺页通常涉及 I/O，代价差异很大。 页面置换希望保留近期仍会访问的工作集。理想 LRU 难以精确实现，系统常用访问位与近似链表。若活跃工作集持续超过物理内存，频繁换页形成抖动，此时增加 Swap 只会延缓失败，未必改善吞吐。 页大小影响页表、TLB 覆盖和内部碎片；大页可减少 TLB 压力，但分配回收更粗。误区是认为虚拟内存等于 Swap、每次地址转换都查磁盘、缺页必然异常退出，以及进程地址空间大小等于驻留内存。小结：虚拟...
操作系统锁与同步机制详解：mutex、semaphore、condition variable、spinlock 与 futex
同步的目标是让并发访问满足不变量。互斥量保证同一时刻只有一个执行者进入临界区，适合保护共享结构；信号量维护许可计数，可限制并发资源数量，也可表达事件，但所有权语义通常弱于互斥量。 条件变量用于等待某个共享状态成立。正确模式是在持有互斥锁时用 while 检查谓词，不满足则等待；等待操作原子地释放锁并睡眠，唤醒后重新加锁、再次检查。使用 if 会受虚假唤醒或其他线程抢先消费影响。 自旋锁在等待时持续检查，不发生睡眠切换，适合临界区极短且预期等待很少的场景；持锁者被抢占或临界区含 I/O 时，自旋会浪费 CPU。futex 的思路是无竞争时在用户态用原子操作完成，发生竞争时才进入内核睡眠与唤醒，许多用户态锁基于此构建。 读写锁允许多个读者并行、写者独占，只有读多写少且临界区足够大时才可能获益，还需关注读者或写者饥饿。任何锁都要控制粒度：过大降低并行，过细增加复杂度和死锁风险。 误区是认为原子变量能自动保护多步不变量、条件变量本身保存事件、用自旋锁等待长任务、持锁调用未知回调，以及漏用 finally 释放。小结：先写共享谓词和所有权，再选择等待策略；锁是维护不变量的手段...
操作系统内存管理详解：分页、分段、页面置换、Swap 与 OOM
内存管理为进程提供独立、连续的虚拟地址视图，并把它映射到有限物理内存。分页把虚拟与物理空间切成固定大小的页，通过页表记录映射和权限；分段更贴近代码、数据、栈等逻辑区域，但可产生外部碎片。 CPU 访问虚拟地址时拆出虚拟页号和页内偏移，先查 TLB 缓存的页表项，未命中再走多级页表。页表项不存在可能触发缺页：匿名页可按需分配，文件页可从文件读取，换出页需从 Swap 调回。若地址不合法或权限不符，则向进程报告错误。 物理页紧张时，系统回收干净文件页或写回脏页，也可能把匿名页换出。页面置换理论上有 FIFO、LRU、Clock 等策略，实际系统会结合访问位、活跃链表和工作集近似。抖动发生在工作集超过可用内存时，系统频繁换页却很少做有效计算。 申请虚拟内存成功不代表物理页已立即准备，也不代表未来不会 OOM。Linux 还会利用剩余内存做页缓存，因而“空闲少”不必然异常。诊断应看可用内存、回收、缺页、Swap 活动和进程驻留集。 误区是把虚拟地址等同物理地址、认为缺页都是故障、把 Swap 当内存扩容的等价替代、看到缓存就清理，以及只按平均内存容量规划。小结：分页提供隔离与按需分配...