c# - goo.gl 或 jsfiddle 等网站如何生成其 URL 代码？

Question

我想生成一个类似 goo.gl 的代码和 jsfiddle网站 ( http://jsfiddle.net/XzKvP/ )。

我尝试了不同的东西，这些东西给了我太大的 guid、重复的字母数字代码等。

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

我要密码看 随机，但确实如此 不是 不得不。
例如，我做 不是 想要项目1234在我的数据库中是 BCDE和 1235项目要BCDF .

示例:

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

goo.gl 也这样做:http://goo.gl/UEhtg有 UEhtg
这是怎么做的？

Answer 1

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

对这个问题有用的是 pseudo random permutation递增 ID 与其对应的将显示在 URL 中的 ID 之间。这种技术保证了碰撞是不可能的，同时仍然生成与输入空间一样小的输出空间。

实现

我建议使用这个 C# 版本的 Feistel cipher具有 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功能同the previous answer除了需要 uint而不是 int (否则这些函数将不得不重写以处理负值)。

自定义算法
RoundFunction是算法的秘诀。您可以将其更改为非公开版本，可能包括 key 。 Feistel 网络有两个非常好的特性:

即使提供 RoundFunction不可逆，算法保证PermuteId()将是数学意义上的排列(这意味着零碰撞)。

即使稍微改变 round 函数内的表达式，也会极大地改变最终输出值的列表。

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

可逆性

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

PermuteId(PermuteId(id))==id

所以给定一个程序产生的短字符串，如果你把它转换回 uint与 FromBase62函数，并将其作为 PermuteId() 的输入，这将返回相应的初始 ID。如果您没有数据库来存储 [internal-ID/shortstring] 关系，那就太酷了:它们实际上不需要存储!

生产更短的琴弦

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

只有 5 个字符，我们希望最多表示 62^5值，略低于 10 亿。如果输出字符串限制为 5 个字符，则应按如下方式调整代码:

查找 N使得 N是偶数和2^N尽可能高但低于 62^5 .那是 28，所以我们的实际输出范围适合 62^5将是 2^28或大约 2.68 亿个值。

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

乘以 RoundFunction 的结果由 16383 而不是 65535，以保持在 14 位范围内。

末PermuteId , 重组 r1和 l1形成14+14=28位值而不是 32。

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

它是什么样子的

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

cZ6ahF
3t5mM
xGNPN
dxwUdS
ej9SyV
CMBVG3
科尔克
bfCPOX
JDr8Q
eg7iuA

如果我对 round 函数做一个微不足道的改变，那就变成:

伊莉莉
ddy0ak
dDw3wm
布瓦格
bKGX22
c0s5GZ
DFNMSp
ZySqE
cxKH4b
dNqMDA