Java Collections中shuffle与sort的源码级剖析：从算法原理到性能实战

说实话java.util.Collections里的shuffle和sort我用了很多年但真正读懂它们是在一次性能排查之后。当时线上有个调度任务天天超时最后定位到是对一个上千万元素的LinkedList做了排序程序在设计上就没选对数据结构。从那以后我才把眼光从“用完就行”挪到“为什么这么实现”上。这篇文章就把这两个方法从源码到算法、从实战到面试考点一次讲透。1. 这两个方法能干什么为什么值得深挖1.1 一个洗牌、一个排序List 上的两把刀shuffle()的作用是把List里的元素顺序随机打乱sort()的作用是按自然顺序或者自定义比较规则把元素排列整齐。两者都定义在java.util.Collections工具类里走的是静态方法路线只接收List系列接口。虽然名字和用法看起来都很简单但它们干的事儿都不小shuffle背后是经典的 Fisher-Yates 洗牌算法时间复杂度 O(n)是生成随机排列的工程标准sort背后在 Java 8 之后对象数组走的是 TimSort一种稳定、自适应、最坏 O(n log n) 的混合排序。这两个方法不只是“给面试准备的 API”实际业务里抽奖打乱、按钮随机排序、排行榜、数据预处理到处都用得上。1.2 工具类背后的设计套路Collections里几乎全是静态方法sort、shuffle、reverse、rotate、binarySearch、frequency等本质上做的都是“把通用算法从具体数据结构里抽出来”这件事。算法只需要依赖List接口的随机访问能力get、set不关心底层是ArrayList、LinkedList还是Vector。这种思想和设计模式里的策略模式有相似之处数据结构的实现是变化的算法是通用的两者通过接口解耦。我们自己写工具类时也可以照搬这套思路——方法参数尽量面向接口内部再针对具体实现做优化分支。后面看shuffle源码时会发现JDK 自己也是这么干的。2. shuffle 方法拆解源码、算法与使用场景2.1 翻开源码看 Fisher-Yates 洗牌直接上源码JDK 8public static void shuffle(List? list, Random rnd) { int size list.size(); if (size SHUFFLE_THRESHOLD || list instanceof RandomAccess) { for (int i size; i 1; i--) swap(list, i - 1, rnd.nextInt(i)); } else { Object[] arr list.toArray(); for (int i size; i 1; i--) swap(arr, i - 1, rnd.nextInt(i)); ListIterator it list.listIterator(); for (int i 0; i arr.length; i) { it.next(); it.set(arr[i]); } } }代码很短但信息量很大。SHUFFLE_THRESHOLD的值是 5。当列表小于 5 个元素或者list实现了RandomAccess接口时直接在原列表上做交换否则先把所有元素拷贝到对象数组里洗完再一次性写回列表。之所以要区分是因为LinkedList的get(index)不是 O(1)而是在链表里逐个遍历。如果直接在它上面循环swap(list, i - 1, rnd.nextInt(i))每次取值都是 O(n)整个洗牌直接退化到 O(n²)数据一大会非常难受。这一段设计很值得学RandomAccess是个空接口纯粹当标记用ArrayList实现了它LinkedList没有。JDK 在底层就是用这种标记接口判断“这个 List 能不能高效随机访问”然后走不同的分支。我们在写自己的通用算法时面对可能有多种实现的数据结构也应该先问一句“它支持高效随机访问吗”再做分支取舍。换个重载不传Random的方法内部会 new 一个默认的Random实例public static void shuffle(List? list) { Random rnd r; if (rnd null) { r rnd new Random(); } shuffle(list, rnd); }2.2 为什么从后往前洗数学上才能保证均匀先看核心循环for (int i size; i 1; i--) swap(list, i - 1, rnd.nextInt(i));rnd.nextInt(i)返回 [0, i-1] 区间内的随机整数。所以第i-1个位置会和[0, i-1]中任意一个位置交换。等到下一轮i减一刚才固定下来的位置就不再参与后续交换。这就是 Fisher-Yates 算法也叫 Knuth Shuffle的标准形态。理解它为什么均匀可以从最后一个位置开始想第一轮最后一个位置等概率地和0..size-1中的任何一个位置交换所以最后一个位置被安排成任意元素的概率都是1/n。第二轮排在倒数第二的位置从剩余n-1个元素里等概率选一个概率是(n-1)/n * 1/(n-1) 1/n。依此类推每一个位置上出现每一个原始元素的概率都正好是1/n所有排列出现的概率是1/n!。换个思路也能证明这个算法生成的排列总数是n * (n-1) * (n-2) * ... * 1 n!而且树形结构里每个叶子对应的路径权重完全一样。我见过有人图省事用“循环从 0 到 n-1随机交换两个位置”的方式洗牌。这种 naive 实现会产生大量重复排列某些排列出现的概率明显高于另一些也就是有偏的。如果做抽奖这类对公平性要求高的场景这种偏差会造成实打实的脏数据。Fisher-Yates 的“从后往前逐个固定”是正确做法别再凭直觉乱写了。2.3 shuffle 实际用到哪些地方游戏发牌斗地主、德州扑克、卡牌对战整副牌一次shuffle然后按顺序发牌。数据预处理机器学习训练前打乱数据集顺序避免模型学到样本间的顺序偏差。抽奖与点名名单打乱后按顺序取公平且逻辑简单。A/B 测试分组用户列表洗牌后按比例切分到实验组和对照组。随机排列生成算法题或者蒙特卡洛模拟里用来产生随机序列。一个特别有用的细节shuffle是原地修改list不会返回新列表。如果你不想动原来的数据得先new ArrayList(original)拷贝一份再洗。这地方真的很多人踩坑尤其是从函数式语言切到 Java 的同事总以为会返回一个新集合。3. sort 方法拆解底层排序、比较器与稳定性3.1 Collections.sort 和 List.sort 到底是什么关系Java 8 之后List接口增加了默认方法sortdefault void sort(Comparator? super E c) { Object[] a this.toArray(); Arrays.sort(a, (Comparator) c); ListIteratorE i this.listIterator(); for (Object e : a) { i.next(); i.set((E) e); } }而Collections.sort的实现只有一行public static T void sort(ListT list, Comparator? super T c) { list.sort(c); }也就是说Collections.sort(list)最终调用的还是list.sort()。ArrayList重写了sort方法直接调Arrays.sort对内部数组排序少了一次“拷贝到新数组再写回”的开销Override public void sort(Comparator? super E c) { final int expectedModCount modCount; Arrays.sort((E[]) elementData, 0, size, c); modCount expectedModCount; }注意这里连modCount都帮你修复了原因是不希望排序过程中修改了元素却被fail-fast机制误判为并发修改。所以实际工作里用Collections.sort还是list.sort效果等价区别只是list.sort更“面向对象”一点Collections.sort更“工具类”一点。JDK 官方保留两套 API 是为了兼容老代码新代码直接用list.sort就行。3.2 对象排序为什么用 TimSort基本类型为什么用双轴快排到了Arrays.sort这层Java 8 之后有一个重要分流基本类型数组排序走的是DualPivotQuickSort双轴快速排序对象数组排序走的是TimSortTimSort 是 Tim Peter 在 Python 里率先使用的排序算法后来被 Java 引入。它的核心思路是“利用数据中天然存在的有序片段”。算法会先扫描数组把一段连续递增或严格递减的区间识别成一个 run短 run 用二分插入排序扩展成长 run然后按规则把这些 run 合并。整个过程是稳定的最好情况可以达到 O(n)数据本身有序最坏情况 O(n log n)还保证稳定性。那为什么对象排序不用快排因为稳定性。快排是不稳定的等值元素在排序后可能颠倒相对顺序。对于引用类型的对象用户通常希望相同 key 的对象保持原来的先后顺序比如先按时间排序再按优先级排序时相同优先级的时间顺序不能被搞乱。归并排序这一族天生稳定能保证这个性质。基本类型排序为什么无所谓因为int和int之间没有“身份”区别两个 5 谁前谁后一点不重要所以用更快的双轴快排极端情况下比稳定归并省内存、省拷贝。这个知识点几乎是 Java 面试必问的一个小点核心就一句话对象排序要求稳定所以走 TimSort基本类型不要求稳定所以走双轴快排。3.3 Comparable 和 Comparator 怎么选先说结论Comparable是让类“自己说自己怎么比”。比如商品类实现ComparableProduct定义默认的价格比较顺序。这种排序规则是类型的固有属性写进类里是合理的。Comparator是“外部定义一套比较规则”。比如同一个商品类这次按价格排下次按销量排再下次按上架时间排。这些规则不应该写死在商品类里而是每次调用时单独传。什么时候用哪个规则几乎不变、是该对象的核心属性时用Comparable规则多变、按场景切换时用Comparator。从设计层面讲Comparator灵活得多也符合开闭原则——给已有类扩展排序方式不需要修改类本身。Java 8 之后Comparator还有一堆链式方法用起来非常顺手users.sort(Comparator.comparing(User::getAge) .thenComparing(User::getName));这个组合“按年龄升序年龄相同按姓名升序”的写法只花了一行。3.4 从大到小排序的几种写法先说最常用的几种// 方式一reverseOrder直接反转自然顺序 Collections.sort(list, Collections.reverseOrder()); // 方式二Collections.reverseOrder(Comparator)反转自定义比较器 list.sort(Collections.reverseOrder(Comparator.comparing(User::getAge))); // 方式三Comparator 自带 reversed() list.sort(Comparator.comparing(User::getAge).reversed()); // 方式四lambda 里直接用 compare 方法 list.sort((a, b) - Integer.compare(b.getAge(), a.getAge()));有一个坑必须提别在 Comparator 里写(a, b) - b - a。虽然看起来没问题但当a是负数很大、b是正数很大的时候减法结果会溢出变成错误的正数整个排序结果直接错乱。正确的 int 比较永远用Integer.compare(a, b)或者用包装类型自带的compareTo。这个坑我见过不止一次落到线上别觉得“怎么会这么巧”数据量一大什么边界都会碰到。另外说一句Collections.reverse(list)是反转顺序不是排序。想要“从大到小”必须是“先排序再倒序”或者直接用上面的比较器写法先把排序搞定其他操作不要混在一起。4. 实操完整示例与性能参考4.1 用扑克牌把 shuffle 和 sort 串起来用一个牌类把两个方法都用上class Card implements ComparableCard { private final String suit; // 花色 private final int rank; // 点数 Card(String suit, int rank) { this.suit suit; this.rank rank; } String getSuit() { return suit; } int getRank() { return rank; } Override public int compareTo(Card o) { return Integer.compare(this.rank, o.rank); } Override public String toString() { return suit rank; } }生成整副牌洗牌发牌然后对玩家的手牌排序ListCard deck new ArrayList(); for (String suit : new String[]{♠, ♥, ♣, ♦}) { for (int rank 1; rank 13; rank) { deck.add(new Card(suit, rank)); } } // 洗牌 Collections.shuffle(deck); // 三个人每人 5 张 ListCard player1 new ArrayList(deck.subList(0, 5)); ListCard player2 new ArrayList(deck.subList(5, 10)); ListCard player3 new ArrayList(deck.subList(10, 15)); // 对手牌排序 Collections.sort(player1); Collections.sort(player2); Collections.sort(player3); System.out.println(player1);这里两个细节值得注意第一subList返回的是原列表的视图直接用deck.subList(0, 5)排序会连原列表对应区段一并排序所以发给玩家前必须new ArrayList()拷贝成独立列表。这是subList的经典陷阱很多线上诡异 Bug 由它引起。第二Card实现了Comparable才可以直接Collections.sort。如果没实现编译阶段不会报错但运行时会抛ClassCastException: Card cannot be cast to Comparable。这也是常见运行期错误之一。4.2 自定义对象的复杂排序再看一个更贴合业务场景的例子用户对象有年龄、姓名、注册时间三个字段需求是先按年龄排序年龄相同按姓名再相同按注册时间倒序ListUser users ...; users.sort(Comparator .comparing(User::getAge) .thenComparing(User::getName) .thenComparing(Comparator.comparing(User::getRegisterTime).reversed()));链式比较器可读性好执行效率和手写多重if差不多但代码量少一个数量级。实现起来也不复杂Comparator内部分别比较每一项thenComparing只有在前面所有项都相等时才继续比较下一项。4.3 性能参考100 万条数据跑一次多久我在自己机器上8 核 i716G 内存JDK 11用ArrayListInteger跑了简单对比。100 万个IntegerCollections.shuffle大约 30-50msCollections.sort大约 200-300ms数据量到 1000 万时shuffle大概 400-600mssort大概 2-3s。数字仅供参考不同机器差异很大但量级关系是稳定的shuffle是 O(n)sort是 O(n log n)数据翻 10 倍时排序耗时大概翻 20 多倍而洗牌只翻 10 倍左右。排序对数据量增长更敏感所以数据量上去后优先考虑是不是可以提前有序、是不是走数据库ORDER BY而不是把所有数据拉进 JVM 里硬排。LinkedList上排序虽然没有直接变成 O(n²)JDK 内部还是先转数组但多了一次到数组的拷贝和写回相同数据量下比ArrayList慢不少。工具类是为通用场景设计的但不代表所有数据结构上都一样快。这个意识比死记源码重要。5. 面试考点与高频问题5.1 高频问题速查表准备面试时我建议直接把下面这组问题背下来问题应该答到的核心点Collections.sort()底层用的什么排序Java 8 之后对象数组用 TimSort稳定、O(n log n)基本类型数组用双轴快排shuffle()的算法和复杂度Fisher-Yates / Knuth ShuffleO(n)原地洗牌为什么对象排序不用快排快排不稳定对象排序要求相等元素保持原顺序Collections.sort和list.sort的关系Collections.sort内部调list.sortArrayList重写后直接调Arrays.sortComparable 和 Comparator 的区别一个类内实现自然排序一个外部传比较策略Comparator 更灵活、不侵入类从大到小怎么排reverseOrder()、Comparator.reversed()、或者Integer.compare(b, a)shuffle 传固定 Random 种子会怎样洗牌结果可复现适合单元测试5.2 场景题的答题思路面试官爱问“有一组对象要排序你怎么做”。别上来就答 API分几步讲先问两个问题一是这个列表会不会并发修改二是排序字段是不是固定的业务规则。并发问题用synchronizedList加外部锁或者CopyOnWriteArrayList规则多变用Comparator规则固定考虑实现Comparable。然后说排序本身。Comparator.comparing(...).thenComparing(...)搞不定的时候再讲手写Comparator接口。最后补一句稳定性“如果先按性别排再按年龄排重复性别之间的相对顺序要保持我会选择稳定的排序实现而 Java 的对象排序默认就是稳定的。”场景题重点考察的是思维链路不是背 API。从并发、稳定性、可维护性几个维度都提到基本就能过关。5.3 手写排序 vs 直接调库面试里手写冒泡排序是为了考基本功但实际开发里永远优先用现成排序。同样是一组数据冒泡排序 O(n²) 在 10 万数据上可能秒级完成而 TimSort 是几十毫秒的事。更关键的是手写排序要处理稳定性、边界、比较器异常一堆问题调库等于把这些问题都交给 JDK 验证过的代码。能用现成的高质量算法绝不自造轮子这是工程常识面试时也应该把这个判断讲出来。6. 实战踩坑记录这些问题我全遇到过6.1 在不可变 List 上排序直接抛异常List.of()、Collections.emptyList()、Collections.unmodifiableList()返回的列表都是不可修改的调用sort()或shuffle()会抛UnsupportedOperationException。但一个容易误判的边界是Arrays.asList()。它返回的是固定大小的列表底层是数组不能add、不能remove但可以set。而sort和shuffle的原地操作本质上只依赖set所以在Arrays.asList()的结果上跑这两个方法是没问题的。我的建议是凡是碰到“不可变集合”这类概念先分清是“完全不可变”还是“长度固定但元素可变”。前者碰都不能碰后者可以安全地洗牌和排序。6.2 Comparator 违反传递性引发的诡异报错Comparator必须满足传递性如果a b且b c必须推出a c。如果比较器逻辑写乱了数据量不大时可能没事数据量一大TimSort 内部合并时会检测到“比较结果自相矛盾”直接抛java.lang.IllegalArgumentException: Comparison method violates its general contract!有一次在业务代码里见过这种报错。起因是有人写了一个“既想按类型优先级、又想按时间、还想把某些状态放到最后”的复杂比较器几个if分支没处理好导致compare(a, b)和compare(b, c)组合起来和compare(a, c)矛盾。数据量小时侥幸没触发一到线上全量数据就炸了。排查思路把这个比较器单独抠出来写一个随机数据的小测试用Collections.sort跑几万次很快就能复现。修复原则就一条比较器必须定义严格全序任何两个元素比较结果必须一致且满足传递性。6.3 固定随机种子带来的可复现性Collections.shuffle(list, new Random(42))会让每次洗牌结果完全一样。这在生产代码里容易被当成 Bug但在单元测试里恰恰是有用的特性测试数据打乱后顺序固定用例可重复。也有反面教训。一个同事为了“让每次抽奖结果都不同”用了new Random()但没控制种子发现重启服务后同一批人抽奖顺序相似以为 Random 出了问题其实是因为new Random()的默认种子跟纳秒时间有关连续多次调用时间间隔太短种子相近导致序列相似。解决办法很简单程序启动时创建一个全局Random实例后续所有随机行为都从它取或者用ThreadLocalRandom.current()。不要每次调用都new Random()。6.4 多线程并发下 synchronizedList 的误用很多人以为Collections.synchronizedList(list)之后对列表的sort、shuffle就线程安全了。这个理解是错的。synchronizedList只是把单个方法加锁而sort和shuffle是“读多个元素、写多个元素”的复合操作整个操作过程中并不是原子的。两个线程同时对同一个synchronizedList调用shuffle底层 swap 会交错执行最终列表状态完全不可控。正确做法是外部加锁ListString list Collections.synchronizedList(new ArrayList()); synchronized (list) { Collections.shuffle(list); }或者干脆把数据拷贝出来洗完再synchronized放回去。这个坑在“调度系统多线程并发重排任务列表”这类场景里很容易出现我印象很深。6.5 大列表上 shuffle 的 LinkedList 陷阱前文源码里已经说过JDK 对LinkedList洗牌时会先转Object[]洗完再写回。这个处理保证了功能正常但额外的 toArray 遍历写回在数据量大时还是很明显。我实测过 100 万条数据ArrayList的 shuffle 只要几十毫秒LinkedList的 shuffle 接近一倍耗时而且 GC 压力更大因为中间多产生了一个大数组对象。业务上如果既要频繁排序洗牌、又要频繁中间插入删除那就得权衡一下数据结构了。纯从排序场景看ArrayList始终是更合理的选择。这也就是为什么我建议“能用 ArrayList 就别用 LinkedList除非你在大量做队头队尾操作”。写在最后shuffle和sort看起来就是两行 API但作为 Java 工程师把它们背后的随机算法、排序稳定性、比较器设计和数据结构匹配度搞清楚写出来的代码质量完全不一样。我在实际项目里最直接的感受是读懂源码之后遇到LinkedList排序性能差、固定种子导致测试不稳定、比较器违反契约这类问题基本不用查资料就能定位方向排查时间从几小时缩短到十几分钟。最后分享一个小技巧把Collections.sort和Collections.shuffle当成你检验“是否真的理解 List 家族”的试金石——能讲清为什么Arrays.asList可以排序而List.of不行为什么对象排序稳定而基本类型排序无所谓为什么shuffle要检查RandomAccess你对 Java 集合框架的理解就比绝大多数人扎实了。这套基本功比记住多少个 API 都值钱。