goo.gl或jsfiddle等网站如何生成网址代码？

Question

我想生成像goo.gl和jsfiddle网站(http://jsfiddle.net/XzKvP/)的代码.

我尝试了不同的东西,给了我太大的guid,重复的字母数字代码等.

我想我应该能够根据数据库表中的主键生成一个字母数字代码.这样它会不重复吗？PK是一个自动递增的整数1.但不确定它应该如何完成.

我想要的代码看起来是随机的,但它不是必须的.例如,我不希望1234我的数据库中BCDE的1235项目和项目BCDF.

例子:

请注意url如何http://jsfiddle.net/XzKvP/具有XzKvP与页面关联的唯一5字符代码.我希望能够生成相同类型的代码.

goo.gl确实太:http://goo.gl/UEhtg有UEhtg

这是怎么做到的？

Answer 1

基于随机子串的解决方案并不好,因为输出会发生冲突.它可能过早地发生(运气不好),并且最终会在生成的值列表变大时发生.对于碰撞变高的概率,它甚至不必那么大(见生日攻击).

这个问题的好处是递增ID和它将在URL中显示的对应物之间的伪随机排列.这种技术保证了碰撞是不可能的,同时仍然产生一个与输入空间一样小的输出空间.

履行

我建议这个C#版本的Feistel密码具有32位块,3轮和圆形功能,其灵感来自伪随机生成器.

private static double RoundFunction(uint input)
{
    // Must be a function in the mathematical sense (x=y implies f(x)=f(y))
    // but it doesn't have to be reversible.
    // Must return a value between 0 and 1
    return ((1369 * input + 150889) % 714025) / 714025.0;
}

private static uint PermuteId(uint id)
{
    uint l1=(id>>16)&65535;
    uint r1=id&65535;
    uint l2, r2;
    for (int i = 0; i < 3; i++)
    {
        l2 = r1;
        r2 = l1 ^ (uint)(RoundFunction(r1) * 65535);
        l1 = l2;
        r1 = r2;
    }
    return ((r1 << 16) + l1);
}

要在base62字符串中表示置换ID:

private static string GenerateCode(uint id)
{
    return ToBase62(PermuteId(id));
}

该Base62函数与前一个答案相同,不同之处在于uint取代int(否则必须重写这些函数以处理负值).

自定义算法

RoundFunction是算法的秘诀.您可以将其更改为非公开版本,可能包括密钥.Feistel网络有两个非常好的属性:

• 即使提供的RoundFunction是不可逆的,该算法也保证PermuteId()了数学意义上的排列(意味着零冲突).

• 即使轻微改变圆函数内的表达式也会彻底改变最终输出值的列表.

要注意在圆形表达式中放置一些过于微不足道的东西会破坏伪随机效应,尽管它仍然可以在每个PermuteId输出的唯一性方面起作用.此外,在数学意义上不是函数的表达式将与算法不兼容,因此例如random()不允许涉及任何涉及的表达式.

可逆性

在当前形式中,PermuteId函数是它自己的逆,这意味着:

PermuteId(PermuteId(id))==id

因此,考虑到由程序生成的短字符串,如果你将其转换回uint用FromBase62功能,并给作为输入PermuteId(),将返回相应的初始ID.如果您没有用于存储[internal-ID/shortstring]关系的数据库,这非常酷:它们实际上并不需要存储!

产生更短的字符串

上述函数的范围是32位,即从0到0的大约40亿个值2^32-1.要在base62中表示该范围,需要6个字符.

只有5个字符,我们希望能够代表最多的62^5价值,这个数字有点不到10亿.如果输出字符串限制为5个字符,则应按如下方式调整代码:

• 发现N这N是偶数且2^N尽可能高但低于62^5.这是28,所以我们的实际输出范围62^5将达到2^28或约为2.68亿.

• in PermuteId,使用28/2=14位值l1而r1不是16位,同时注意不要忽略输入的单个位(必须小于2 ^ 28).

• 将结果乘以RoundFunction16383而不是65535,以保持在14位范围内.

• 在最后PermuteId,重新组合r1并l1形成一个14+14=28比特值而不是32.

相同的方法可以应用于4个字符,输出范围为2^22或大约4百万个值.

它是什么样子的

在上面的版本中,以id = 1开头的前10个生成的字符串是:

cZ6ahF
3t5mM
xGNPN
dxwUdS
ej9SyV
cmbVG3
cOlRkc
bfCPOX
JDr8Q
eg7iuA

如果我在圆函数中做了一个微不足道的改变,那就变成了:

ey0LlY
ddy0ak
dDw3wm
bVuNbg
bKGX22
c0s5GZ
dfNMSp
ZySqE
cxKH4b
dNqMDA

Answer 2

您可以将五个字母的代码视为base-62表示法中的数字:您的"数字"是26个小写字母和26个大写字母,以及0到9个数字(26 + 26 + 10)个数字.给定从0到62^5(等于916132832)的数字(例如,您的主键),您可以将转换为五位数的基数-62,如下所示:

private static char Base62Digit(int d) {
    if (d < 26) {
        return (char)('a'+d);
    } else if (d < 52) {
        return (char)('A'+d-26);
    } else if (d < 62) {
        return (char)('0'+d-52);
    } else {
        throw new ArgumentException("d");
    }
}

static string ToBase62(int n) {
    var res = "";
    while (n != 0) {
        res = Base62Digit(n%62) + res;
        n /= 62;
    }
    return res;
}

private static int Base62Decode(char c) {
    if (c >= '0' && c <= '9') {
        return 52 + c - '0';
    } else if (c >= 'A' && c <= 'Z') {
        return 26 + c - 'A';
    } else if (c >= 'a' && c <= 'z') {
        return c - 'a';
    } else {
        throw new ArgumentException("c");
    }
}

static int FromBase62(string s) {
    return s.Aggregate(0, (current, c) => current*62 + Base62Decode(c));
}

以下是如何生成加密强大的随机数(需要添加引用System.Security):

private static readonly RNGCryptoServiceProvider crypto =
    new RNGCryptoServiceProvider();

private static int NextRandom() {
    var buf = new byte[4];
    crypto.GetBytes(buf);
    return buf.Aggregate(0, (p, v) => (p << 8) + v) & 0x3FFFFFFF;
}