Ruby 中 SecureRandom.urlsafe_base64(8) 的碰撞概率? [英] Probability of collision of SecureRandom.urlsafe_base64(8) in Ruby?

问题描述

我正在使用 SecureRandom.urlsafe_base64(8) 以便在我的系统中创建 URL 安全的唯一 ID.

I am using SecureRandom.urlsafe_base64(8) in order to create unique ids in my system that are URL safe.

我想知道如何计算碰撞概率?我将这些 id 中的大约 10.000 个插入到一个数组中，我想避免检查其中一个键是否已经在数组中，但我还想确保它们没有重复?机会有多大?

I would like to know how to calculate the probability of collision? I am inserting about 10.000 of those ids into an array, and I want to avoid checking if one of the keys is already in the array, but I also want to make sure that are not repeated? What are the chances?

推荐答案

这个概率有一个很好的近似值(这与 生日问题).如果有k个潜在值并且采样n，则碰撞概率为:

There is a good approximation of this probability (which relates to the birthday problem). If there are k potential values and n are sampled, the probability of collision is:

k! / (k^n * (k - n)!)

base64 方法返回根据输入的随机字节数构建的 base 64 字符串，而不是随机数字的数量.八个随机字节为我们提供了 k = 256^8，大约为 1.8446744e+19.您正在生成 10,000 个这样的字符串，因此 n = 10,000，这为我们提供了 2.710498492319857e-12 的概率，这是非常低的.

The base64 method returns a base 64 string built from the inputted number of random bytes, not that number of random digits. Eight random bytes gives us k = 256^8, about 1.8446744e+19. You are generating 10,000 of these strings, so n = 10,000, which gives us a probability of 2.710498492319857e-12, which is very low.

这篇关于Ruby 中 SecureRandom.urlsafe_base64(8) 的碰撞概率?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！