简介《程序员实用算法》一书配套源码下载包以C语言实现面向希望深入算法底层、动手验证书中结论的程序员和计算机相关专业学生。源码结构基本对应原书章节从链表、栈与队列入手逐步触及散列冲突处理、字符串查找与近似匹配、多种排序算法再到二叉树、AVL树、红黑树、伸展树和B树等进阶主题并向后延伸至日期时间处理、任意精度算术、霍夫曼与LZW压缩、循环冗余校验等实战模块几乎每个专题都提供独立可编译的程序方便单独调试或联合作业。整套资源共116个文件以68个C源码和18个C头文件为主体另有批处理、make工程脚本以及少量示例数据与说明文本便于在Windows和Unix类环境下构建压缩包仅163KB轻量易用适合离线查阅与代码复用。目前已有410人学习/下载读者可对照原书逐章运行源码模仿工程化写法重点理解边界条件、优化手法与不同算法的适用场景是一份能帮助系统巩固算法功底、提高代码实现能力的实用代码集。 做了这么多年开发我观察到一个现象一说学算法很多人第一反应就是打开 LeetCode 刷题一说要提升代码能力就去背各种八股。但真正到了线上帮你撑住流量、稳住延迟的那些东西往往藏在你压根没仔细看过的源码里——你用的框架、中间件、公共库里面全是经过真实流量和业务打磨出来的实用算法。我这些年最大的成长就是学会了从源码里拆解算法再想办法把它们用到自己的项目里。这篇文章我打算把这套方法完整讲一遍包括为什么源码里的算法值得读、具体怎么读、读完怎么落地基本覆盖一个普通程序员从“会写业务代码”到“能设计系统”的必经之路。适合写过两三年代码、想往底层或者架构方向走的同学也适合那些刷过题但总觉得“算法用不上”的人。1. 为什么我建议每个程序员都去啃源码里的算法1.1 算法不是刷题是工程里的取舍刷题和工程里的算法有个很大的区别刷题追求的是在理想模型下把时间复杂度和空间复杂度做到最优但工程里的算法追求的是“在当前场景下综合最优”。这个差别光靠刷题体会不到。举个特别常见的例子在小数据集上做查找线性扫描往往比二分查找更快。为什么因为二分查找虽然复杂度是 O(log n)但它引入了更多分支跳转还破坏了 CPU 的局部性缓存而线性扫描就是顺着一块连续内存往下读数据量小的时候分支预测和预取能把速度拉到极高。很多源码里就是这种“违背教科书最优”的选择比如 glibc 的 qsort 实现在小规模区间直接切成插入排序道理类似。所以说工程里的算法其实是在跟数据规模、内存带宽、缓存命中率、并发竞争、可维护性这些因素做博弈。源码里那些看似“多此一举”的判断和分支往往就是为了处理某种极端数据分布或者规避某个竞争条件这些东西在纯刷题的答案里是看不到的。读源码里的算法读的就是这些取舍背后的理由。1.2 源码是算法唯一的“第一现场”教科书或者刷题网站上的算法通常会把边界条件、异常输入都给你规整得干干净净但真实世界的输入从来不会这么善良。源码里的算法不一样它是有调用方、有上下文、有血有肉的“活物”。比如说 Redis 里的哈希表它没有用教科书里那种简单的一次性 rehash而是搞了一个渐进式 rehash把搬迁工作分摊到每一次增删改查里面去。基础版哈希扩容几分钟就能讲完但为什么同步扩容在大流量下会卡顿、为什么渐进式 rehash 能避免服务毛刺这些是源码的注释和 commit message 里才有的信息。类似的例子还有 STL list::sort 那个奇怪的循环归并实现、Linux 内核里红黑树为什么要这么旋转每个选择背后都有一整套实际工程考量。读源码里的算法相当于拿着带标准答案的习题集在学。而且这套习题集里所有的答案都是被线上大规模环境反复验证过的含金量比任何面试题都高。2. 三类值得反复咀嚼的算法源码2.1 字符串处理KMP 和 AC 自动机字符串处理是源码里出现频率最高、也最容易让普通程序员忽略的一类算法。大家平时写代码基本靠语言自带函数库但真正遇到高吞吐的日志匹配、内容审核、编辑器高亮O(n*m) 的暴力匹配很快就会让你难受。KMP 算法是第一个值得精读的。很多源码里的字符串查找、词法解析器核心都是它的变体。KMP 的精髓是前缀函数next 数组通过预处理模式串的最长相等前后缀实现主串指针不回退。我给一段最简实现建议直接拿去对照源码读def build_next(p): nxt [0] * len(p) j 0 for i in range(1, len(p)): while j 0 and p[i] ! p[j]: j nxt[j - 1] if p[i] p[j]: j 1 nxt[i] j return nxt这段代码前三行很基础但第五行的 while 回退很多人第一次看都懵。它的意思是当匹配失败时借助已经算出来的前缀信息把模式串指针往左回退到某个安全位置避免从头开始匹配。这个“安全位置”的理解直接影响后续能不能读懂 AC 自动机。AC 自动机可以理解为 KMP 在多模式匹配场景下的扩展核心是 Trie 树加上失配指针fail 指针。等你能读懂 KMP 的 next 数组再看 AC 自动机会轻松很多。源码里真正的难点在 fail 指针的构建我后面会用实际案例详细讲。2.2 排序与查找的工程化写法排序和查找是源码里最容易“看起来眼熟、实际读不懂”的模块。很多人看 STL 的 sort 源码会震惊因为它不是一个快排而是快排、堆排、插入排序的混合体。这个混合策略其实是为了应对快排的最坏情况如果每次选的主元都落在区间端点附近复杂度会退化到 O(n²)而堆排可以保证 O(n log n)但常数大。所以工程做法是递归深度浅的时候用快排深度超过阈值就切堆排区间小于一定长度就换插入排序。这种“用空间的确定性换取时间稳定性”的思路是纯理论题里学不到的。再比如二分查找看起来几行代码但边界条件能坑死一大批人。我在源码里见过好几个团队自己实现的二分死循环和错位的 case 频繁出现。核心问题是对“左闭右开”还是“左闭右闭”的定义不清晰导致 mid 取值、区间收窄的写法不一致。一个相对不容易写错的版本长这样def lower_bound(nums, target): l, r 0, len(nums) # 左闭右开区间r 指向第一个不小于 target 的位置 while l r: mid (l r) // 2 if nums[mid] target: l mid 1 else: r mid return l这里最关键的决定是把右边界定义成“开边界”循环条件用l rmid更新时右边保持不动左边加一。这样写能天然避开死循环的坑。源码里大量查找函数底层都是这套逻辑只不过包了一层又一层的模板和宏剥开看就是这些老面孔。2.3 数据结构内部藏着的最实用算法很多人忽略了一个事实数据结构本身就是算法的集合体。哈希表的扩容算法、LRU 淘汰算法、红黑树的旋转与变色这些都是算法而且比单独的一个排序函数更能体现系统设计思路。哈希表值得重点看两件事。第一是负载因子的设置比如 Java HashMap 默认是 0.75Redis 的 dict 则有自己的扩大和缩小阈值这个值不是拍脑袋定的它直接影响空间占用和冲突概率之间的平衡。第二是冲突解决策略拉链法还是开放寻址扩容时是整体复制还是渐进式 rehash这决定了数据结构在高并发下会不会出现卡顿。LRU 缓存淘汰算法更典型一个“双向链表 哈希表”的组合能把查询和淘汰都优化到 O(1)。这个算法在 Memcached、Redis、操作系统的页面置换里都能看到源码读起来有非常强烈的“复用”快感——明明是两个基础数据结构组合起来就解决了复杂的淘汰问题。3. 从源码中提炼算法的实操方法论3.1 带着问题读源码而不是从头通读我最早读源码犯过一个很大的错误拿到一个开源项目就从头到尾一行一行读。结果三天读过去代码没记住多少人倒是劝退了。后来我改成先给自己提三个问题再动手效率翻了好几倍。这三个问题是这段代码要解决什么问题它的入参有哪些边界条件这个函数在被谁调用高频必经路径还是偶尔触发为什么不用更简单的方案是性能、并发还是兼容性要求拿读 Redis 的哈希表源码举例我不是一上来就看 dict.c而是先去搜索哪些地方调用到了dictExpand、_dictExpandIfNeeded搞清楚扩容发生在什么时候然后再在关键函数里打上断点用真实请求打出触发栈。带着问题读代码会条理清晰得多也会少很多“读了后面忘了前面”的挫败感。读的时候我建议你一定把代码跑起来。随便开一个调试器不行要用断点看实时的变量变化。比如读红黑树源码光看旋转的代码十有八九看不懂但你在插入节点的地方打断点然后连续插入十几个不同的值观察树结构一步步变化旋转和变色立刻就理解了。3.2 三步吃透一段算法源码我自己的方法比较笨但确实有效分三步。第一步只读接口和注释不碰实现。先把函数签名、入参、出参、边界条件写清楚搞清楚这段代码对外承诺了什么。这一步的目的是建立心理边界避免一头扎进实现细节里出不来。第二步画数据流图。不用画得多规范就在纸上画几种典型输入下核心变量和数据结构是怎么一步步变化的。这一步的目的是把“算法的过程”从代码里抽离出来理解它到底在干什么。第三步合上源码默写一遍实现。这一步是整套流程里最重要的。很多人读源码能做到“从头到尾都懂”但一合上代码就什么都写不出来这说明知识还没真正进入脑子。默写完之后不要急着走拿你的实现和源码做逐行对比重点看源码里多了哪些你没写的判断和分支那些地方通常是特殊数据场景、溢出保护或者并发考虑是你之前没想明白的关键。3.3 复现时的关键细节默写复现的时候有几个细节是我反复踩坑之后总结出来的分享给各位。边界条件必须单独列清单。常见的有空集、单个元素、全部元素相同、元素已排序、元素反序、包含负数或零。我自己的习惯是写一段算法代码前先把这些边界条件全列出来然后写一个简单测试函数直接跑不要靠脑子想。另一个是内存和溢出的细节。在 C 语言源码里见过不少mid (left right) / 2的写法这里有一个被很多人忽略的整型溢出问题。安全写法是mid left (right - left) / 2这也是源码里考究的实现会特意避开前者的原因。类似的细节还有很多比如数组下标 -1 退避、指针越界、浮点数精度。这些细节单独看都不起眼但组合在一起就构成了“工程代码”和“玩具代码”的分水岭。4. 我在项目里提炼算法并落地的两个案例4.1 网关限流从“计数器”到“滑动窗口”之前做一个内部网关的限流模块最开始团队同学用的是最简单的计数器方案每秒一个计数器超过阈值直接拒绝。上线后压力测试发现一个问题在临界点附近会出现突发流量比如 9:59:59 和 10:00:00 这两个窗口各放了 500 个请求但用户感知到的流量却是瞬间 1000 个请求打进来这就突破了后端服务的保护水位。这个场景摆在面前最容易想到的方案就是滑窗也就是把时间窗口细分成多个小格子比如把 1 秒拆成 10 个 100ms 的子窗口每次判断时把当前时间往前推一个完整窗口统计窗口内所有子窗口的请求数。工程上最简单的一种实现是拿一个定长数组存请求时间戳然后每次请求到达时做窗口裁剪。示例代码长这样import time from collections import deque class SlidingWindowLimiter: def __init__(self, capacity, window_size): self.capacity capacity self.window_size window_size self.timestamps deque() # 双端队列支持两端的 O(1) 操作 def allow(self): now time.time() while self.timestamps and self.timestamps[0] now - self.window_size: self.timestamps.popleft() if len(self.timestamps) self.capacity: self.timestamps.append(now) return True return False我在落地的时候做了几个改造。第一是没有用数组而是用双端队列避免pop(0)的 O(n) 开销第二是把窗口分片细节封装在了协议层方便后续接分布式限流第三是单独监控了timestamps队列长度用来预警突发流量堆积。这个模块上线后最直观的效果就是网关后面那台数据库服务器的 QPS 高峰曲线变得平滑了很多不再有那种“卡点冲刺”的现象。4.2 内容审核AC 自动机做敏感词过滤另一个让我印象深刻的项目是做社区内容的敏感词过滤。最开始的实现非常朴实遍历敏感词库对每个词调一次indexOf。后来词库涨到几千条、每秒钟又有几百条评论进来这种 O(评论长度 × 敏感词数量) 的暴力方案很快就扛不住了。当时我脑子里的第一反应就是源码里读过的 AC 自动机。本质上是把敏感词集合建立成一棵 Trie 树再给每个节点加一个 fail 指针让文本在遍历时一旦失配就能跳到下一个可能匹配的位置最终用一个 O(n) 的扫描解决全部模式的匹配。构建 fail 指针的过程是核心我把简化版写出来from collections import deque def build_ac(children, fail, words): children[node_id] 是子节点映射返回构建好的 fail 数组 q deque() for key, node_id in children[0].items(): fail[node_id] 0 # 第一层节点的 fail 指向根节点 q.append(node_id) while q: cur q.popleft() for key, node_id in children[cur].items(): f fail[cur] # 沿着 fail 链找父节点的失配指针下是否存在同样的子节点 while f and key not in children[f]: f fail[f] fail[node_id] children[f].get(key, 0) q.append(node_id)这段代码真正不太好理解的地方在while f and key not in children[f]它其实是在做 fail 指针的“路径压缩”沿着父节点的失配链往上跳直到找到一个同样以 key 作为子节点的位置为止。只有亲手实现过一遍才明白这个循环存在的意义是避免查找时重复回退确保后面匹配文本时的跳转是 O(1) 级别。线上改造完成之后同量级文本的过滤耗时就掉了两个数量级规则库再往后涨到几万条也没再成为瓶颈。这个过程让我很直观地感受到源码里那些“读着费劲”的算法一旦真正落到业务场景回报是非常可观的。5. 读算法源码时踩过的坑与排查心得5.1 我在读源码时常犯的三个认知误区第一个误区是只背思路不手写。我早年读红黑树源码读注释、看图解都觉得自己懂了但真到面试或者自己要实现一个有序集合时手完全跟不上脑子。后来我给自己定了一条规矩凡是觉得“看懂了”的算法必须在三天之内默写一遍。默写不出来的就不算真正读过。第二个误区是忽略数据规模差异。源码里的算法设计一定适配它所在场景的数据规模换一个量级就未必成立。比如 Redis 里有些操作频繁、数据量又小的路径会用简单链表你如果照搬到大数据量场景必然出问题。读源码的时候要时刻问一句它这个选择是在什么数据量级下做的判断第三个误区是只关注时间不关注空间。比如 AC 自动机构建 Trie 树之后就有一个明显的空间开销每个节点还要挂 fail 指针词库大的时候内存会直线上升。源码里经常有类似的“空间换时间”决策如果只读逻辑不关注内存占用换到自己项目里很可能被内存打爆。5.2 源码被“隐藏”后怎么排查读 C/C 源码的时候很多人会被宏定义、内联函数、模板展开折磨得够呛。明明核心逻辑就几行但跳来跳去始终找不到入口。我遇到这种情况的排查经验是不要用默认的 Release 构建去读源码一定要编译一个带 debug 符号、关闭优化的版本再配合 IDE 的“跳转到定义”功能去看会舒服很多。另外一类隐蔽的坑是我在调一个内存问题时遇到的由于编译器做了优化实际执行的代码和源码并不严格一致尤其是涉及到 volatile、内存屏障、无锁编程的部分你会看到源码里明明没有的读写顺序变化。这种时候不要怀疑是源码错了更不要急着改逻辑应该先去看对应的汇编或者打开编译器优化开关再重新分析。还有一类问题是源码依赖链太长。比如你想读一个哈希函数结果它引入了十几个头文件和类型抽象追着追着就迷失了。我的经验是先对着函数名全局搜索找到最核心的几十行实现而不是从入口函数一步步往下跳。等你把这几十行吃透了再回头补那些外围封装效率能高一倍不止。5.3 更高效读算法源码的三个小工具最后分享几个我读完大量源码后沉淀下来的实用技巧。第一个是小工具git log读源码时顺手查一下关键函数的历史提交可以看到它从简单的写法一步步变得复杂的过程commit message 里往往写着为什么要加这种边界处理这是比注释更真实的设计文档。第二个是用性能分析工具验证你的判断。比如你读了一个哈希算法想知道它到底快在哪里直接拿 perf 看分支预测失败率、缓存命中率比空想有说服力得多。同样的道理适用于内存分配、磁盘读写这些外围因素很多时候代码本身不是瓶颈算法所在的环境才是。第三个是维护自己的“算法源码片段库”。每读透一个算法尽量保留一个最小可运行的示例、一份核心思路说明、一组边界测试样例。时间长了你会发现自己手头积累了一整套带在实际业务里验证过的算法工具箱以后做设计选型时可以直接“抄自己以前的作业”而且知道每段实现背后的取舍比临时上网找答案要可靠得多。阅读痛点常见原因我的排查建议宏和内联导致逻辑跳转困难预处理器展开后代码形态变化大用 debug 构建 关闭优化配合 IDE 跳转到展开后的定义源码与实际执行行为不一致编译器优化、乱序执行、无锁语义查看汇编或关闭优化复测必要时对比 CPU 缓存行为依赖链太长迷失在类型抽象中工程架构分层过多优先抓最核心几十行外围封装后补避免线头式跟踪理解算法但无法复现缺少输出倒逼输入三天内默写一遍拿实现和源码逐行对比差异无法判断算法效率缺乏数据规模意识用 perf 查看分支预测、缓存命中率用压测验证复杂度提示源码阅读不是一朝一夕的事我更建议你把它作为日常开发的一部分而不是专门挑出一整周来“闭关”。每次只挑一个函数、一个问题带着问题去读读完了就试着写一遍、改一遍久而久之才真正变成自己的能力。我个人在实际操作中的体会是源码和算法从来不是两个割裂的领域。普通程序员最容易犯的错就是把源码当作文档来通读或者把算法当作公式来死背。真正有效的姿势是把源码当作问题的集合把算法当作问题的答案然后在两者之间来回穿梭。现在我处理一个问题时习惯性地会先问一句手头这些依赖库里有没有现成的实现它是怎么处理数据分布的如果换我来写我会在哪里做得不一样这三个问题想明白了这段源码里的算法基本就吃透了。我自己这些年攒下的代码片段库就是这么一点点积累出来的。本文还有配套的精品资源点击获取