java - 产生随机数字时，为什么比人们想象的更早开始重复，有没有更好的方法？

Question

我正在尝试生成许多由 4 位数字组成的随机字符串，并且它们不应相互重复。我不知道确切的数字，但大约有几百个。我试过 nextInt():

public static String generateLogID() {

    Random rdm = new Random();
    String s = "";
    for (int i=0;i<4;i++) {
        String digit = String.valueOf(rdm.nextInt(9));
        s = s.concat(digit);    
    }
    return s;
}

但是，当它出现在 70 号或 80 号左右时，它得到了重复字符串。理论上会有10*10*10*10种可能，为什么这么快就重复了，应该怎么做才能避免重复呢？谢谢你的任何建议!

我使用 HashMap 来保存所有记录以避免重复，而且效果很好。

HashMap<Integer, String> map = new HashMap<Integer, String>();
int count = 0;
for(loop conditions){
 String id = IDGenerator.generateLogID();
                while(map.containsValue(id)){
                    id = IDGenerator.generateLogID();
                    }
                map.put(count, id);
                count++;
}

但我真正想知道的是为什么这个生成器生成重复的速度这么快，还有没有其他生成方法可以降低重复率？

Answer 1

通过birthday problem ，在 80 个随机 4 位小数中出现重复的几率为 27.1%，100 个这样的随机值增加到 39.1%，118 个这样的随机值增加到 50%。因此，观察到的结果不足为奇。

这些赔率可以计算为:
p₀ = 0
p_i+1 = 1-(1-p_i)*(k-i)/k
其中 k 是等概率可能值的数量(此处 k=10000)。

要生成不同类随机数，我们可以

• 使用适当的密码，利用 Format Preserving Encryption 用常量( secret ) key 对计数器进行加密技术。这允许使用 O(log(k)) 内存处理非常大的 k，并且每个生成的 ID 的工作量增长为 O(log(k))。
• 使用 Fisher-Yates shuffle 生成 [0..k-1] 范围内整数的随机排列(ID 是打乱后的数组的第一个元素)；这对于中等 k 的编码更简单，但需要 O(k log(k)) 内存和初始工作(一个优雅的实现在 another answer 中，在数组中搜索 ID)。