Dai Wei

哈希表把任意类型的键映射到数组下标，用空间换时间，把查询、插入、删除的平均成本压到常数级。它的全部设计难点集中在三件事上：哈希函数怎么设计、冲突来了怎么安放、表快满了怎么扩。 它解决什么问题「按 key 快速找到 value」是编程中最高频的需求之一：缓存索引、频率统计、去重、分片路由，背后都是它。顺序表查找要 O(n)，有序数组二分是 O(log n)，而哈希表借助「键 → 整数 → 下标」的映射，理想情况下一次定位。代价有两条：一是键空间远大于数组，不同键挤进同一个桶的冲突在数学上不可避免；二是它只回答「在不在、值是多少」，不维护任何顺序关系。 可以把哈希表拆成三层理解：数组负责存放数据，每个槽位叫桶；哈希函数负责把键变成整数；冲突策略决定多个键落到同一桶时如何安置。三层中任何一层设计失衡，性能都会从常数掉到线性。 核心原理好的哈希函数要同时满足三条要求。第一是确定性：同一个键在任何时刻算出的哈希值必须一致，否则放进去就再也找不到。第二是计算快：通常是移位、乘法、异或的组合，如果哈希计算本身很重，就抵消了哈希表的速度优势。第三是分布均匀：输出要尽可能铺满值域，理想状态是雪...

图是描述”多对多关系”的通用模型：社交网络、依赖管理、路由寻址的背后都是它。本文从存储结构讲起，理清 DFS/BFS 遍历、拓扑排序与最短路算法族各自的适用边界。 它解决什么问题线性结构表达一对一，树表达一对多，而现实世界的关系往往是任意的多对多：用户之间的好友关系、构件之间的依赖关系、城市之间的航线。图把对象抽象为顶点集合 V、把关系抽象为边集合 E，记作 G(V, E)，再按边是否有方向、是否带权，细分出有向图、无向图、带权图等变体。建模时方向与权重定错，后面的算法再精妙也只会得到错误答案。 核心原理存储：邻接矩阵与邻接表的权衡邻接矩阵用 V×V 的二维数组记录边，matrix[i][j] 直接给出 i 到 j 的边或权值：判断任意两点是否相邻是 O(1)，但空间恒为 O(V²)，稀疏图里绝大多数格子在空转；无向图的矩阵天然对称。邻接表为每个顶点维护一条邻居列表，空间 O(V+E)，枚举一个顶点的所有邻居只花与其度数成正比的时间，是稀疏图和算法题的默认选择。选择依据就两条：边的密度（E 与 V² 的比值），以及操作画像——“频繁查任意点对之间有没有边”选矩阵，”...

布隆过滤器用一块位数组加 k 个哈希函数，以极小的空间回答「某个元素是否可能存在」：它说不在就一定不在，它说在则有小概率是误判。这个不对称的特性，决定了它适合做「快速排除」，而不是「保存事实」。 它解决什么问题海量集合的存在性判断是个经典难题：亿级 URL 爬虫去重、千万级黑名单过滤，如果把原始数据全塞进哈希集合，内存先被压垮。布隆过滤器给出的交易是——不存元素本身，只存它的「指纹」，用可控的误判率换取数量级的空间压缩。它适配的业务画像是：宁可小概率误杀（把不在的说成在），绝不能漏判（把在的说成不在）。 核心原理结构只有两部分：长度为 m 的位数组（初始化全 0），以及 k 个相互独立的哈希函数。 插入 x：计算 k 个哈希值，把对应的 k 个位置置为 1。 查询 x：检查同样的 k 个位置。只要有一位是 0，x 一定没被插入过；全部为 1，只能说「可能存在」。 误判的来源很直观：位是被所有元素共享的，别的元素的哈希位置恰好把你要查的 k 个位置全部点亮，一个从未插入的元素就会被误报为存在。反过来，已插入元素的 k 个位在插入那一刻就全是 1，只要没有人乱清位，它永远查得...

本专栏覆盖数组、链表、哈希表、树、堆、图以及 Trie、跳表、红黑树、LRU 等进阶结构。这一篇是学习地图：先把主题按解决的问题分组，再理清依赖关系与推荐顺序，最后用一句话索引告诉你每个结构到底解决什么问题。 主题分组按”解决的问题类型”，全部主题可以分成四组。 基础线性组：数组、链表、栈、队列。回答”元素在内存里怎么摆、按什么秩序进出”，是一切结构的地基，也是复杂度思维的起点。 定位组：哈希表。回答”怎样按键用平均 O(1) 找到元素”，是缓存、索引、去重、计数的共同底座。 层级与关系组：树、堆、图。树表达层级与有序，堆表达偏序下的极值，图表达任意连接关系——三者分别对应”有等级””有轻重””有连接”三类现实问题。 进阶工程组：Trie、并查集、跳表、红黑树、布隆过滤器、LRU 缓存。每个都对应真实的系统组件：搜索提示、动态连通分组、Redis ZSet、TreeMap、缓存穿透防护、缓存淘汰策略。 依赖与顺序依赖主线是：线性结构 → 哈希表 → 树 → 堆/图 → 进阶结构。理由如下： 线性结构建立”存储布局决定操作成本”的核心直觉，后面每个结构都是这个直觉的...

数组和链表是线性结构的两种存储实现，差异不在接口而在内存布局：是否连续决定了随机访问成本与缓存友好度。栈和队列则是在线性结构上叠加访问约束，用 LIFO 与 FIFO 的语义表达处理顺序。吃透这四个结构，分析一切复杂结构就有了起点。 它解决什么问题程序里的数据很少孤立存在，更多时候是一批同类型元素的集合：一串日志、一组订单、一条调用链。第一个要回答的问题不是”用哪个类”，而是”这批元素在内存里怎么摆”。摆放方式只有两种基本选择——紧挨着连续存放（数组），或者分散存放再用指针串起来（链表）。布局一旦确定，每种操作的成本就被物理规律锁死了。 栈和队列回答的是另一类问题：元素按什么秩序进出。它们不关心底层用什么存，只规定访问端点——栈只暴露栈顶，队列一头进另一头出。约束越强，语义越清晰，能表达的处理模型也越明确：撤销、递归、层级遍历，背后都是这两种进出秩序。 核心原理数组 vs 链表：差异来自内存布局数组占据一整块连续内存，第 i 个元素的地址可以直接算出来：基地址 + i × 元素大小。一次加法、一次寻址，这就是 O(1) 随机访问的全部秘密。链表的节点散落在堆中，彼此靠指针相连...

传统 read/write 发送一个文件，要经历 4 次数据拷贝和 4 次用户态/内核态切换，其中两次 CPU 拷贝纯属把数据搬进用户空间又原样搬出。零拷贝是一类让数据不经过用户空间的技术统称：mmap 共享页缓存、sendfile 内核内直发、SG-DMA 抹掉最后一次 CPU 拷贝、splice 借管道传递页引用。本文把每条路线的账算清，并落到 Java NIO、Netty 与 Kafka/RocketMQ 的实践。 它解决什么问题典型场景是文件下载服务：服务端把磁盘文件经 socket 发给客户端，代码只需 read 加 write 两行。但应用根本没有修改数据内容，数据却被 CPU 在内核缓冲和用户缓冲之间来回搬了两趟，外加 4 次态切换的寄存器保存恢复开销。高并发、大文件场景下，这部分纯搬运会被放大成明显的 CPU 瓶颈。零拷贝要省的就是这部分。 先约定算账口径：数据初始不在 Page Cache（需要真正读盘）、不做 TLS/压缩等用户态处理、设备支持 DMA；”切换”指用户态与内核态的模式切换，一次系统调用进出各算一次，与...

I/O 多路复用解决的是”一个线程怎么同时盯住上万个连接”的问题，而不是让单次读写变快。这篇从阻塞模型的线程瓶颈讲起，沿 select、poll、epoll 的演进拆解每一代到底改掉了什么，再讲清 LT 与 ET 的语义差异，最后给出 epoll 的适用边界——它不是银弹。 它解决什么问题最直觉的 TCP 服务端写法是：主线程 accept 一个连接，就丢给一个新线程去阻塞读写。连接少时一切安好；连接冲到上万，问题全面爆发——每个线程默认预留数 MB 栈空间，内存先告急；几千个线程挤在几个核上，CPU 大量时间消耗在上下文切换；而绝大部分连接其实是空闲的，占着线程干等数据。 这就是 C10K 问题。先看一次网络读在内核里的两个阶段： 等数据就绪：数据在网卡、在路上，内核等它到达并放进内核缓冲区。这一步慢，且时长不可控。 拷贝数据：从内核缓冲区拷到用户态的应用缓冲区。这一步很快。 阻塞模型把线程钉死在第一阶段。多路复用换了思路：把一批文件描述符托付给内核，线程阻塞在一个专门的监听调用上，任一 fd 就绪就返回，然后只处理那几个就绪的。”多路”指多个连接，”复用”指...

操作系统面试下篇围绕三条主线：虚拟内存如何隔离与翻译地址、I/O 模型如何高效搬运数据、文件系统如何组织与持久化数据。能否解释「epoll 为什么撑得住十万连接」「write 返回后数据到底在哪」，就看这一篇的功底。 考察地图 虚拟内存与内存管理：虚拟内存的价值、多级页表与 TLB、缺页异常、页面置换。考察对「虚拟地址 → 物理地址」整条翻译链路的理解。 I/O 模型：一次阻塞 read 的完整旅程、select/poll/epoll、零拷贝三条路线。考察对「数据经过哪几层、在哪个阶段阻塞」的把握。 文件系统：inode/dentry 与链接、write 与 fsync 的持久化边界。考察对存储栈的实证理解。 建议自行查阅：内存管理五大职责、VSZ/RSS/PSS 指标、内存碎片与伙伴系统/SLAB、分页与分段的对比、Swap/工作集/抖动、Overcommit 与 OOM Killer、open() 流程、文件的块分配方式、日志文件系统、磁盘调度算法（FCFS/SS...

虚拟内存让每个进程都以为自己独占一片连续内存，物理页实际可以分散、共享、甚至暂时不存在。本文走完一条完整链路：MMU 如何逐级查页表把虚拟地址翻译成物理地址，缺页异常如何按需建立映射，fork 为什么靠写时复制瞬间返回，mmap 能把什么搬进地址空间，以及内存耗尽时 OOM Killer 按什么逻辑挑进程。 它解决什么问题程序想要的是连续、独占、足够大的内存；硬件只有有限且被所有进程共享的物理内存。没有中间层时，程序地址写死、互相踩踏、物理内存用满即崩。虚拟内存用一层地址翻译调和这对矛盾：进程发出的地址不必对应真实位置，隔离、保护、按需分配、共享映射等能力全部从这层翻译生长出来。 核心原理：一次地址翻译的完整路径虚拟地址由虚拟页号和页内偏移组成，翻译时偏移原样保留，页号负责查表。以 x86-64 四级分页为例，48 位虚拟地址按 9+9+9+9+12 位拆分：CR3 寄存器锚定顶级页表 PGD 的物理地址，MMU 依次用各段 9 位索引查 PGD、PUD、PMD，最终在 PTE 拿到物理页帧号，拼上 12 位偏移得到物理地址。每级 512 项、每项 8 字节，一张表恰好占满一...

两个线程同时执行 count++，结果可能只加了一次——同步机制要管的就是这类事。本文从临界区讲起，理清互斥锁、自旋锁、信号量、读写锁各自等的是什么，futex 如何把等待成本压到最低，最后用两个经典问题把原语串起来。 它解决什么问题count++ 在源码里是一行，编译后却是”读内存、加一、写回”三条指令。线程 A 读到旧值还没写回，线程 B 也读到同一个旧值，两个线程各算各的，最后一次写回覆盖了另一次——这就是竞态条件（Race Condition）：结果取决于执行时序，而时序不受你控制。 访问共享可变状态、且不能被并发交错执行的那段代码，叫临界区（Critical Section）。锁与同步机制的全部使命，就是保证同一时刻只有一个执行流在临界区里，并且它写的成果能被下一个进入者正确看到。评价一种同步机制看四个维度：正确性（真的互斥）、进展性（不会全员卡死）、公平性（没人永远等不到）、性能（无竞争时足够便宜）。 核心原理：四种锁各自等什么互斥锁（Mutex） 等的是”进入临界区的资格”。拿不到就睡眠，把 CPU 让出来，由内核在锁释放时唤醒。它有明确的所有权语义：谁加锁谁解...