你说什么斩波型4 UUID以这种方式 [英] What do you say of chopping type-4 UUID in this manner

问题描述

检查这一点，

    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);
    }

此方法传递般的魅力。与我在即时pression它略好采取至少显著比特，而不是最显著。因为在最显著位有6比特固定为一些信息，并与至少显著其并非如此。因此，平均而言，我们需要产生2 ^ 29的UUID来获取与最显著位的碰撞，但2 ^ 32许多与至少显著位。编号： SO线程。 我是正确的假设？

This method is passing like charm. And I am in the impression that it is slightly better to take least significant bits, rather than the most significant. Because in the most significant bits you have 6 bits fixed for some info, and with least significant its not the case. Hence, on average we need to generate 2^29 UUIDs to get a collision with most significant bits, but 2^32 many with least significant bits. Ref: SO Thread. Am I right in assuming that?

现在，我在这里砍2个最显著的我从方法得到了至少显著位数字。我使用的子字符串来表示。请注意，我砍2位数字和符号位关闭。 这是否并不意味着现在平均需要生成2 ^ 31的UUID得到一个碰撞？

Now, here I am chopping 2 more most significant digits of the least significant bits I got from the method. I am using substring to that. Notice I am chopping 2 digits and a sign bit off. Does that not mean that now on average we need to generate 2^31 UUIDs to get a collision?

precisely，我想生成一个唯一的标识符，应该不超过17位的长度。它必须是一个整数，而不是在Java类型感。 如何可靠是我的方法？

Precisely, I am trying to generate a unique identifier which should not exceed 17 digit length. And it must be an integer, not in a sense of Java type. How reliable is my approach?

元信息：

事实上，我们正在将一些旧的体系，我们必须提供一些独特的数量不超过17位。他们是有它的数据库中唯一关键，我想。我们也可以使用序列在这种情况下，我提出，在首位。但是，他们对我说，它的好，如果我能想出​​一个随机数代替，因此消费者无法猜测。

Actually, we are integrating with some legacy system, and we must provide some unique number not more than 17 digits. They are having it as a database unique key, I assume. We can also use sequence in this case, and I proposed that in the first place. But they said to me that its good if I can come up with a random number instead, so consumer can't guess.

据我所知，关于4型实现UUID在Java中，我们需要生成2 ^ 61的UUID平均得到碰撞。难道不是意味着我们需要生成2 ^ 32获得至少显著位的碰撞，和2 ^ 29获得大多数显著位的碰撞？如果是的话那么它是不正确的假设，我们需要生成平均2 ^ 31获得至少显著位碰撞砍2后留下的大多数数字？

As far as I know regarding the type-4 implementation of UUID in Java we need to generate 2^61 UUIDs on average to get a collision. Does that not means that we need to generate 2^32 to get the collision on least significant bits, and 2^29 to get the collision on most significant bits? If yes then is it not correct to assume that we need to generate on average 2^31 to get the collision on least significant bits after chopping of 2 left most digits?

我试图用的SecureRandom 为好，但也给了我19位长的价值。因此，我结束了第一斩的那个数字了。下面是code为。

I tried to use SecureRandom as well, but that is also giving me 19 digits long value. Hence I end up chopping first to digits of that too. Below is the code for that.

    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位数。但是，这将是非常依赖处理器，并且可以猜测的，我想。因为我不是很肯定，我得到了在毫秒更改后99轮。可能是我会的，不过这将取决于处理器的速度。 99并发请求是不太可能，但。

The other option I can think of is to use date in a format "yyMMddHHmmssSSS+2-seq-digits". But that would be quite processor dependent, and guessable, I suppose. Because I am not quite certain that I got a change in millisecond after 99 rounds. May be I will, but that would depend on processor speed. 99 simultaneous requests are quite unlikely though.

推荐答案

我建议你使用随机或SecureRandom的生成随机位，把这些转化为数字。这应该是更便于携带。

I suggest that you use either Random or SecureRandom to generate random bits and turn those into a number. That should be more portable.

我不明白你对砍位点。假设你是从一个长周期的产生不够位的17（十进制）位数字PRNG你应该有1 10 ** 17为任何给定的产生对数字的碰撞的机会。如果源是好的，并使用足够的位则是无形的，你是砍......

I don't understand your point about chopping digits. Assuming that you are generating a 17 (decimal) digit number from enough bits from a long-cycle PRNG you should have a chance of 1 in 10**17 of a collision for any given generated pair of numbers. If the source is good, and you use enough bits then it is immaterial that you are "chopping" ...

目前还不清楚，我认为1 10 ** 17 是不够好。它取决于有多少数字要存在（在你的持久存储）在任何给定的时间。例如，如果有44万个号码现存，至少一对之间的碰撞的机会将是约1％。

It is not clear to me that 1 in 10**17 is good enough. It depends on how many numbers are going to exist (in your persistent store) at any given time. For instance, if you have 44 million numbers extant, the chance of a collision between at least one pair will be about 1%.

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

Try plugging some numbers into a Birthday Paradox Calculator.

编辑：我认为你需要的是一台发电机，为您提供64位的伪随机数周期较长的长度和不重复的多个数字比你所能可能产生绝对的保证。它也必须是能够持续发生器的状态，并恢复它。然后，为了获得一个17进制数字随机数，得到从发电机和测试的下一个值，如果它的范围是从 0 ... 10 ** 17 - 1 。如果是，使用它，如果不重复。

I think what you need is a generator that gives you 64 bit pseudo random numbers with a long cycle length AND an absolute guarantee of no repetitions for more numbers than you could ever possibly generate. It must also be possible to persist the state of the generator and resume it. Then, to get a 17 decimal digit "random" number, get the next value from the generator and test if it is in the range 0 ... 10**17 - 1. If it is, use it, if not repeat.

如果你正确地管理生成器，你永远不会得到重复的系统的寿命，因此有冲突的零风险。但重要的是你用一个PRNG（不是真正的RNG），而且你选择一个PRNG具有正确的性质是非常重要的。

If you manage the generator correctly, you never get a repetition for the lifetime of the system, and therefore there is zero risk of a collision. But it is important that you use a PRNG (not a true RNG) and that you pick a PRNG that has the right properties.

这是我可以告诉，Random类提供了一个PRNG与 2 ** 48 周期长;也就是说，你应该得到 2 ** 48 数字（例如使用 getLong之（）法）之前的数字开始重复。 OTOH，SecureRandom的任一给出真正的随机或伪随机的一个很长的周期计数...但具有重复每次调用若干小但非零的机会。

From what I can tell, the Random class offers a PRNG with a cycle length of 2**48; i.e. you should get 2**48 numbers (e.g. using the getLong() method) before the numbers start to repeat. OTOH, SecureRandom gives either truly random or pseudo-random with a very long cycle count ... but with a small but non-zero chance of repeating a number on each call.

这篇关于你说什么斩波型4 UUID以这种方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！