如何将 UUID 转换为少于 40 位的数字？
How to convert a UUID to a number with less than 40 digits?
我需要将 UUID（如 ffffffff-ffff-ffff-ffff-ffffffffffff）转换为尽可能少的数字。这些 UUID 由 com.fasterxml.uuid.impl.TimeBasedGenerator.java.
生成
package com.fasterxml.uuid.impl;
import java.util.UUID;
import com.fasterxml.uuid.*;
/**
* Implementation of UUID generator that uses time/location based generation
* method (variant 1).
*<p>
* As all JUG provided implementations, this generator is fully thread-safe.
* Additionally it can also be made externally synchronized with other
* instances (even ones running on other JVMs); to do this,
* use {@link com.fasterxml.uuid.ext.FileBasedTimestampSynchronizer}
* (or equivalent).
*
* @since 3.0
*/
public class TimeBasedGenerator extends NoArgGenerator
{
/*
/**********************************************************************
/* Configuration
/**********************************************************************
*/
protected final EthernetAddress _ethernetAddress;
/**
* Object used for synchronizing access to timestamps, to guarantee
* that timestamps produced by this generator are unique and monotonically increasings.
* Some implementations offer even stronger guarantees, for example that
* same guarantee holds between instances running on different JVMs (or
* with native code).
*/
protected final UUIDTimer _timer;
/**
* Base values for the second long (last 8 bytes) of UUID to construct
*/
protected final long _uuidL2;
/*
/**********************************************************************
/* Construction
/**********************************************************************
*/
/**
* @param ethAddr Hardware address (802.1) to use for generating
* spatially unique part of UUID. If system has more than one NIC,
*/
public TimeBasedGenerator(EthernetAddress ethAddr, UUIDTimer timer)
{
byte[] uuidBytes = new byte[16];
if (ethAddr == null) {
ethAddr = EthernetAddress.constructMulticastAddress();
}
// initialize baseline with MAC address info
_ethernetAddress = ethAddr;
_ethernetAddress.toByteArray(uuidBytes, 10);
// and add clock sequence
int clockSeq = timer.getClockSequence();
uuidBytes[UUIDUtil.BYTE_OFFSET_CLOCK_SEQUENCE] = (byte) (clockSeq >> 8);
uuidBytes[UUIDUtil.BYTE_OFFSET_CLOCK_SEQUENCE+1] = (byte) clockSeq;
long l2 = UUIDUtil.gatherLong(uuidBytes, 8);
_uuidL2 = UUIDUtil.initUUIDSecondLong(l2);
_timer = timer;
}
/*
/**********************************************************************
/* Access to config
/**********************************************************************
*/
@Override
public UUIDType getType() { return UUIDType.TIME_BASED; }
public EthernetAddress getEthernetAddress() { return _ethernetAddress; }
/*
/**********************************************************************
/* UUID generation
/**********************************************************************
*/
/* As timer is not synchronized (nor _uuidBytes), need to sync; but most
* importantly, synchronize on timer which may also be shared between
* multiple instances
*/
@Override
public UUID generate()
{
final long rawTimestamp = _timer.getTimestamp();
// Time field components are kind of shuffled, need to slice:
int clockHi = (int) (rawTimestamp >>> 32);
int clockLo = (int) rawTimestamp;
// and dice
int midhi = (clockHi << 16) | (clockHi >>> 16);
// need to squeeze in type (4 MSBs in byte 6, clock hi)
midhi &= ~0xF000; // remove high nibble of 6th byte
midhi |= 0x1000; // type 1
long midhiL = (long) midhi;
midhiL = ((midhiL << 32) >>> 32); // to get rid of sign extension
// and reconstruct
long l1 = (((long) clockLo) << 32) | midhiL;
// last detail: must force 2 MSB to be '10'
return new UUID(l1, _uuidL2);
}
}
我预计每天至少会在特定机器上生成 1200 万个 UUID。我假设 TimeBasedGenerator 将在程序启动时实例化一次，因此将具有恒定的网络地址和恒定的 运行dom 生成器种子时间（下面代码片段中的值 now）。
final long now = 1644575806478L;
final TimeBasedGenerator sut = new TimeBasedGenerator(EthernetAddress.fromInterface(),
new UUIDTimer(new Random(now), null));
如何使用
将UUID转换为数字
a) 少于 40 位 和
b) 以便最早在 6 个月内出现一次重复的 UUID？
尝试失败 1
将 UUID 转换为数字的最简单方法如下所示：
import java.math.BigInteger;
import java.util.function.Function;
public class OldUUIDConverter implements Function<String, BigInteger> {
@Override
public BigInteger apply(final String uuid) {
final String uuidWithoutDashes = uuid.replaceAll("-", "");
return new BigInteger(uuidWithoutDashes, 16);
}
}
对于最大可能的 UUID (ffffffff-ffff-ffff-ffff-ffffffffffff)，它会生成数字
340282366920938463463374607431768211455
^ ^ ^ ^ ^
因为我们是直接转换UUID，所以如果UUID生成器不是太频繁地产生重复的UUID，就不会重复。
满足上述要求的条件b)。但是条件 a) -- 转换后的数字的长度 -- 不是。
尝试失败 2
有人提议只取UUID的前8位。因此标准 a) 将得到满足。
但是，UUID的前8位重复太频繁了。
我写了一个简单的测试程序：
import com.fasterxml.uuid.EthernetAddress;
import com.fasterxml.uuid.UUIDTimer;
import com.fasterxml.uuid.impl.TimeBasedGenerator;
import org.junit.Test;
import java.io.IOException;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
public class UUIDShortenerTest {
@Test
public void test() throws IOException {
final Set<String> first8DigitsAsLong = new HashSet<>(73000000);
final long now = 1644575806478L;
final TimeBasedGenerator sut = new TimeBasedGenerator(EthernetAddress.fromInterface(), new UUIDTimer(new Random(now), null));
for (int i=0; i < Integer.MAX_VALUE; i++) {
final String curUuid = sut.generate().toString();
final String first8Digits = curUuid.substring(0, 8);
if ((i % 1000000L) == 0) {
System.out.println(String.format("Counter: %d", i));
}
if (!first8DigitsAsLong.add(first8Digits)) {
System.out.println("Duplicate!");
System.out.println(i);
break;
}
}
}
}
我运行它10次。每次我记下UUID代数后前8位重复。
结果如下：
- 在
74499376 代 UUID 之后找到重复的前 8 位数字。
- 44259478
- 45365652
- 45031094
- 45445463
- 46250299
- 45403800
- 44658612
- 46098250
- 43748051
假设在我生成了 7500 万个 UUID 后重复前 8 位数字。
如果我每天生成1200万个UUID，这意味着第一个前8位重复的UUID将在62-63天（75000000/1200000=62.5天）后生成。
这62.5天（约两个月）低于UUID重复前6个月的要求。
我知道的选项
我可以做很多事情来解决这个问题。
一个是增加我使用的第一个数字的数量，直到 UUID 重复的频率达到所需的水平。也就是说，我可以尝试使用 9 个第一位数字而不是 8 个，看看它是否足够好。如果没有，我可以使用前 10 个数字等
另一种方法是使用失败尝试 #1 中的代码，并在具有更大基础的数字系统中对结果数字 340282366920938463463374607431768211455 进行编码。
假设我使用数字 0-9、拉丁文小写和大写字母以及 14 个特殊字符。这导致每个数字可以有 10+26+26+14=76 个数字。我假设上述数字在 base 76 系统中将比十进制或十六进制系统中的相同数字短。
是否还有其他更好的选择（例如具有足够多样性的哈希函数）？
tl;博士
new BigInteger(
"ffffffff-ffff-ffff-ffff-ffffffffffff" ,
16
) // Parse the input as hexadecimal numbers. Returns a `BigInteger` object.
.toString() // Generate text containing the digits of a decimal integer representation of this number.
.codePoints() // Generate a stream of the Unicode code point number assigned to each of the characters in this string.
.toArray() // Collect the streamed code point numbers into an array.
.length // Get size of array.
39
340282366920938463463374607431768211455确实不足40位
您的声明：
But criterion a) -- the length of the converted number -- is not.
…不正确。
生成的整数有 39 位。 Thirty-nine 满足您小于 40 位数的门槛：39 < 40。
这是计算数字的代码。
String input = "ffffffff-ffff-ffff-ffff-ffffffffffff" ;
String uuidWithoutDashes = input.replaceAll( "-" , "" );
BigInteger bi = new BigInteger( uuidWithoutDashes , 16 );
String output = bi.toString() ;
int digitCount = output.codePoints().toArray().length ;
System.out.println( bi ) ;
System.out.println( digitCount ) ;
看到这个code run live at IdeOne.com。
340282366920938463463374607431768211455
39
或者，手动计算数字。为了便于计数，我添加了脱字符来标记 1、11、21、31、41。
340282366920938463463374607431768211455
^ ^ ^ ^ ^
至于更大的图景，我无法想象存储从 UUID 的十进制表示中提取的 39 位数字的有价值的目的。研究建议您坚持使用 128 位二进制表示的评论。
我也想知道为什么你提供一个固定的数字作为你的 Random 的种子。这样做会产生与输出相同的数字。
这是生日问题。理论上只要生成两个UUID就可以发生UUID冲突，不过有方便的probability tables。您正在尝试生成 12*10^6*30*6 ~= 2*10^9 个 ID。您愿意承担多少风险？
我需要将 UUID（如 ffffffff-ffff-ffff-ffff-ffffffffffff）转换为尽可能少的数字。这些 UUID 由 com.fasterxml.uuid.impl.TimeBasedGenerator.java.
package com.fasterxml.uuid.impl;
import java.util.UUID;
import com.fasterxml.uuid.*;
/**
* Implementation of UUID generator that uses time/location based generation
* method (variant 1).
*<p>
* As all JUG provided implementations, this generator is fully thread-safe.
* Additionally it can also be made externally synchronized with other
* instances (even ones running on other JVMs); to do this,
* use {@link com.fasterxml.uuid.ext.FileBasedTimestampSynchronizer}
* (or equivalent).
*
* @since 3.0
*/
public class TimeBasedGenerator extends NoArgGenerator
{
/*
/**********************************************************************
/* Configuration
/**********************************************************************
*/
protected final EthernetAddress _ethernetAddress;
/**
* Object used for synchronizing access to timestamps, to guarantee
* that timestamps produced by this generator are unique and monotonically increasings.
* Some implementations offer even stronger guarantees, for example that
* same guarantee holds between instances running on different JVMs (or
* with native code).
*/
protected final UUIDTimer _timer;
/**
* Base values for the second long (last 8 bytes) of UUID to construct
*/
protected final long _uuidL2;
/*
/**********************************************************************
/* Construction
/**********************************************************************
*/
/**
* @param ethAddr Hardware address (802.1) to use for generating
* spatially unique part of UUID. If system has more than one NIC,
*/
public TimeBasedGenerator(EthernetAddress ethAddr, UUIDTimer timer)
{
byte[] uuidBytes = new byte[16];
if (ethAddr == null) {
ethAddr = EthernetAddress.constructMulticastAddress();
}
// initialize baseline with MAC address info
_ethernetAddress = ethAddr;
_ethernetAddress.toByteArray(uuidBytes, 10);
// and add clock sequence
int clockSeq = timer.getClockSequence();
uuidBytes[UUIDUtil.BYTE_OFFSET_CLOCK_SEQUENCE] = (byte) (clockSeq >> 8);
uuidBytes[UUIDUtil.BYTE_OFFSET_CLOCK_SEQUENCE+1] = (byte) clockSeq;
long l2 = UUIDUtil.gatherLong(uuidBytes, 8);
_uuidL2 = UUIDUtil.initUUIDSecondLong(l2);
_timer = timer;
}
/*
/**********************************************************************
/* Access to config
/**********************************************************************
*/
@Override
public UUIDType getType() { return UUIDType.TIME_BASED; }
public EthernetAddress getEthernetAddress() { return _ethernetAddress; }
/*
/**********************************************************************
/* UUID generation
/**********************************************************************
*/
/* As timer is not synchronized (nor _uuidBytes), need to sync; but most
* importantly, synchronize on timer which may also be shared between
* multiple instances
*/
@Override
public UUID generate()
{
final long rawTimestamp = _timer.getTimestamp();
// Time field components are kind of shuffled, need to slice:
int clockHi = (int) (rawTimestamp >>> 32);
int clockLo = (int) rawTimestamp;
// and dice
int midhi = (clockHi << 16) | (clockHi >>> 16);
// need to squeeze in type (4 MSBs in byte 6, clock hi)
midhi &= ~0xF000; // remove high nibble of 6th byte
midhi |= 0x1000; // type 1
long midhiL = (long) midhi;
midhiL = ((midhiL << 32) >>> 32); // to get rid of sign extension
// and reconstruct
long l1 = (((long) clockLo) << 32) | midhiL;
// last detail: must force 2 MSB to be '10'
return new UUID(l1, _uuidL2);
}
}
我预计每天至少会在特定机器上生成 1200 万个 UUID。我假设 TimeBasedGenerator 将在程序启动时实例化一次，因此将具有恒定的网络地址和恒定的 运行dom 生成器种子时间（下面代码片段中的值 now）。
final long now = 1644575806478L;
final TimeBasedGenerator sut = new TimeBasedGenerator(EthernetAddress.fromInterface(),
new UUIDTimer(new Random(now), null));
如何使用
将UUID转换为数字a) 少于 40 位 和
b) 以便最早在 6 个月内出现一次重复的 UUID？
尝试失败 1
将 UUID 转换为数字的最简单方法如下所示：
import java.math.BigInteger;
import java.util.function.Function;
public class OldUUIDConverter implements Function<String, BigInteger> {
@Override
public BigInteger apply(final String uuid) {
final String uuidWithoutDashes = uuid.replaceAll("-", "");
return new BigInteger(uuidWithoutDashes, 16);
}
}
对于最大可能的 UUID (ffffffff-ffff-ffff-ffff-ffffffffffff)，它会生成数字
340282366920938463463374607431768211455
^ ^ ^ ^ ^
因为我们是直接转换UUID，所以如果UUID生成器不是太频繁地产生重复的UUID，就不会重复。
满足上述要求的条件b)。但是条件 a) -- 转换后的数字的长度 -- 不是。
尝试失败 2
有人提议只取UUID的前8位。因此标准 a) 将得到满足。
但是，UUID的前8位重复太频繁了。
我写了一个简单的测试程序：
import com.fasterxml.uuid.EthernetAddress;
import com.fasterxml.uuid.UUIDTimer;
import com.fasterxml.uuid.impl.TimeBasedGenerator;
import org.junit.Test;
import java.io.IOException;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
public class UUIDShortenerTest {
@Test
public void test() throws IOException {
final Set<String> first8DigitsAsLong = new HashSet<>(73000000);
final long now = 1644575806478L;
final TimeBasedGenerator sut = new TimeBasedGenerator(EthernetAddress.fromInterface(), new UUIDTimer(new Random(now), null));
for (int i=0; i < Integer.MAX_VALUE; i++) {
final String curUuid = sut.generate().toString();
final String first8Digits = curUuid.substring(0, 8);
if ((i % 1000000L) == 0) {
System.out.println(String.format("Counter: %d", i));
}
if (!first8DigitsAsLong.add(first8Digits)) {
System.out.println("Duplicate!");
System.out.println(i);
break;
}
}
}
}
我运行它10次。每次我记下UUID代数后前8位重复。
结果如下：
- 在
74499376代 UUID 之后找到重复的前 8 位数字。 - 44259478
- 45365652
- 45031094
- 45445463
- 46250299
- 45403800
- 44658612
- 46098250
- 43748051
假设在我生成了 7500 万个 UUID 后重复前 8 位数字。
如果我每天生成1200万个UUID，这意味着第一个前8位重复的UUID将在62-63天（75000000/1200000=62.5天）后生成。
这62.5天（约两个月）低于UUID重复前6个月的要求。
我知道的选项
我可以做很多事情来解决这个问题。
一个是增加我使用的第一个数字的数量，直到 UUID 重复的频率达到所需的水平。也就是说，我可以尝试使用 9 个第一位数字而不是 8 个，看看它是否足够好。如果没有，我可以使用前 10 个数字等
另一种方法是使用失败尝试 #1 中的代码，并在具有更大基础的数字系统中对结果数字 340282366920938463463374607431768211455 进行编码。
假设我使用数字 0-9、拉丁文小写和大写字母以及 14 个特殊字符。这导致每个数字可以有 10+26+26+14=76 个数字。我假设上述数字在 base 76 系统中将比十进制或十六进制系统中的相同数字短。
是否还有其他更好的选择（例如具有足够多样性的哈希函数）？
tl;博士
new BigInteger(
"ffffffff-ffff-ffff-ffff-ffffffffffff" ,
16
) // Parse the input as hexadecimal numbers. Returns a `BigInteger` object.
.toString() // Generate text containing the digits of a decimal integer representation of this number.
.codePoints() // Generate a stream of the Unicode code point number assigned to each of the characters in this string.
.toArray() // Collect the streamed code point numbers into an array.
.length // Get size of array.
39
340282366920938463463374607431768211455确实不足40位
您的声明：
But criterion a) -- the length of the converted number -- is not.
…不正确。
生成的整数有 39 位。 Thirty-nine 满足您小于 40 位数的门槛：39 < 40。
这是计算数字的代码。
String input = "ffffffff-ffff-ffff-ffff-ffffffffffff" ;
String uuidWithoutDashes = input.replaceAll( "-" , "" );
BigInteger bi = new BigInteger( uuidWithoutDashes , 16 );
String output = bi.toString() ;
int digitCount = output.codePoints().toArray().length ;
System.out.println( bi ) ;
System.out.println( digitCount ) ;
看到这个code run live at IdeOne.com。
340282366920938463463374607431768211455
39
或者，手动计算数字。为了便于计数，我添加了脱字符来标记 1、11、21、31、41。
340282366920938463463374607431768211455
^ ^ ^ ^ ^
至于更大的图景，我无法想象存储从 UUID 的十进制表示中提取的 39 位数字的有价值的目的。研究建议您坚持使用 128 位二进制表示的评论。
我也想知道为什么你提供一个固定的数字作为你的 Random 的种子。这样做会产生与输出相同的数字。
这是生日问题。理论上只要生成两个UUID就可以发生UUID冲突，不过有方便的probability tables。您正在尝试生成 12*10^6*30*6 ~= 2*10^9 个 ID。您愿意承担多少风险？