创建自己的Tinyurl风格的uid

Question

我正在写一篇关于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个可能的读取)？

我之前的一般想法是在数据库或其他商店中使用ID,可以通过电话或印刷材料使用,而不是巨大的16字节guid.

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

Answer 1

为什么要使用随机函数？我总是假设tinyurl使用顺序Id的基础62(0-9A-Za-z)表示.没有冲突,网址总是尽可能短.

你会有一个DB表

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

相应的URL将是:

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

Answer 2

查看生日悖论,这是你遇到的确切问题.

问题是:你需要在一个房间里聚会多少人,这样你就有50%的机会让任何两个人拥有相同的生日？答案可能会让你大吃一惊.

Answer 3

前段时间我做到了这一点,我按照Sklivvz提到的方式行事.整个逻辑是使用SQL服务器存储过程和几个UDF(用户定义的函数)开发的.步骤是:

• 说你要缩短这个网址:创建你自己的Tinyurl风格的uid
• 将URL插入表中
• 获取最后一次插入的@@ identity值(数字id)
• 根据字母和数字的"域"转换相应字母数字值的id(我实际上使用了这个集合:"0123456789abcdefghijklmnopqrstuvwxyz")
• 返回那个值,比如'cc0'

转换是通过几个非常短的UDF实现的.

两个转换称为一个接一个将返回"顺序"值,如下所示:

select dbo.FX_CONV (123456) -- returns "1f5n"

select dbo.FX_CONV (123457) -- returns "1f5o"

如果您有兴趣,我可以分享UDF的代码.

Answer 4

与某一特定 ID 发生冲突的概率为：

\n\n

p = ( 0.5 * ( (0.5*1/10) + (0.5*1/26) ) )^6\n

\n\n

大约是 1.7\xc3\x9710^-9。

\n\n

生成 n 个 ID 后发生冲突的概率为 1-p^n，因此在插入 100 万个 ID 后，每次新插入发生冲突的概率约为 0.17%，在插入 1000 万个 ID 后，发生冲突的概率约为 1.7%，并且1亿后约16%。

\n\n

每分钟 1000 个 ID 相当于每月 4300 万个左右，因此，正如 Sklivvz 指出的那样，在这种情况下，使用一些递增的 ID 可能是更好的方法。

\n\n

编辑：

\n\n

为了解释数学原理，他实际上是抛硬币，然后选择一个数字或字母 6 次。抛硬币匹配的概率为 0.5，然后 50% 的概率为 1/10 匹配，50% 的概率为 1/26 匹配。这种情况独立发生 6 次，因此您可以将这些概率相乘。

\n