UUID子串的唯一性
Uniqueness of UUID substring
我们使用 java.util 生成的 UUID 跟踪一个内部实体。新要求是将此对象传递给需要最大字符数限制为 11 的唯一标识符的第三方。代替生成、跟踪和映射全新的唯一 ID，我们想知道使用UUID 作为计算字段。记录数最多1000万条。
java.util.UUID.randomUUID().toString() // 用于生成
的代码
引用自其他资源（包括 SOF）：
“....只有在大约 100 年内每秒生成 10 亿个 UUID 后，创建单个重复项的概率才会达到 50%。”
“生成更长的 UUID 并对它们进行子字符串处理时也要小心，因为 ID 的某些部分可能包含固定字节（例如 MAC、DCE 和 MD5 UUID 就是这种情况）。” =10=]
我们将检查现有 ID 的子字符串是否重复。子字符串生成重复项的可能性有多大？
这是生日问题的一个实例。 B.P 的一种表述：给定一个 n 值的选择，通过替换随机抽样，我们可以抽取多少个值，然后相同的值将至少出现两次，概率为 p?
对于问题的经典实例，
p = 0.5, n = the 365 days of the year
答案是 23。换句话说，当你调查 23 个人时，两个人生日相同的几率是 50%。
可以插上
n = the number of possible UUIDs
取而代之的是获得 50% 碰撞概率所需的那种宇宙大样本量——大约每秒十亿次的数字。是
n = 16^32
对于由 16 个不区分大小写的十六进制数字组成的 32 个字符的字符串。
B.P。一个计算成本相对较高的问题，因为没有已知的封闭形式公式。事实上，我刚刚在 Wolfram Alpha Pro 上尝试了你的 11 个字符的子字符串 (n = 16^11)，它超时了。
但是，我发现了一种封闭式估计的有效实现方式 here。这是我对 Python.
的改编
import math
def find(p, n):
return math.ceil(math.sqrt(2 * n * math.log(1/(1-p))))
如果我插上经典B.P。数字，我得到 23 的答案，这是正确的。对于完整的 UUID 编号，
find(.5, math.pow(16, 32)) / 365 / 24 / 60 / 60 / 100
我的结果竟然是接近每秒70亿个UUID，持续了100年！也许这个估计对于大量数据来说太粗略了，虽然我不知道你的消息来源使用了什么方法。
对于 11 个字符的字符串？您只需生成大约 500 万个 ID 即可达到 50% 的碰撞几率。对于1%，总共只有60万左右。与您的来源相比，这可能高估了安全性（假设子字符串是随机的，我们已经犯了这个错误）。
我的工程建议：除了唯一性之外，您真的需要 UUID 提供的保证，例如不可枚举性和在分布式上下文中防止冲突的保证吗？如果不是，那么就使用顺序 ID，避免这些复杂情况。
我们使用 java.util 生成的 UUID 跟踪一个内部实体。新要求是将此对象传递给需要最大字符数限制为 11 的唯一标识符的第三方。代替生成、跟踪和映射全新的唯一 ID，我们想知道使用UUID 作为计算字段。记录数最多1000万条。
java.util.UUID.randomUUID().toString() // 用于生成
的代码引用自其他资源（包括 SOF）： “....只有在大约 100 年内每秒生成 10 亿个 UUID 后，创建单个重复项的概率才会达到 50%。”
“生成更长的 UUID 并对它们进行子字符串处理时也要小心，因为 ID 的某些部分可能包含固定字节（例如 MAC、DCE 和 MD5 UUID 就是这种情况）。” =10=]
我们将检查现有 ID 的子字符串是否重复。子字符串生成重复项的可能性有多大？
这是生日问题的一个实例。 B.P 的一种表述：给定一个 n 值的选择，通过替换随机抽样，我们可以抽取多少个值，然后相同的值将至少出现两次，概率为 p?
对于问题的经典实例，
p = 0.5, n = the 365 days of the year
答案是 23。换句话说，当你调查 23 个人时，两个人生日相同的几率是 50%。
可以插上
n = the number of possible UUIDs
取而代之的是获得 50% 碰撞概率所需的那种宇宙大样本量——大约每秒十亿次的数字。是
n = 16^32
对于由 16 个不区分大小写的十六进制数字组成的 32 个字符的字符串。
B.P。一个计算成本相对较高的问题，因为没有已知的封闭形式公式。事实上，我刚刚在 Wolfram Alpha Pro 上尝试了你的 11 个字符的子字符串 (n = 16^11)，它超时了。
但是，我发现了一种封闭式估计的有效实现方式 here。这是我对 Python.
的改编import math
def find(p, n):
return math.ceil(math.sqrt(2 * n * math.log(1/(1-p))))
如果我插上经典B.P。数字，我得到 23 的答案，这是正确的。对于完整的 UUID 编号，
find(.5, math.pow(16, 32)) / 365 / 24 / 60 / 60 / 100
我的结果竟然是接近每秒70亿个UUID，持续了100年！也许这个估计对于大量数据来说太粗略了，虽然我不知道你的消息来源使用了什么方法。
对于 11 个字符的字符串？您只需生成大约 500 万个 ID 即可达到 50% 的碰撞几率。对于1%，总共只有60万左右。与您的来源相比，这可能高估了安全性（假设子字符串是随机的，我们已经犯了这个错误）。
我的工程建议：除了唯一性之外，您真的需要 UUID 提供的保证，例如不可枚举性和在分布式上下文中防止冲突的保证吗？如果不是，那么就使用顺序 ID，避免这些复杂情况。