我需要编写一个随机字符串生成类，它从 31 个字符的数字字符集和一些字母(10+26-5，省略 5 个元音)生成 7 个字符的字符串。简单的数学给出了一组 31^7 种可能的组合 ~ 275 亿。 我对 bday 悖论有疑问，我进行了一些测试，重复的数量呈指数增长。 我可以做些什么来避免这种情况吗？

At 1 million, duplicates encountered till now = 19
At 2 million, duplicates encountered till now = 69
At 3 million, duplicates encountered till now = 157
At 4 million, duplicates encountered till now = 280
At 5 million, duplicates encountered till now = 470
At 6 million, duplicates encountered till now = 662
At 7 million, duplicates encountered till now = 896
At 8 million, duplicates encountered till now = 1185
At 9 million, duplicates encountered till now = 1500
At 10 million, duplicates encountered till now = 1823
At 11 million, duplicates encountered till now = 2204
At 12 million, duplicates encountered till now = 2584
At 13 million, duplicates encountered till now = 3020
At 14 million, duplicates encountered till now = 3527
At 15 million, duplicates encountered till now = 4110
At 16 million, duplicates encountered till now = 4683
At 17 million, duplicates encountered till now = 5284
At 18 million, duplicates encountered till now = 5919
At 19 million, duplicates encountered till now = 6611
At 20 million, duplicates encountered till now = 7343
At 21 million, duplicates encountered till now = 8095
At 22 million, duplicates encountered till now = 8858
At 23 million, duplicates encountered till now = 9707
At 24 million, duplicates encountered till now = 10547
At 25 million, duplicates encountered till now = 11452
At 26 million, duplicates encountered till now = 12399
At 27 million, duplicates encountered till now = 13356
At 28 million, duplicates encountered till now = 14393
At 29 million, duplicates encountered till now = 15369
At 30 million, duplicates encountered till now = 16436

下面是测试类:

import java.util.Set;

import org.apache.commons.lang3.RandomStringUtils;

import com.google.common.collect.Sets;

public class RandomUnivmylocaL {

    public static void main(String[] argv) {

        final int million = 1_000_000;

        final int iterations = 30;
        // 31 chars
        final char[] charArr = new char[] { '1', '2', '3', '4', '5', '6', '7', 
                '8', '9', '0', 'B', 'C', 'D', 'F', 'G', 'H', 'J', 'K', 'L',
                'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'V', 'W', 'X', 'Y', 'Z' };
        // System.out.println(charArr.length);

        final Set<String> set = Sets.newHashSetWithExpectedSize(
                iterations * million);

        for (int i = 0; i < iterations; i++) {
            for (int j = 0; j < million; j++) {
                final String univCode = RandomStringUtils.random(7, charArr);
                set.add(univCode);
            }
            System.out.println("At " + (i + 1) + " million, " +
                    "duplicates encountered till now = " + 
                    (((i + 1) * million) - set.size()));
        }
        System.out.println("done");
    }
}

最佳答案

这就是生日悖论。

sqrt(27.5bn) = 165831，大 M 的生日悖论公式为 1.177*sqrt(M)，因此当您生成大约 200,000 时，出现问题的可能性为 50/50，当您到达一百万你会有大约 18 个问题，等等。

生日问题 - 在有可能发生碰撞之前有多少 - 大约 200,000。 http://www.wolframalpha.com/input/?i=n%3D200000,+m%3D(31%5E7),+n+-+m(1+-+((m-1)%2Fm)%5En)

设置 n = 23.0 和 m = 365 以查看一个房间中的 23 个人。 http://www.wolframalpha.com/input/?i=n%3D23.0,+m%3D365,+n+-+m(1+-+((m-1)%2Fm)%5En)

您可以看到您的模拟与大数的预期答案有多接近。

http://www.wolframalpha.com/input/?i=n%3D30e6,+m%3D(31%5E7),+n+-+m(1+-+((m-1)%2Fm)%5En)

Quora 文章不错。 http://www.quora.com/How-can-I-calculate-the-expected-number-of-cache-hits .

因此您需要增加允许的字符数或使用更长的字符串。或者 - 要使用 7 位数字，只需增加计数器即可。 或使用随机数，并检查您以前是否使用过它，并在您厌倦了寻找新号码时重新设置。

还有伪随机生成器可以覆盖空间而无需重新点击。 7 个字符不会使您的解决方案安全。

关于java随机字符串生成和生日悖论，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31282812/