Java Unique Number Generator 碰撞测试内存不足

Question

我有一个系统要求生成一个 11 个字符的字符串，其中最右边的 8 个字符必须是唯一的。

据我了解，这种情况每天最多发生几百次。不幸的是，由于速度问题，我被要求避免使用数据库来简单地检索序列中的 nextval()。

所以我不得不测试各种方法来尽可能好地生成随机数，并且我想出了一个基于 SecureRandom 类的解决方案。

我决定对其进行测试，看看生成的字符串 self 重复的可能性有多大；我使用 HashMap (string, string) 测试了 1000 万代 - 看起来不错，并希望在晚上测试十亿个随机字符串，但由于线程“main”java.lang.OutOfMemoryError 中的异常而失败:Java堆空间

我目前的测试代码是这样的:

public class Main {
public static BigInteger BASE = BigInteger.valueOf(62);
public static final String DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

public static void main(String[] args) {
    // TODO Auto-generated method stub
    long lStartTime = System.nanoTime();
    HashMap<String, String> orders = new HashMap<String, String>();

    for (int i = 0; i < 960000000; i++) {
        SecureRandom randObj = new SecureRandom();
        BigInteger BigRand = new BigInteger(128, randObj);
        String rand = BigRand.toString(62);

        StringBuilder result = new StringBuilder();
        while (BigRand.compareTo(BigInteger.ZERO) == 1 && result.length()<11) { // number > 0
              BigInteger[] divmod = BigRand.divideAndRemainder(BASE);
              BigRand = divmod[0];
              int digit = divmod[1].intValue();
              result.insert(0, DIGITS.charAt(digit));
            }
        String doesKeyExistString = orders.get(result);
        if (doesKeyExistString != null) {
            System.out.print("Duplicate key found!: "+result.toString()+"\n");
        } else {
            orders.put(result.toString(), result.toString());  // No such key
        }
    }
    long lEndTime = System.nanoTime();
    long difference1 = lEndTime - lStartTime;
    double difference = (double)difference1/1000000000;
    System.out.println("Elapsed seconds: " + difference);
    System.out.println("Elapsed exact: " + difference1);

}

您有什么建议可以证明我们可以依赖这种生成随机数的方法，并且有可能将相同的字符串足够小两倍？

我偶然发现了这个问题:random number generator test答案看起来很有趣，但我不太明白如何将其应用到我的案例中(统计学是我最难的类(class)，我第二次尝试勉强通过了......)

我也不确定，如何调整这个随机生成器以动态设置生成的数字的长度。必须有比我在这里做的更好的方法来做到这一点......

谢谢!

Answer 1

让我们来看看这里的原始数字。

您正试图在 HashMap 中存储 10 亿个 11 个字符长的字符串。

如果我们计算这个(11 个字符数组 + 长度为 int)的绝对最小空间，则:

1e9 * (11 * 2 bytes + 4 bytes) = 26e9 bytes

或大约 24 GB。那就是您的解决方案需要多少内存。

如果我们看等式的另一边。您希望使用 62 个字符的字母表随机生成两个长度为 8 的相等字符串。这意味着你有

62 ^ 8 = 218340105584896

或者关于 2.18e14 的不同组合。看着 birthday problem我们可以计算我们需要生成的字符串数量，以至少有 50% 的概率生成相同的字符串两次。根据公式，该数字约为 1.74e7 倍。因此，如果您生成 1800 万个字符串，则两次生成相同字符串的概率超过 50%。

1800万个字符串应该只需要

1.8e7 * (11 * 2 bytes + 4 bytes) = 4.68e8 bytes

或大约 470 兆字节，这应该在您的限制范围内。

现在，至于您的实际问题 - 使用 random UUID如果可能的话，因为您可以依赖两次生成相同 UUID 的可能性，就所有实际目的而言，这是不存在的。

如果您不能使用 UUID 但必须使用这 8 个字符，我建议您稍微扩展一下字母表。通过使用所有可打印的 ASCII 字符(95 个字符)，您可以将可能的组合数量增加到略低于 6.1e15 - 尽管 50% 的碰撞机会的生成数仅增加到大约 9000 万。