★ FEATURED ARTICLE 如果你跟我一样经历过那种背完八股文依然写不好代码的阶段多少会对Java常用算法这种词既熟悉又反感。面试官喜欢问ArrayList和LinkedList谁快、ConcurrentHashMap怎么保证线程安全、线程数该设多少可进了公司整天写的还是CRUD和接口。我干了几年Java之后才慢慢明白所谓常用算法不在那种需要推导证明的难题里而是藏在集合框架和并发工具类背后的每一个工程决策中。这篇内容不推公式就用我实际踩过的坑把集合框架里的扩容与哈希结构、排序库函数背后的算法策略、并发编程里的CAS/AQS/线程池调度以及数据一致性场景下的锁和幂等方案串一遍。适合准备面试的Java工程师也适合想把日常代码写得心里有数的开发者。1. 集合框架的复杂度错觉先搞清楚数据结构再谈算法1.1 ArrayList扩容背后的均摊复杂度当年我背面试题时对ArrayList的add是O(1)深信不疑直到看了源码才意识到问题没那么简单。add(E e)确实大部分时候是常数时间但在容量不够的时候它会创建新数组并把旧数组整体复制过去这个System.arraycopy是货真价实的O(n)。两者都对区别在于你要区分单次最坏复杂度和均摊复杂度。ArrayList默认初始容量是10每次扩容变成oldCapacity (oldCapacity 1)也就是1.5倍。假设容量从n涨到1.5n这一次扩容要拷贝n个元素但接下来还能再插入0.5n次而不用扩容所以把n的拷贝成本摊到这0.5n次新增上单次均摊就是O(1)。这个结论有个前提扩容倍数必须大于1。假如有谁把扩容策略改成每次只加1个槽位那均摊复杂度直接就退化成O(n)每一次add都可能触发数组拷贝。Java里1.5倍就是扩容因子它本质上是在浪费内存和频繁拷贝之间做权衡。实际工程里ArrayList是否预分配容量对性能影响非常直观。我做过一个百万级数据的批处理循环往List里add没设置初始容量结果频繁扩容导致GC压力激增任务跑到后面明显变慢。改成new ArrayList(预估行数)之后扩容次数从几十次降到一两次整体耗时几乎减半。你不需要记住确切数字但要养成一个习惯只要你能估算数据规模就顺手把容量传进去。1.2 LinkedList的O(1)神话为什么总翻车教科书标准答案是ArrayList查找快、插入慢LinkedList插入快、查找慢。这句话放在理论层面没错但工程里经常被错误套用。LinkedList真正的O(1)只针对addFirst和addLast这种头尾操作中间插入add(int index, E element)得先用O(n)从头或从尾找到那个位置和ArrayList一样慢甚至更慢因为要遍历节点。另外每个节点都是一个Node对象在64位JVM上占的内存比一个数组元素多得多再加上节点分散在堆里遍历时CPU缓存命中率很差。相比之下ArrayList的底层数组是连续内存块CPU预取机制能发挥很大作用。我做过一个不严谨但很有参考性的小实验在10万个元素的数据结构正中间插入一次ArrayList和LinkedList谁快结果是ArrayList反而快。原因很直白ArrayList的System.arraycopy是极其底层的内存搬移对于十万数量的数组就是几十KB级别的拷贝而LinkedList要先从头或者尾二分地遍历五万个节点每次访问都会产生指针跳转和缓存未命中。两者一对比LinkedList插入快这个结论在中间插入场景里根本不成立。真正能发挥LinkedList优势的是只从头部和尾部持续增删的队列场景而且那个场景你直接用ArrayDeque更好连续数组比链表节点内存更紧凑。1.3 HashMap的哈希扰动与树化阈值HashMap是我觉得最值得花时间看源码的集合类。put的时候会对key.hashCode()做一个扰动h ^ (h 16)目的是让高位信息混合到低位来因为取下标时用的是低位。HashMap的数组长度永远保持2的幂所以table.length - 1的二进制是全1hash (table.length - 1)就能等价于取模但是纯位运算比%快得多。这也是为什么HashMap扩容永远翻倍而不是随意增长翻倍之后重新散列时才可以用位运算快速重定位。链表转红黑树的阈值是8退化为链表的阈值是6中间空两格是为了防抖。单次hash冲突导致链表过长是极小概率事件在负载因子0.75、哈希分布均匀的假设下某个桶链表长度超过8的概率大约只有千万分之六所以树化其实是防御极端攻击或者异常hashCode的保险丝。很多人担心自己不完美的hashCode会把HashMap变成链表但真正能把桶打爆到8的往往是有人在恶意构造相同哈希的key或者你重写的hashCode只返回固定值。这种时候红黑树虽然能兜底但性能照样不如去修hashCode本身。2. 排序算法在Java里的三种面孔手写、库函数、并行排序2.1 冒泡排序教学价值远大于工程价值冒泡排序是无数人的算法启蒙也是面试八股文常客但工程里几乎不会有人真拿它处理数据。它的教学价值在于把比较、交换、缩减问题规模这三个最朴素的步骤讲清楚。经典双层循环外层控制比较轮数内层控制比较范围把最大元素逐步顶到末尾。最直观的优化是加一个标记位某一轮没有任何交换就提前结束。这个优化让冒泡排序在遇到基本有序数据时能达到接近O(n)的效果。还有一个更进一步的优化是记录每一轮最后一次发生交换的位置下一轮内层循环只需要扫到这个位置天然就把后半段已经有序的元素排除掉了。我之前整理算法笔记时写过一个带边界缩进的冒泡版本虽然现实中没用上但写它的过程让我理解了所有排序优化的共同点减少无效比较。这个思想在后面看Arrays.sort里的插入排序小数组优化、TimSort对有序run的识别全都一脉相承。所以面试官让你手写冒泡考的不是你能不能背出代码是你懂不懂它在排序算法家族里的位置和局限。public static void bubbleSort(int[] arr) { int n arr.length; int lastSwap n - 1; while (lastSwap 0) { int newLastSwap 0; for (int i 0; i lastSwap; i) { if (arr[i] arr[i 1]) { int tmp arr[i]; arr[i] arr[i 1]; arr[i 1] tmp; newLastSwap i; } } lastSwap newLastSwap; } }这段代码里的lastSwap就是边界缩进的核心只要某一轮最后交换发生在位置i就说明i之后的元素都已经有序下一轮比较到i即可不用再往后扫。2.2 Arrays.sort的双枢轴快排与TimSortJava的Arrays.sort其实内部有两条完全不同的算法路线这是很多人忽略的。对int、long这类基本类型数组它用DualPivotQuicksort双枢轴快排对Object数组比如你sort一个String数组或者自定义对象数组它走的是TimSort。为什么要区分基本类型只需要排序结果无所谓稳定但对象排序通常希望相等元素的原始顺序保持不变这是稳定排序而快排是不稳定的归并排序是稳定的TimSort本质就是归并加插入排序的混合体。所以Collections.sort、list.sort这些你日常用的接口背后其实都是归并这一条稳定路线。DualPivotQuicksort是JDK 7引入的改进版本一次选取两个枢轴把区间切成三块比经典单枢轴快排平均减少递归深度和元素移动。TimSort的绝活是识别数据里已经连续有序的run直接拿过来用再配合二分插入排序把小run整理成大run最后归并。这解释了为什么很多经验贴说对部分有序数据TimSort比快排还快。对基本类型的大数据量还有Arrays.parallelSort会用ForkJoin并行化底层算法仍然是这两条路线只是拆成子任务交给多核。它的阈值是8192数据量不够大时走并行反而可能因为线程拆分开销变慢。这里有个很实用的选型心得如果数据是基本类型并且对稳定性没要求就用Arrays.sort(int[])默认快排如果是对象或者需要保证稳定用list.sort走TimSort如果机器核数多而且数据量几十万起步可以试试parallelSort但一定要做压测别凭感觉上线。2.3 Comparator签名里的反直觉陷阱排序库函数再快如果Comparator写错了照样崩给你看。JDK 8之后TimSort加了一个校验一旦发现比较器违反传递性会抛IllegalArgumentException: Comparison method violates its general contract。最常见的翻车写法就是return a - bint差值在溢出时符号会反转比如a是Integer.MAX_VALUEb是负数a-b反而变成负数明明a更大却排在前面。正确做法是Integer.compare(a,b)或者Comparator.comparingInt。还有一种常见错误是只返回1和-1不返回0比如(a b ? 1 : -1)这会让比较器认为任何两个元素都不相等破坏排序稳定性在去重或TreeSet场景会出现奇怪行为。不要迷信一行比较器比手写compareTo更高大上。Comparator.comparing(类::字段, Comparator.nullsLast(...))这种链式写法能让JDK替你处理空值和稳定比较比你手写少踩很多坑。我之前线上出过一个偶现排序异常排查了很久最后发现是某个字段转成Integer后有空值没处理Comparator在特定数据分布下违反传递性不同JVM版本的排序结果还不一致属于典型的数据相关bug。后来的习惯是能用Comparator.comparing链式写法就不手写compareTo尤其配合Comparator.nullsFirst/nullsLast处理空值让JDK替我把边界情况处理干净。3. 并发编程的算法内核CAS、AQS与线程池3.1 CAS自旋无锁同步的原子基石并发编程里最常见的两个算法级组件一个是CAS一个是AQS。CAS全称Compare-And-Swap底层是CPU的cmpxchg指令Java用Unsafe或VarHandle把它包出来。AtomicInteger的incrementAndGet内部就是一个死循环每次读取当前值算出自增后的新值然后用CAS比较当前内存里的值是否还等于刚才读到的旧值相等才写入不相等就重头再来。这里的重头再来叫自旋。自旋等待的好处是全程没有线程阻塞没有上下文切换低竞争时性能甩synchronized一条街坏处是高竞争下大量线程同时空转CPU利用率很高但吞吐上不去。CAS还有经典的ABA问题线程A读到值是X中间线程B把它改成Y又改回XA再CAS时发现还是X误以为自己操作期间没人动过。在业务里这可能导致双重扣款或者重复状态流转。AtomicStampedReference用版本号戳AtomicMarkableReference用一个布尔标记都是为了让CAS能感知到变过又变回来。我的建议是CAS适合那些逻辑短、冲突少、操作快的场景比如计数器、累加器、状态标记一旦关键区逻辑超过十几行别硬撑着搞无锁用并发容器或者Lock反而更稳。3.2 AQS的CLH队列复杂并发原语的统一裁决者AQS即AbstractQueuedSynchronizer是ReentrantLock、Semaphore、CountDownLatch、ReentrantReadWriteLock的共同底座。它内部维护一个volatile int state代表资源状态再维护一个CLH队列用于排队。拿锁失败时线程会被包装成Node通过CAS挂到队列尾部然后进入自旋或阻塞状态前驱节点释放锁后会唤醒后继节点继续抢锁。这套设计把锁抽象成了对state的获取和释放state为0表示无锁加锁就是CAS把0改成1Semaphore的state代表剩余许可数CountDownLatch的state是剩余倒数次数。AQS里公平锁和非公平锁的差异特别能体现算法取舍。ReentrantLock(false)是非公平锁lock时先CAS抢一次不管队列里有没有人排队抢不到再入队这样新线程有机会插队吞吐更高但队尾线程可能长时间等待ReentrantLock(true)是公平锁只要队列里已经有线程在排新来的就老实入队每个线程等待时间更均匀代价是整体吞吐略低。没有哪个一定更好电商秒杀里可能非公平锁更能扛瞬时并发而对响应时间敏感的后台任务公平锁反而更可预期。这种取舍思维比记住某个锁API的意义要大。3.3 线程池调度算法为何线程数量不能拍脑袋ThreadPoolExecutor的调度逻辑可以浓缩成五步提交任务后先判断当前线程数是否小于核心线程数小于就新建线程否则尝试把任务放进阻塞队列队列满了再看线程数是否小于最大线程数小于就新建线程直到上限还是不行就执行拒绝策略。很多人把这个顺序背得滚瓜烂熟却很少想为什么是先加线程、再进队列、最后扩到最大而不是排队更多一点、线程一步到位。原因在于线程是稀缺资源启动和销毁都要成本核心线程数是常备兵力队列是缓冲池最大线程数是极限动员。任务突发时先用队列吸收如果队列都扛不住再扩线程这样才能让线程尽量稳定复用。线程数的估算也有些成熟思路。CPU密集任务经验值就是CPU核数加1IO密集任务可以参考线程数等于CPU核数乘以(1加等待时间除以计算时间)或者直接用核数2倍到4倍之间压测调整。我负责过的一个接口平均IO等待占比很高我把核心线程设成核数的2倍、最大线程数设成4倍配上容量几百的ArrayBlockingQueue一次促销模拟请求的拒绝率从20%直接降到0CPU峰值反而没打满。线程池是典型的数据决定算法不是拍脑袋决定参数。参数含义我的建议corePoolSize常驻线程数CPU密集用核数1IO密集用核数2倍起步maximumPoolSize极限线程数一般为corePoolSize的2倍需压测校正阻塞队列任务的缓冲池必须用有界队列避免内存被打爆拒绝策略兜底手段优先CallerRunsPolicy或记录告警别默认丢弃4. 数据一致性问题的算法级解法从synchronized到分布式4.1 锁膨胀synchronized的优化路径谈到一致性问题最先想到的往往是锁。Java的synchronized经过多年优化已经不是早年那种一竞争就阻塞的重量级锁。JDK 6之后它有一条经典升级链路无锁、偏向锁、轻量级锁、重量级锁。偏向锁假设同步块基本没人竞争线程第一次进入时CAS记录自己的线程ID后续再进只要比对即可省掉加解锁开销一旦出现两个线程竞争偏向锁撤销并升级成轻量级锁轻量级锁靠自旋等锁不阻塞线程只有自旋过度或者竞争进入白热化才会膨胀为重量级锁真正挂起线程。这条链路的本质是让JVM根据竞争烈度自动切换同步算法。这里值得单独提醒偏向锁在JDK 15默认禁用JDK 17之后相关代码被移除。原因也很现实现代服务端大量使用线程池复用线程线程ID和对象头里的偏向记录经常不匹配偏向锁撤销反而成了新开销。所以你不需要把这条老链路当成必须掌握的最新技术但理解它有助于你明白synchronized现在的设计方向能自旋就别阻塞能轻量就别膨胀。日常写代码时只要不在锁里跑长任务或远程调用其实不用过度纠结锁粒度。4.2 乐观锁的version字段与CAS数据库层面的数据一致性我最常用的方案不是悲观锁for update而是乐观锁。核心逻辑是给表加version字段select的时候就带出来update时set versionversion1 where id? and version?如果影响行数是0说明这期间数据被别人改过业务重试。它和CAS在思想上是同构的先比较期望值再执行更新失败重来。相比悲观锁乐观锁在读多写少的场景下几乎没有锁等待成本吞吐高很多。一个经典的例子是库存扣减。新手写法往往是先select stock再判断stock是否大于0然后再update stockstock-1这个流程在高并发下必然超卖因为判断和更新中间隔着线程切换。正确做法是把判断和更新合并成一条原子SQLupdate stock set stock stock - 1 where id ? and stock 0数据库自带的行锁保证这条update要么成功要么失败且不超卖。这段经验让我理解了所谓一致性算法本质就是尽量把检查和动作绑定成原子操作要么不做要么做完整。乐观锁的version、CAS的旧值比对都是为了让这个检查不可分割。4.3 分布式锁与幂等校验的算法思路单机的synchronized和数据库行锁在分布式场景下都拦不住跨进程的并发。这时候常见方案是分布式锁。最简做法是Redis的SET key value NX EX一条命令原子地完成不存在才设置和设置过期时间避免先setnx再expire两步操作之间宕机导致锁永久不释放。生产环境再讲究一点会用Redisson的看门狗自动续期让锁在业务没跑完前不会过期。更严谨的方案是ZooKeeper的临时顺序节点所有请求在同一个锁目录下创建顺序节点序号最小的拿锁其他节点监听前一个节点的删除事件以此实现公平排队和领导者选举。Redis锁胜在简单、性能高ZK锁胜在强一致选择取决于你对极端情况的容忍度。不过在实际业务里分布式锁经常被用错地方。用户重复点击下单按钮你加分布式锁锁住整个下单流程性能差而且容易引起超时更好的做法是幂等校验前端传一个唯一请求IDRedis的setNX先记录这个请求已经处理过数据库再给请求ID加唯一索引兜底重复请求要么直接被拦截要么插入时违反唯一索引被拒。这个方案比锁更轻量而且能覆盖绝大多数重复提交场景。我后来总结出的一句话是能用幂等解决就别用锁能用版本号解决就别停服务。所谓一致性算法最终目的不是让你会用锁而是让你清楚每种锁和并发控制手段各自的约束和适用条件。回头看我这些年啃过的Java知识真正在工作里反复起作用的不是记住了某个集合的复杂度而是学会了用算法的眼光做工程选择ArrayList和LinkedList、快排和稳定归并、CAS和synchronized、乐观锁和悲观锁每一对选项背后都站着数据规模、访问模式、竞争烈度这几个变量。遇到性能问题我先问数据长什么样、读多还是写多、冲突概率高不高把这三个问题答清楚大多数并发和集合相关的坑都能提前避开。这个习惯可能是我最想推荐给后来者的东西。
阅读完成 · 觉得有帮助？
