像goo.gl或jsfiddle这样的网站如何生成其URL代码？

Question

我想生成类似goo.gl和jsfiddle网站（http://jsfiddle.net/XzKvP/）的代码。

我尝试了各种不同的操作，这些操作给了我太大的引导，重复的字母数字代码等。

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

我想要的代码 看起来 是随机的，但它 不是 必须的。例如，我 不
希望1234数据库中BCDE的1235项目为并且项目为BCDF。

例子：

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

goo.gl也这样做：http ://goo.gl/UEhtg有UEhtg

怎么做？

Answer 1

基于随机子字符串的解决方案不好，因为输出会发生冲突。它可能会过早发生（运气不好），并且最终会在生成的值列表变大时发生。冲突的可能性甚至不必变得很大（请参阅生日攻击）。

对这个问题有好处的是，递增ID与对应ID之间的伪随机置换将显示在URL中。该技术保证了碰撞是不可能的，同时仍会生成与输入空间一样小的输出空间。

实作

我建议此Feistel密码的
C＃版本具有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。如果您没有用于存储[内部ID
/短字符串]关系的数据库，那就太酷了：实际上并不需要存储它们！

产生更短的弦

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

仅用5个字符，我们就可以希望最多代表62^510亿以下的值。如果输出字符串限制为5个字符，则应对代码进行如下调整：

• 找出N这样一个N偶数，2^N并尽可能高但低于62^5。那是28，所以我们适合的实际输出范围62^5将是2^28大约2.68亿个值。

• 在中PermuteId，请使用和而不是16位的28/2=14位值，同时注意不要忽略输入的单个位（其必须小于2 ^ 28）。l1``r1

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

• 在的末尾PermuteId，重新组合r1并l1形成一个14+14=28位值，而不是32。

相同的方法可以应用于4个字符，输出范围为2^22，或约400万个值。

它是什么样子的

在上述版本中，以id = 1开头的前10个生成的字符串为：

cZ6ahF
3t5mM
xGNPN
dxwUdS
ej9SyV
cmbVG3
cOlRkc
bfCPOX
JDr8Q
eg7iuA

如果我对round函数进行微不足道的更改，则变为：

ey0LlY
ddy0ak
dw3wm
bVuNbg
bKGX22
c0s5GZ
dfNMSp
ZySqE
cxKH4b
dNqMDA