1. 从一个真实需求说起：为什么“随机取n个不重复”没那么简单

做Java开发这些年，被问得最多的一类问题不是框架怎么搭、性能怎么调，反而是这种看起来特别“小”的需求：从一堆数据里随机挑几个不重复的出来。比如抽奖系统要从一万个用户里抽十个中奖者，比如考试系统要从题库里随机抽五十道题组卷，比如推荐模块要从候选池里随机选几个展示位。乍一听这需求简单得不行，Random一new，循环一跑，完事。但真动手写过的都知道，坑全藏在“不重复”这三个字里。

我见过太多项目里随手写的随机选取代码，测试环境数据量小的时候跑得好好的，一上生产、数据量一大，要么性能直接崩掉，要么选出来的结果分布不均匀，要么在并发场景下出现重复。更麻烦的是，这类问题往往不会立刻暴露，等到业务方反馈“怎么老是抽到同一批人”的时候，回头查代码才发现根子在这儿。所以这个标题虽然朴素，但它背后牵扯的是算法选型、数据结构、性能边界、并发安全这一整套东西，值得认真拆一拆。

这篇文章我打算按实际做项目的思路来写：先讲清楚有哪几种主流方案、各自的适用边界在哪，再深入到具体实现和参数计算，然后把我自己踩过的坑和排查经验整理出来。不管你是刚学Java的新手，还是写了几年业务代码想补补基础的老手，应该都能从里面找到能直接抄作业的东西。核心关键词就三个：随机数、指定范围、不重复选取，全文围绕它们展开。

2. 方案选型：四种主流思路的取舍逻辑

2.1 先明确问题的三个边界条件

在动手写代码之前，有几个问题必须先问清楚，因为它们直接决定你该用哪种方案。第一个是数据范围有多大，是从100个数里选10个，还是从一千万个数里选100个，量级不同方案完全不一样。第二个是选取比例有多高，选10个和选9990个（从一万个里）是两种截然不同的场景，前者是“稀疏选取”，后者是“密集选取”。第三个是数据源是什么形态，是一个连续的整数区间，还是一个已经存在的List或数组，这决定了你能不能直接用下标做文章。

很多人写代码出问题，就是因为没分清这三个边界，拿一个适合小数据量的方案去处理大数据量，或者拿一个适合稀疏选取的算法去处理密集选取。下面我把四种主流方案摆出来，逐一分析它们的适用场景和背后的取舍。

2.2 四种方案对比与选择依据

这张表是我自己总结的，实际选型时我一般按这个顺序判断：先看数据源是不是流式的，是就用蓄水池抽样；不是的话看选取比例，比例超过30%左右我倾向洗牌法，低于这个值用集合标记或暴力重试。这里说的30%不是绝对标准，是个经验阈值，因为洗牌法的成本是固定的O(N)，而集合标记法的期望成本跟n相关，两者在某个点会交叉。

注意：暴力重试法在选取比例接近范围上限时会急剧退化。比如从100个数里选99个，最后几个数的命中概率只有百分之几，期望重试次数会飙升到几百次，这种场景千万别用它。

2.3 为什么我优先推荐“集合标记+范围收缩”

在范围是连续整数、且选取比例不高的情况下，我个人最常用的是集合标记法的一个变体，我管它叫“范围收缩法”。思路是这样的：维护一个待选范围的上下界，每次随机取一个下标，取完之后把该位置的值和范围末尾的值交换，然后把范围缩小一位。这样每次选取都是O(1)，总共n次选取就是O(n)，而且天然不会重复，因为被选走的位置已经被换到末尾、排除在范围之外了。

这个思路的好处是它不需要额外的Set去判重，判重这个动作本身在数据量大时是有开销的。它用一个数组内部的交换就完成了“标记已选”的功能，非常巧妙。代价是它会修改原数组的顺序，如果你不能动原数据，就得先拷贝一份。这个取舍在实际项目里通常是划算的，因为拷贝一个数组的成本远低于维护一个Set的成本。

3. 核心实现细节：从原理到可运行代码

3.1 范围收缩法的完整实现与逐行解析

先把最推荐的方案代码贴出来，然后逐行讲清楚每一步在干什么。

import java.util.Arrays; import java.util.Random; public class RandomPicker { /** * 从 [min, max] 闭区间内随机选取 count 个不重复的整数 * @param min 范围下界（含） * @param max 范围上界（含） * @param count 需要选取的个数 * @param random 随机数发生器，便于外部控制种子 * @return 选取结果数组 */ public static int[] pickUnique(int min, int max, int count, Random random) { if (min > max) { throw new IllegalArgumentException("下界不能大于上界"); } long rangeSize = (long) max - min + 1; if (count < 0 || count > rangeSize) { throw new IllegalArgumentException("选取个数超出范围容量"); } // 把范围映射到 0..rangeSize-1 的连续下标数组 int[] pool = new int[(int) rangeSize]; for (int i = 0; i < pool.length; i++) { pool[i] = min + i; } int[] result = new int[count]; int bound = pool.length; for (int i = 0; i < count; i++) { // 在 [0, bound) 中随机取一个下标 int idx = random.nextInt(bound); result[i] = pool[idx]; // 把选中的位置和当前范围末尾交换，然后收缩范围 bound--; pool[idx] = pool[bound]; } return result; } }

这段代码有几个细节值得展开说。第一，我用long rangeSize来算范围大小，是为了防止max - min + 1在极端情况下整型溢出。比如min是Integer.MIN_VALUE、max是Integer.MAX_VALUE的时候，直接算会溢出成负数，用long接一下再判断就安全了。第二，random.nextInt(bound)里的bound是动态收缩的，第一次是pool.length，第二次是pool.length-1，以此类推，保证每次都在“剩余未选”的范围内取。第三，交换那一步pool[idx] = pool[bound]，注意顺序是先bound--再赋值，这样被换过来的元素正好落在收缩后的范围末尾，逻辑上是自洽的。

3.2 随机源的选择：Random、ThreadLocalRandom还是SecureRandom

选哪个随机源，很多人不在意，随手就new Random()。但在实际项目里这个选择是有讲究的。java.util.Random是线程安全的，它内部用CAS更新种子，多线程竞争激烈时性能会下降。ThreadLocalRandom是JDK7引入的，每个线程独立一个实例，没有竞争，在并发场景下性能明显更好，我一般在高并发业务里优先用它。

import java.util.concurrent.ThreadLocalRandom; // 单线程或并发场景都适用，性能优于共享的 Random int idx = ThreadLocalRandom.current().nextInt(bound);

至于SecureRandom，它是密码学安全的随机源，生成速度比前两者慢一个数量级，除非是抽奖、发券这类对不可预测性有强要求的场景，否则没必要用。我见过有人为了“更随机”在所有地方都用SecureRandom，结果在批量选取时性能直接掉下来，这是典型的过度设计。

提示：如果你需要可复现的随机结果（比如测试用例），用new Random(固定种子)；如果只是业务随机，用ThreadLocalRandom就够了。

3.3 当数据源不是连续整数时怎么改

上面的实现假设数据源是连续的整数区间。如果数据源是一个已有的List，比如从用户列表里随机选，思路是一样的，只是把“下标数组”换成“元素数组”，交换的也是元素本身。

public static <T> List<T> pickUniqueFromList(List<T> source, int count, Random random) { int size = source.size(); if (count < 0 || count > size) { throw new IllegalArgumentException("选取个数超出集合容量"); } // 拷贝一份，避免修改原集合 List<T> pool = new ArrayList<>(source); List<T> result = new ArrayList<>(count); int bound = size; for (int i = 0; i < count; i++) { int idx = random.nextInt(bound); result.add(pool.get(idx)); bound--; pool.set(idx, pool.get(bound)); } return result; }

这里用new ArrayList<>(source)做了一次浅拷贝，元素本身还是引用同一批对象，只是容器是新的，所以不会影响原集合的顺序。如果你的源数据是数组，逻辑完全一样，把get/set换成下标访问即可。这个泛型版本我在好几个项目里直接复用，基本没出过问题。

4. 性能实测与参数计算：数据量到底多大才需要换方案

4.1 一次实测：不同方案在不同数据量下的表现

光讲理论不够，我做过一组实测，环境是普通的开发机，JDK17，分别测了暴力重试法、范围收缩法、洗牌法在几种数据量下的耗时。数据是多次运行取的平均值，单位是毫秒。

从这组数据能看出几个规律。暴力重试法在选取比例低的时候还能用，一旦比例上去就彻底崩了，10000选5000直接跑到320毫秒，而范围收缩法只要1.2毫秒，差了将近三百倍。洗牌法在范围大、选取少的时候反而吃亏，因为它不管选几个都要打乱整个数组，100万选100要45毫秒，而范围收缩法只要6毫秒。范围收缩法在几乎所有场景下都表现稳定，这也是我推荐它的核心原因。

4.2 内存占用的估算方法

除了时间，内存也得算。范围收缩法需要一份和范围等大的数组，如果范围是100万，一个int数组就是4MB，这个开销在大多数场景下可以接受。但如果范围是一亿，那就是400MB，这时候就得考虑别的方案了。蓄水池抽样就是为这种场景准备的，它只需要n大小的额外空间，跟范围总量无关。

// 蓄水池抽样：适用于范围极大或数据流式到达的场景 public static int[] reservoirSample(int min, int max, int count, Random random) { int[] reservoir = new int[count]; long rangeSize = (long) max - min + 1; // 先填满前 count 个 for (int i = 0; i < count; i++) { reservoir[i] = min + i; } // 从第 count+1 个开始，按概率替换 for (long i = count; i < rangeSize; i++) { long j = nextLong(random, i + 1); if (j < count) { reservoir[(int) j] = (int) (min + i); } } return reservoir; } private static long nextLong(Random random, long bound) { long r = random.nextLong(); long m = bound - 1; if ((bound & m) == 0L) { r &= m; } else { for (long u = r >>> 1; u + m - (r = u % bound) < 0L; u = random.nextLong() >>> 1); } return r; }

蓄水池抽样的核心是：前count个元素直接进池子，从第count+1个开始，每个元素以count/i的概率替换池子里的某个元素。数学上可以证明，遍历结束后每个元素留在池子里的概率都是相等的。这个算法的空间复杂度是O(count)，跟范围总量无关，所以范围再大也不怕。代价是它必须遍历整个范围，时间复杂度是O(rangeSize)，范围特别大的时候时间成本高。

4.3 怎么根据业务场景选参数

选型的时候我一般按这个决策流程走：先看范围总量，超过一千万且选取个数不多，优先蓄水池抽样；范围在一千万以内，看选取比例，比例低于30%用范围收缩法，高于30%用洗牌法。这个30%的阈值不是死的，实际还要看你对内存的敏感程度和对原数据能否修改的约束。

还有一个容易被忽略的点是随机数的质量。范围收缩法里每次nextInt(bound)的bound是变化的，如果bound不是2的幂，Random.nextInt内部会做拒绝采样来保证均匀性，这个开销在小数据量下可以忽略，但在百万级选取时会有累积影响。实测下来这个影响在5%以内，一般业务可以接受，如果对性能极度敏感，可以考虑用位运算优化，但代码复杂度会上升，不太划算。

5. 常见问题与排查技巧实录

5.1 为什么我的随机结果看起来“不够随机”

这是被问得最多的一个问题。现象是：明明用了随机数，但选出来的结果总感觉集中在某几个值上。排查下来通常有三个原因。第一个是随机源被重复初始化，比如在循环里每次都new Random()，而new Random()默认用当前时间做种子，循环执行太快的话种子几乎一样，导致每次生成的序列相同。解决办法是把Random实例提到循环外面，或者用ThreadLocalRandom。

第二个原因是取模偏差。有些人喜欢用random.nextInt() % bound来取范围，这种做法在bound不能整除Integer.MAX_VALUE时会导致某些值被选中的概率略高。正确做法是直接用random.nextInt(bound)，它内部已经处理了均匀性问题。

第三个原因是数据本身的问题，比如源数据里某些值重复出现，那选出来自然看起来集中。这种情况要先对源数据去重，或者接受“按权重随机”的语义。

5.2 并发场景下出现重复选取怎么办

多线程同时调用选取方法时，如果共享了同一个可变状态（比如共享的pool数组），就会出现数据竞争，导致选出的结果重复或错乱。我遇到过一次线上问题，就是两个线程同时操作同一个pool，一个线程刚交换完，另一个线程读到了中间状态，结果选出了重复元素。

解决办法有两个方向。一是每次调用都拷贝一份独立的pool，各线程互不干扰，代价是内存开销翻倍。二是用ThreadLocal给每个线程一份独立的pool，适合pool本身不大、线程数固定的场景。如果选取逻辑是纯函数式的（不修改共享状态），那天然就是线程安全的，范围收缩法只要保证pool是方法内局部变量就没问题。

注意：ThreadLocalRandom本身是线程安全的，但如果你把它的实例存到静态变量里跨线程共享，就失去了它的设计意义，还是老老实实每次ThreadLocalRandom.current()获取当前线程的实例。

5.3 常见问题速查表

5.4 几个我踩过的坑

第一个坑是边界值处理。有一次需求是从1到100选100个，也就是全选，我的代码里count > rangeSize判断写成了>=，结果全选场景直接抛异常。后来改成count > rangeSize才对。这种边界一定要写单元测试覆盖，我现在的习惯是至少测四个case：选0个、选1个、选全部、选超出范围。

第二个坑是整型溢出。前面提过max - min + 1的溢出问题，我是在一次处理时间戳范围选取时踩到的，min和max都是很大的long值，相减直接溢出成负数，导致数组长度计算出错。后来所有涉及范围计算的地方我都用long先接一下。

第三个坑是随机性验证。有次业务方质疑抽奖结果不公平，我写了个小脚本跑十万次选取，统计每个元素被选中的频率，画了个分布图，确认频率偏差在合理范围内才说服对方。这个验证方法后来成了我的标准动作，涉及抽奖、发券这类敏感场景，我都会先跑一遍分布验证。

6. 几个进阶场景的扩展思路

6.1 带权重的随机选取

实际业务里经常不是等概率选取，而是带权重的。比如抽奖，一等奖概率低、参与奖概率高。这种场景就不能用上面的等概率方案了，得用别名法或者前缀和+二分查找。前缀和方案的思路是把权重累加成一个数组，随机取一个总权重范围内的值，然后二分查找落在哪个区间。这个方案实现简单，O(log n)的查找复杂度，在权重数量不多时完全够用。

// 前缀和 + 二分查找实现带权重随机 public static int weightedPick(int[] weights, Random random) { int total = 0; int[] prefix = new int[weights.length]; for (int i = 0; i < weights.length; i++) { total += weights[i]; prefix[i] = total; } int target = random.nextInt(total); int lo = 0, hi = prefix.length - 1; while (lo < hi) { int mid = (lo + hi) >>> 1; if (prefix[mid] < target + 1) { lo = mid + 1; } else { hi = mid; } } return lo; }

带权重选取如果要保证不重复，逻辑会复杂一些，通常的做法是选一个、把该元素权重置零、重新计算前缀和，重复n次。数据量小的时候可以这么做，数据量大就得用更复杂的算法，比如加权蓄水池抽样。

6.2 从超大范围里选少量数据

前面说的蓄水池抽样是标准解法，但它有个前提是范围可遍历。如果范围大到无法遍历，比如从所有可能的64位整数里选10个，那就得用随机数生成+去重的思路，本质上退化成暴力重试法，但因为范围极大，重复的概率极低，实际表现反而很好。这种场景下用Set判重，选10个几乎不会有碰撞，性能完全没问题。

6.3 结果需要保持原顺序怎么办

范围收缩法会打乱顺序，如果业务要求选出的结果保持原来的相对顺序，那就不能直接用交换法。解决办法是选完之后对结果排个序，或者用TreeSet收集结果。排序的成本是O(n log n)，n是选取个数，通常不大，可以接受。如果选取个数很大，那就得权衡一下，看业务是否真的需要保序。

7. 写在最后的一点个人体会

这套随机选取的东西，我从入行到现在反复用过很多次，每次遇到新场景都会重新想一遍选型。最大的体会是：没有银弹，只有匹配。范围收缩法在大多数场景下表现优秀，但它不是万能的，范围极大时它内存吃不消，需要保序时它得额外排序，带权重时它直接不适用。真正靠谱的做法是把这几种方案的边界都摸清楚，遇到具体需求时能快速判断该用哪个。

另外就是测试要跟上。随机相关的代码最容易出隐蔽bug，因为它的错误往往不是必现的，而是概率性的。我的习惯是给每个选取方法都写分布验证的测试，跑个几万次统计频率，偏差超过阈值就报警。这个习惯帮我提前发现过好几次种子重复和取模偏差的问题，省了不少线上排查的功夫。

如果你正在做类似的功能，建议先把数据范围和选取比例这两个参数确定下来，然后对照第2节的表格选方案，再用第3节的代码改一改就能用。真遇到性能问题，第4节的实测数据可以帮你快速定位是不是选型的问题。这套流程我用了很多次，基本没翻过车。