Java中高效向HashSet添加随机整数的方法？添加2000万整数耗时过长求优化

首先，你当前代码耗时极长的核心原因是HashSet默认的初始容量太小，导致频繁扩容。HashSet底层依赖HashMap实现，默认初始容量仅为16，负载因子是0.75——当元素数量达到容量×负载因子时，就会触发扩容（容量翻倍），而每次扩容都需要重新哈希所有已有元素，这会带来巨大的性能开销，尤其是当你要添加2000万元素时，这个过程会重复几十次，直接拖慢整体速度。

下面针对你的需求（不管是连续整数还是随机不重复整数），给出具体的优化方案：

一、如果是添加连续整数（你的代码当前逻辑） #

如果只是要把1到2000万的连续整数存入Set，HashSet其实不是最优选择——BitSet会更高效，它用位存储数据，2000万元素仅占用约2.5MB内存（相比HashSet的几百MB），操作速度也更快。不过如果业务必须用HashSet，可以这样优化：

final int SET_SIZE = 20000000;
// 计算初始容量：目标元素数 / 负载因子 + 1，确保不会触发扩容
Set<Integer> set1 = new HashSet<>((int) (SET_SIZE / 0.75f) + 1, 0.75f);
for (int i = 1; i <= SET_SIZE; i++) {
    set1.add(i);
}

如果可以改用BitSet，代码如下（需要判断存在性时更高效）：

final int SET_SIZE = 20000000;
BitSet bitSet = new BitSet(SET_SIZE + 1);
for (int i = 1; i <= SET_SIZE; i++) {
    bitSet.set(i);
}
// 若必须转换成HashSet，可批量添加（但会占用较多内存）
Set<Integer> set = new HashSet<>((int)(SET_SIZE/0.75f)+1);
for (int i = bitSet.nextSetBit(0); i != -1; i = bitSet.nextSetBit(i+1)) {
    set.add(i);
}

二、如果是添加2000万个不重复的随机整数 #

除了优化HashSet的初始容量，还要解决随机数生成效率和重复率的问题：

1. 优化HashSet初始化 #

同样先指定足够大的初始容量，避免扩容。

2. 用更高效的随机数生成器 #

ThreadLocalRandom比传统的Random更高效——它避免了Random的线程安全锁开销，单线程下性能提升明显。

3. 降低随机数重复概率 #

如果随机数范围太小，会导致大量重复值，add操作需要反复检查元素是否存在，拖慢速度。建议把随机数范围设置为目标数量的1.5_{2倍（比如2000万的话，范围设为1}3000万）。

代码示例：

final int SET_SIZE = 20000000;
int initialCapacity = (int) (SET_SIZE / 0.75f) + 1;
Set<Integer> set = new HashSet<>(initialCapacity, 0.75f);
ThreadLocalRandom random = ThreadLocalRandom.current();

// 设置足够大的随机数范围，减少重复
int maxRandom = SET_SIZE * 2;
while (set.size() < SET_SIZE) {
    int num = random.nextInt(1, maxRandom + 1);
    set.add(num);
}

进阶：洗牌法避免重复 #

如果需要严格不重复的随机数，且范围刚好是目标数量（比如生成2000万个不重复的随机数，范围就是1~2000万），可以用Fisher-Yates洗牌算法先生成随机序列，再批量添加到Set：

final int SET_SIZE = 20000000;
int[] nums = new int[SET_SIZE];
// 先填充连续整数
for (int i = 0; i < SET_SIZE; i++) {
    nums[i] = i + 1;
}
// Fisher-Yates洗牌生成随机序列
ThreadLocalRandom random = ThreadLocalRandom.current();
for (int i = nums.length - 1; i > 0; i--) {
    int j = random.nextInt(i + 1);
    // 交换元素
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
// 批量添加到HashSet
Set<Integer> set = new HashSet<>((int)(SET_SIZE/0.75f)+1, 0.75f);
for (int num : nums) {
    set.add(num);
}

关键优化点总结 #

• 避免扩容：初始化时计算好足够的初始容量，这是提升性能最明显的一步。
• 选择合适的工具：连续整数用BitSet，随机数用ThreadLocalRandom。
• 减少重复检查：随机数场景下扩大范围，或用洗牌法直接生成无重复序列。

内容的提问来源于stack exchange，提问作者One Any