1

检查这个，

    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 线程。我的假设是对的吗？

现在，在这里，我将从该方法中获得的最低有效位中再砍掉 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 个同时请求是不太可能的。

4

3 回答 3

4

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

我不明白你关于砍数字的观点。假设您正在从长周期 PRNG 的足够位中生成 17（十进制）数字，对于任何给定的生成数字对，您应该有 10**17 发生冲突的机会。如果来源很好，并且您使用了足够多的位，那么您“切碎”就无关紧要了...

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

尝试将一些数字插入生日悖论计算器。

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

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

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

于 2009-11-13T06:29:28.600 回答
1

好的，几个问题，我会尽力的

  1. 如果你在低位有勾结但在高位没有，你仍然有唯一的 id。相反的情况也是如此。因此，您需要 2^61 个数字才能获得勾结。
  2. 以 0.5 的概率，你砍掉 3 位数字，因为 + 号没有写。因此，您总共有 2^41 个可能的数字，因此串通的样本量为 2^21。(10^18 =~ 2^41)
  3. 让我们看看你是如何得到结果的：Random.getLong() 被调用了两次，然后你删除了一些位（PRNG创建的随机位）。我看不出它比调用 Random.getLong() 或 getInt() 更可靠。

如果您需要 17 位数字，为什么不执行以下操作：

String id = String.valueOf(random.nextLong) % 1000000000000000000L);

请注意，它不会给出对称分布 - 因为 MAX_LONG 是 9223372036854775807L，所以 [0,23372036854775807] 范围内的数字出现的机会会稍好一些。

此外，你的方法和这个方法都不能确保唯一的 id。

于 2009-11-13T06:27:15.610 回答
0

UUID 算法是特定于实现的。

将 guid 分成较小的数字不会具有相同的唯一性传播或保证。你节省的比特真的那么重要吗？

于 2009-11-13T04:49:39.540 回答