做了十年PHP开发我越来越觉得“PHP用不到算法”这句话是个伪命题。早期做业务系统天天写增删改查确实用不上什么高深算法可一旦系统开始有瓶颈——接口超时、导出卡死、内存爆掉、排行榜算半天出不来——追根溯源几乎都卡在数据结构和算法选型上。分页查询慢、日志去重跑不动、缓存命中率低这些Web开发里最常见的性能问题本质上都是算法问题。这篇我就把PHP里真正用得上的常用算法梳理一遍从数组、栈、队列这些数据结构到排序、查找、缓存淘汰策略全按实战场景展开每段都带可运行的代码和踩坑复盘。不管你是刚入门还是做了几年业务开发按着这条路把基础算法补上后面遇到性能优化你会发现自己突然就有思路了。1. 为什么PHP开发者绕不开算法这道坎1.1 Web开发里的算法比你想象的更常见很多人觉得日常开发里算法没啥用其实是因为算法藏得太深你根本没意识到自己正在用它。用户登录时校验密码从数据库里把用户记录读出来、比对哈希串这是哈希查找购物车里的商品要按添加时间倒序展示你写了个usort这是排序算法后台菜单要做成无限级分类你递归遍历每个节点的子节点这是树的遍历运营要导出一批订单按金额区间统计你循环套循环这已经无意中用到了复杂度分析的概念。我见过某开发者接手一个电商后台库存扣减接口越来越慢排查到最后发现罪魁祸首是一段嵌套三层循环的商品匹配逻辑数据量从几千涨到几万之后单次请求时间直接翻了上百倍。他当时很委屈地说“我没写算法啊”可那段代码明明就是最典型的O(n³)复杂度实现。所以算法不是一门独立课程它就是你写代码时的每一层循环、每一次查找、每一次排序选择。1.2 大O复杂度衡量代码好坏的尺子大O复杂度这个概念看着唬人其实就是“当数据量变大时你的代码变慢的速度”。最直观的理解方式把数据量从1万涨到10万如果执行时间几乎不变那是O(1)或O(log n)如果时间翻了10倍那是O(n)如果翻了100倍那就是O(n²)级的代码。PHP业务代码里最常见的性能杀手就是嵌套循环凑出来的O(n²)。两个各有一万条数据的数组要做匹配最自然的写法是两层foreach套着if看似没毛病数据量一上来就完蛋。换成哈希表把匹配建索引直接降到O(n)10万条数据也就几十毫秒的事。后面第6章我会专门用真实场景复盘这种优化这里先记住一个结论算法优化的本质就是想办法把复杂度从高数量级往低数量级压。2. PHP数据结构最顺手的那套工具箱2.1 PHP数组一个披着数组外衣的万能容器PHP的数组在底层是个哈希表这决定了它和传统语言的数组有本质区别。普通数组按下标存储按下标访问PHP数组则是一个键值对映射字符串键和整数键都能用查找时间复杂度接近O(1)非常快。但也正因为底层是哈希表PHP数组维护了元素的插入顺序所以foreach遍历时是按插入顺序来的这一点和纯哈希表不一样。实际开发中我经常利用这个特性做集合运算。比如一个接口返回了多个批次的商品ID需要去重后按原有顺序传给下游我直接拿数组键来去重$ids [1001, 1002, 1001, 1003, 1002, 1004]; $unique []; foreach ($ids as $id) { $unique[$id] true; } $result array_keys($unique); // 输出: [1001, 1002, 1003, 1004]这个操作是O(n)的比“查询数据库去重”或者“两层循环去重”都快得多。很多开发者为了去重去写array_unique但 array_unique 底层实际上也是先排序再比较复杂度更高在批量数据处理时反而不如这种“键值翻转”写法快。这就是理解底层数据结构带来的甜头。2.2 SplStack与SplQueue标准栈与队列的正确用法PHP内置的SplStack和SplQueue实现了标准的栈和队列操作但业务代码里主动用的人不多大部分人用数组加array_push/array_pop模拟。数组模拟当然可以可一旦涉及函数间传递或者需要保证类型清晰内置SPL类更规范代码可读性也好很多。栈的典型场景是括号匹配校验。比如运营配置了一个公式要检查括号是否成对、顺序是否正确我写过这样的解析器function checkBrackets(string $expr): bool { $stack new SplStack(); $map [( ), [ ], { }]; $length strlen($expr); for ($i 0; $i $length; $i) { $char $expr[$i]; if (isset($map[$char])) { $stack-push($char); } elseif (in_array($char, $map, true)) { if ($stack-isEmpty() || $map[$stack-pop()] ! $char) { return false; } } } return $stack-isEmpty(); }队列的应用更常见。某次做一个消息推送的批量任务需要把待处理的用户ID按顺序分批推送用SplQueue存待处理列表处理完一个pop一个子任务成功后push到下一轮队列里代码清爽且不容易出错。想想生活中的排队——先来的先服务这就是FIFO跟栈这种“后进先出”完全相反。3. 排序算法从手写到内置函数的取舍3.1 快速排序理解分治思想的开端快速排序的思维用一句话概括选一个基准值把比它小的放左边比它大的放右边然后对左右两部分递归重复这个过程。这种“分而治之”的思路在算法里无处不在理解透了以后看二叉搜索树、归并排序都会顺很多。我写一个简洁的实现版本function quickSort(array $arr): array { $count count($arr); if ($count 1) { return $arr; } $pivot $arr[0]; $left $right []; for ($i 1; $i $count; $i) { if ($arr[$i] $pivot) { $left[] $arr[$i]; } else { $right[] $arr[$i]; } } return array_merge(quickSort($left), [$pivot], quickSort($right)); }这个版本胜在短、好记、面试能写出来但生产环境直接用肯定不行。问题在于递归会重复创建大量中间数组内存消耗大而且基准值固定取第一个元素遇到基本有序的数组反而退化到O(n²)。所以真要用手写快速排序建议用原地分区方式加三数取中选基准这是后话这里知道原理优先。3.2 归并排序当稳定性成为硬需求快速排序是不稳定的相同值的元素可能交换相对位置。比如订单列表先按金额排序再按下单时间排序如果第二轮的排序不稳定第一轮的结果会被打乱。归并排序是稳定的它把数组不断对半分直到每个子数组只有一个元素再把相邻的有序子数组合并起来。实际业务里需要自己写归并的场合确实不多因为PHP内置的sort家族已经用了稳定排序的优化策略。但这个算法的真正价值在于“合并两个有序数组”的操作思路它经常用在数据合并场景里。例如两个已经排好序的数据源要合并成一个有序列表与其重新全量排序不如用归并的合并步骤复杂度只有O(mn)。3.3 PHP内置排序函数别重复造轮子PHP自带了非常完善的排序家族sort排序数组值、asort保持键值关联排序、ksort按键排序、usort用自定义函数排序数组值、uasort用自定义函数保持键值关联排序。这些函数底层由C实现性能远强于手写PHP循环能用内置函数的场景绝不手写这是铁律。但sorted家族有个坑是它们的排序规则和你想的未必一致。比如对数字数组用sort($arr)如果没传SORT_REGULAR以外的标志PHP可能把数字当字符串比导致10 9。解决方法是明确传标志位$nums [3, 10, 9, 22, 1]; sort($nums, SORT_NUMERIC);另一个坑是usort的回调函数不符合预期时排序结果是未定义的。你要返回负数、零或正数而不是返回布尔值。某架构师排查过一个问题一组城市按首字母排序总是乱序最后发现回调里直接return $a[initial] $b[initial];当相等时返回false但实际上相等应该返回0这个细节导致结果不稳定。写法应该是usort($cities, function ($a, $b) { return strcmp($a[initial], $b[initial]); });4. 查找算法二分、哈希与搜索场景4.1 二分查找有序数据里的倍速搜索二分查找的要求很明确数据有序、可随机访问。它的逻辑不复杂——每次取中间值比较目标小则往左半区找目标大则往右半区找每次砍掉一半范围。对一亿条有序数据做查找最多只需要约27次比较这就是log n复杂度带来的震撼。我常遇到的情况是需要在一个有序的ID数组里判断某个ID是否存在。用for循环线性找是O(n)二分是O(log n)。手写二分最容易出错的是边界条件一不小心就死循环或者越界。我推荐直接用闭区间写法清晰且不容易错function binarySearch(array $arr, int $target): int { $left 0; $right count($arr) - 1; while ($left $right) { $mid intdiv($left $right, 2); if ($arr[$mid] $target) { return $mid; } if ($arr[$mid] $target) { $left $mid 1; } else { $right $mid - 1; } } return -1; }注意这里$mid的算法PHP整数溢出虽然不常见但intdiv($left $right, 2)相比($left $right) 1可读性更好。循环条件必须用否则数组只有一个元素时会漏判更新边界时用mid 1和mid - 1而不是mid不然可能出现死循环。这几个点都是手写二分必考的细节。4.2 哈希查找登录场景里的O(1)之道哈希查找本质上就是“通过计算直接定位”不需要比较。PHP数组底层就是哈希表所以当你用用户名作为键去取用户信息时已经是在用哈希查找了$userMap []; foreach ($users as $user) { $userMap[$user[username]] $user; } $target $userMap[admin] ?? null;把一批用户数据灌进数组后按用户名取数据就是O(1)。这就是前面说的“用哈希表把匹配建索引”的底层原理。实际Web开发里缓存系统就是最典型的哈希查找——Redis的底层存储本质上是哈希表Memcached也是。理解哈希查找你就知道缓存Key的设计有多重要Key设计得好一次哈希定位直接拿到数据设计得差可能得遍历整个缓存空间完全失去缓存的意义。哈希碰撞不同Key映射到同一位置是理论上不可避免的但PHP底层已经用链地址法处理了碰撞日常开发基本无感。真正需要关注的是哈希函数是否均匀——如果某公司用户中心把所有用户ID取模后存到Redis的不同分片分片数量设置不合理会导致大量Key集中在少部分分片上查找性能不均匀。这就是典型的哈希分布理论在生产里的体现。5. 缓存淘汰算法LRU的PHP实现5.1 为什么需要LRU而不是FIFO缓存系统迟早要面临一个现实问题内存有限放不下所有数据到底淘汰谁FIFO先进先出规则是“谁先来谁走”不考虑数据有没有被频繁使用LRU最近最少使用规则是“最久没被使用的先淘汰”。前者实现简单但不合理——一个每天都访问的热门数据只因为进入得早也可能被无辜淘汰。LRU的思想是基于时间局部性原理如果一个数据刚被访问过那么短期内大概率还会再被访问。所以最近被用过的数据应该保留长时间没被碰过的数据优先清理。这个策略在Redis的maxmemory-policy配置里也是默认的方向之一。我自己做本地缓存层时就常以LRU为核心来设计内存管理。理解LRU比单纯调配置更能帮你判断缓存为什么命中率低。5.2 用数组实现一个简易LRU缓存LRU需要同时支持两种操作快速找到Key对应的值、快速知道哪个Key最久没被访问。单靠一个普通数组做不到因为数组只能按插入顺序遍历无法快速把某个已有Key提到“最新访问”的位置。所以常见方案是哈希表加双向链表但在PHP里我们可以用一个比较取巧的办法用一个记录访问时间的数组加一个值数组。class LRUCache { private array $values []; private array $lastAccess []; private int $capacity; public function __construct(int $capacity) { $this-capacity $capacity; } public function get(string $key): mixed { if (!isset($this-values[$key])) { return null; } $this-lastAccess[$key] microtime(true); return $this-values[$key]; } public function set(string $key, mixed $value): void { if (!isset($this-values[$key]) count($this-values) $this-capacity) { $oldest null; $oldestTime PHP_FLOAT_MAX; foreach ($this-lastAccess as $k $time) { if ($time $oldestTime) { $oldestTime $time; $oldest $k; } } if ($oldest ! null) { unset($this-values[$oldest], $this-lastAccess[$oldest]); } } $this-values[$key] $value; $this-lastAccess[$key] microtime(true); } }这个实现思路用于中小规模缓存完全够用但每次淘汰时要遍历全部lastAccess找最老的时间点复杂度是O(n)。生产环境如果缓存条目多这个遍历会成为瓶颈那时就应该换用真正的哈希表加双向链表结构维护访问顺序或者直接交给Redis做LRU让专业的东西干专业的活。但作为学习理解和中小场景实践这个版本逻辑清晰比看伪代码直观得多。6. 性能优化实战复盘算法选型如何救命6.1 日志去重嵌套循环改哈希耗时从秒级到毫秒级某次帮一个用户行为分析系统做日志清洗每天几百万条日志要去掉重复的设备ID保留最后一次出现的记录。最初的实现是两层循环外层遍历当天日志内层维护一个已处理列表判断当前ID是否已存在。日志量3万条时还能接受到50万条时直接跑一个多小时根本没法用于日常报表。问题的本质是O(n²)每处理一条日志都要线性扫描已处理列表。改成哈希表后已处理的设备ID直接用数组键存储判断是否存在变成O(1)整体复杂度降到O(n)。同样的50万条日志处理时间从小时级降到两分钟以内。我当时还顺手用isset判断而不是array_key_exists因为isset在值不可能为null时更快在一个高频循环里这微小的差异都会累积。$processed []; foreach ($logs as $log) { $deviceId $log[device_id]; $processed[$deviceId] $log[timestamp]; } $uniqueLogs array_map( fn($d) [device_id $d, timestamp $processed[$d]], array_keys($processed) );6.2 订单列表排序usort配合稳定排序保住分页结果运营后台的订单列表原来一直用SQL的ORDER BY先把时间排好再取当前页。后来需求变成“同一商品的最新订单优先展示”就只能先把订单按商品分组组内按时间排序。当时有同事直接在内存里用三层循环做排序数据量一大页面直接超时。正确解法是分两步先用商品ID分组建立商品ID 订单列表的哈希映射再对每组订单用usort按时间排序。因为SQL查出来的数据本来就是有序的组内排序用稳定的usort配合strcmp或空间比较符非常高效。这个案例的关键不是排序本身多难而是意识到了“用哈希分组避免嵌套循环”这一点然后再叠加稳定的排序规则保证结果可预期。$grouped []; foreach ($orders as $order) { $grouped[$order[product_id]][] $order; } foreach ($grouped as $group) { usort($group, fn($a, $b) $b[created_at] $a[created_at]); }6.3 大表分页抛弃OFFSET改用游标分页是Web开发每天都要面对的场景但数据量大以后LIMIT 100000, 20这类写法会越来越慢。原因是数据库必须先扫描、丢弃前10万行再取后面的20行这个操作的成本随页码增大而线性上升。这本质上是“跳过前面所有元素”的线性操作不是算法问题但算法思维能帮你设计出更好的方案。我推荐的方案是游标分页记录上一页最后一条记录的ID或者时间下一页直接用WHERE id $lastId ORDER BY id LIMIT 20取。这样每次查询都是直接定位效率稳定跟页码无关。代价是用户不能再随意跳页但对信息流、列表页这类产品来说完全没有影响。这个思路就是二分查找思想的变体——每次直接定位到目标区间不做过量扫描。// 旧方案: 深度分页 $rows $db-query(SELECT * FROM orders ORDER BY id LIMIT 100000, 20); // 新方案: 游标分页, 假设上一页最后一条ID是 $lastId $rows $db-query(SELECT * FROM orders WHERE id $lastId ORDER BY id LIMIT 20);7. 常见问题与排查技巧实录7.1 递归炸掉内存Xdebug与迭代替换写过递归的PHP代码大概率遇到过Allowed memory size of 134217728 bytes exhausted之类的报错。递归每深入一层就会在调用栈上多压一层帧PHP默认内存限制往往经不起太深的递归。某次写无限级分类的树形结构用递归构建菜单树数据层级到了七八层就开始报警再深直接内存溢出。排查方式可以用Xdebug的xdebug_get_function_stack()看调用栈深度或者直接减小内存限制让错误更早暴露。但真正解决还得从算法层面下手把递归改成显式栈迭代。用SplStack手动模拟系统调用栈每处理一个节点就压栈循环处理不再依赖PHP的调用栈内存占用即刻恢复正常。这是一个典型的“知道栈结构就能解决问题”的案例。function buildTreeIterative(array $nodes, string $parentKey parent_id): array { $tree []; $stack new SplStack(); $stack-push([nodes $nodes, parent null, depth 0]); while (!$stack-isEmpty()) { $item $stack-pop(); $parent $item[parent]; $children array_filter($item[nodes], fn($n) $n[$parentKey] $parent); if ($parent null) { $tree $children; } foreach ($children as $child) { $stack-push([nodes $nodes, parent $child[id], depth $item[depth] 1]); } } return $tree; }这个版本不是最优的但能清楚说明迭代替代递归的核心逻辑。实际生产我建议直接把树形结构查出来一次性处理避免数据库递归查询这是另一个话题了。7.2 排序不稳定导致的数据错位一次数据报表出现诡异Bug同一批数据刷新两次结果顺序不一样而且相同金额的订单排列顺序每次都变。排查半天发现是usort的回调函数返回了不稳定的布尔值没有严格返回负数、零、正数。PHP文档里明确写了回调返回的非零值会被当作“前大于后”但如果两个元素相等时你也返回一个非零值排序结果就是未定义的——底层快排的交换逻辑会随意移动它们。这个问题的排查思路其实很简单先检查回调函数是不是满足“严格弱序”的要求——相等时返回0小于时返回负数大于时返回正数。用太空船运算符天然满足这个要求推荐直接用它。7.3 迭代时修改数组的坑在foreach循环里直接对数组做unset或者array_splice很容易产生诡异行为。比如删除当前元素后下一个元素的索引可能错位或者因为PHP数组内部指针的移动规则导致某些元素被漏处理。这个问题的正确解法不是“小心处理索引”而是“不要边遍历边改数组”。先收集要删除的键遍历结束后统一删除或者用array_filter生成一个新数组。这个原则在算法题里也有体现很多排序和查找算法的错误实现就是因为在处理过程中修改了原数组而没有保存副本。理解“不可变操作”“先收集后统一处理”的思路能帮你规避一大类PHP陷阱。$toDelete []; foreach ($items as $key $item) { if ($item[expired]) { $toDelete[] $key; } } foreach ($toDelete as $key) { unset($items[$key]); }8. 一些实操体会我反复强调过一件事算法不是象牙塔里的东西它就是你在写每一行循环、每一次查找时做的选择。用哈希代替嵌套循环用游标代替深度分页用稳定排序保住业务规则用显式栈代替递归——这些优化没有一个是需要高深数学能力的它们靠的是把数据结构和复杂度这两个基本功落到代码里。很多PHPer觉得算法是面试前临时抱佛脚的东西其实不然。真正常年写业务代码的人会发现系统性能问题的根因翻来覆去就是那么几种无效的重复计算、糟糕的数据结构选择、忽略了复杂度随数据量增长的变化。我把这些问题的解法都写在了上面遇到类似场景可以直接套用、改改就能上生产。最后再分享一个小技巧排查性能瓶颈时先别急着看慢查询日志和加缓存先用排除法确定“最内层的循环是什么”“最频繁的查找是什么”“数据量从多少涨到了多少”。这三问能帮你把问题定位到具体的算法选择上。很多时候优化SQL索引不如优化应用层的查找结构来得快加Redis缓存不如先把内存里那个每次都全表扫描的数组换成哈希表来解决得彻底。算法功底就体现在这些地方——它是你手里最朴实但最可靠的那把刀。