java - 您对以这种方式切割 type-4 UUID 有何看法

Question

检查一下，

    List<String> list = new ArrayList<String>();
    for (int i = 0; i < 10000; i++) {
        String value = (""+UUID.randomUUID().getLeastSignificantBits()).substring(3, 20);
        assertFalse(list.contains(value));
        assertTrue(value.length() < 18);
        list.add(value);
    }

这个方法就像魅力一样转瞬即逝。我的印象是，采用最低有效位比采用最高有效位稍微好一些。因为在最高有效位中，您有 6 位固定用于某些信息，而在最低有效位中，情况并非如此。因此，平均而言，我们需要生成 2^29 个 UUID 才能与最高有效位发生冲突，但需要生成 2^32 个 UUID 来与最低有效位发生冲突。引用:SO Thread 。 我的假设正确吗？

现在，我将从该方法获得的最低有效位中再切掉 2 个最高有效位。我正在使用子字符串。请注意，我正在删除 2 位数字和一个符号位。 这是否意味着现在我们平均需要生成 2^31 个 UUID 才能发生碰撞？

准确地说，我正在尝试生成一个长度不超过 17 位的唯一标识符。而且它必须是一个整数，而不是Java类型意义上的。 我的方法有多可靠？

元信息:

实际上，我们正在与一些遗留系统集成，我们必须提供一些不超过17位的唯一编号。我认为他们将其作为数据库唯一键。在这种情况下我们也可以使用序列，这是我首先提出的。但他们对我说，如果我能想出一个随机数就好了，这样消费者就无法猜测。

据我所知，关于 Java 中 UUID 的 type-4 实现，我们平均需要生成 2^61 个 UUID 才能发生冲突。这是否意味着我们需要生成 2^32 来获得最低有效位的冲突，并生成 2^29 来获得最高有效位的冲突？如果是，那么假设我们需要平均生成 2^31 才能在斩波最左边的 2 位数字后获得最低有效位的冲突，这是否不正确？

我也尝试使用SecureRandom，但这也给了我 19 位长的值。因此，我最终也先将其切成数字。下面是相关代码。

    List<String> list = new ArrayList();
    Random random = new SecureRandom();
    for (int i = 0; i < 10000; i++) {
        String value = ""+random.nextLong().substring(2, 19);
        assertFalse(list.contains(value));
        assertTrue(value.length() < 18);
        list.add(value);
    }

我能想到的另一个选项是使用“yyMMddHHmmssSSS+2-seq-digits”格式的日期。但这完全依赖于处理器，并且是可以猜测的，我想。因为我不太确定在99轮后我得到了毫秒的变化。也许我会，但这取决于处理器速度。不过 99 个同时请求的可能性很小。

Answer 1

我建议您使用 Random 或 SecureRandom 来生成随机位并将其转换为数字。那应该更便携。

我不明白你关于切割数字的观点。假设您从长周期 PRNG 的足够位中生成 17 位(十进制)数字，对于任何给定的生成数字对，您应该有 10**17 分之一的碰撞机会。如果来源很好，并且您使用了足够的位，那么您“砍伐”就无关紧要了......

我不清楚 10**17 中的 1 是否足够好。这取决于在任何给定时间(在持久存储中)将存在多少数字。例如，如果现有 4400 万个号码，则至少一对之间发生冲突的几率约为 1%。

尝试将一些数字插入 Birthday Paradox Calculator .

编辑:我认为您需要的是一个生成器，它可以为您提供具有长周期长度的 64 位伪随机数，并且绝对保证不会重复比您可能生成的数字更多的数字。还必须能够保持生成器的状态并恢复它。然后，要获取 17 位十进制数字“随机”数字，请从生成器获取下一个值并测试它是否在 0 ... 10**17 - 1 范围内。如果是，则使用它，如果不是则重复。

如果正确管理生成器，则在系统的整个生命周期内永远不会出现重复，因此碰撞风险为零。但重要的是您使用 PRNG(不是真正的 RNG)并且选择具有正确属性的 PRNG。

据我所知，Random 类提供了一个循环长度为 2**48 的 PRNG；即，在数字开始重复之前，您应该获取 2**48 数字(例如使用 getLong() 方法)。 OTOH，SecureRandom 提供真正的随机或伪随机，具有非常长的循环计数......但每次调用时重复数字的机会很小但非零。