一尘不染

创建自己的Tinyurl样式uid

algorithm

我正在写一篇关于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)


阅读 224

收藏
2020-07-28

共1个答案

一尘不染

与一个特定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次,因此您将这些概率相乘。

2020-07-28