我正在写一篇关于Guids / UID的人类可读替代品的小文章,例如TinyURL上用于URL哈希的替代品(通常印在杂志上,因此必须简短)。
我生成的简单uid是-6个字符:小写字母(az)或0-9。
“根据我的计算队长”,这是6个相互排斥的事件,尽管计算冲突的概率要比P(A或B)= P(A)+ P(B)难一些,因为显然它包括数字和在下面的代码中,您可以看到它确定是使用50/50还是数字还是字母。
我对冲突率感兴趣,如果下面的代码是对预期冲突率的真实模拟,则可以从生成哈希中获得。平均而言,每百万我会发生40-50次冲突,但是请记住,uid不会一次生成一百万次,而每分钟可能仅生成10-1000次。
每次发生冲突的可能性是多少,有人可以提出更好的解决方法吗?
static Random _random = new Random(); public static void main() { // Size of the key, 6 HashSet<string> set = new HashSet<string>(); int clashes = 0; for (int n=0;n < 1000000;n++) { StringBuilder builder = new StringBuilder(); for (int i =0;i < 7;i++) { if (_random.NextDouble() > 0.5) { builder.Append((char)_random.Next(97,123)); } else { builder.Append(_random.Next(0,9).ToString()); } } if (set.Contains(builder.ToString())) { clashes++; Console.WriteLine("clash: (" +n+ ")" +builder.ToString()); } set.Add(builder.ToString()); _random.Next(); //Console.Write(builder.ToString()); } Console.WriteLine("Clashes: " +clashes); Console.ReadLine(); }
更新: 这是该问题的结果文章
我在这里真的问了两个问题,所以我作弊。我追求的答案是rcar,但是Sklivvz的答案也是第二部分(替代)。是否有可能在数据库中创建自定义的唯一ID生成器,还是在客户端(首先可能进行2次读取)?
我追求的总体思路是在数据库或其他商店中使用Ids,这些ID可以通过电话或印刷材料使用,而不是16字节的巨大GUID。
更新2: 我将两个互斥事件的公式放在两个之上,而不是两个独立的事件(因为第一次获得“ a”并不意味着第二次不能获得“ a”)。应该是P(A和B)= P(A)x P(B)
与一个特定ID发生冲突的概率为:
p = ( 0.5 * ( (0.5*1/10) + (0.5*1/26) ) )^6
大约是1.7×10 ^ -9。
生成n个ID后发生冲突的可能性为1-p ^ n,因此在插入100万个ID之后,每次新插入都会有大约0.17%的冲突机会,在1000万个ID之后,大约为1.7%。 1亿后约为16%。
1000 ID /分钟的计算量约为每月4300万,因此,如Sklivvz所指出的,在这种情况下,使用递增ID可能是更好的方法。
编辑:
为了解释数学原理,他实际上是在掷硬币,然后拣选一个数字或字母6次。硬币翻转匹配的可能性为0.5,然后有50%的时间有1/10的匹配几率和50%的1/26匹配的几率。该操作独立发生6次,因此您将这些概率相乘。