创建自己的Tinyurl样式uid

Question

我正在撰写一篇关于Guid/UID的人类可读性替代方案的小文章，例如在TinyURL上用于url散列的那些选项(它们经常在杂志中打印，因此需要简短)。

我生成的简单uid是-6个字符:小写字母(A)或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条)？

我所追求的总体想法是在数据库或其他可以通过电话或印刷品使用的存储中使用in，而不是一个巨大的16字节guid。

更新2:我把两个相互排斥的事件的公式放在上面，而不是两个独立的事件(因为第一次得到'a‘并不意味着第二次不能得到'a’)。应该是P(A和B) = P(A) x P(B)

Answer 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亿ID之后大约为16%。

1000个ID /分钟计算为每月4300万个ID，因此正如Sklivvz所指出的，在这种情况下使用一些递增ID可能是更好的方法。

编辑：

为了解释数学，他基本上是抛硬币，然后选择一个数字或字母6次。硬币翻转匹配的概率为0.5，而50%的情况下，匹配的概率为1/10，匹配的概率为50%。这是6次独立发生，所以你把这些概率相乘。

Answer 2

你为什么要用随机函数？我一直认为tinyurl使用了顺序Id的基数62 (0-9A-Za-z)表示。没有冲突，urls总是尽可能短。

您将有一个DB表，如

Id  URL
 1  http://google.com
 2  ...
... ...
156 ...
... ...

相应的网址是：

http://example.com/1
http://example.com/2
...
http://example.com/2W
...

Answer 3

查找生日悖论，这正是您遇到的问题。

问题是:你需要在一个房间里聚几个人，这样你就有50%的机会让两个人有相同的生日？答案可能会让你吃惊。