26

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

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

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

我希望代码看起来是随机的，但不一定是这样。例如，我不希望1234我的数据库中BCDE的 item 是并且1235item 是BCDF.

例子：

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

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

这是怎么做到的？

4

3 回答 3

24

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

对这个问题有好处的是递增 ID 与其对应的 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()将是数学意义上的排列（这意味着零碰撞）。

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

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

可逆性

在其当前形式中，该PermuteId函数是它自己的逆函数，这意味着：

PermuteId(PermuteId(id))==id

uint因此，给定程序生成的短字符串，如果您使用函数将其转换回FromBase62，并将其作为输入提供给PermuteId()，则将返回相应的初始 ID。如果您没有数据库来存储 [internal-ID / shortstring] 关系，那就太酷了：它们实际上不需要存储！

制作更短的字符串

上述函数的范围是 32 位，也就是从 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 亿个值。

  • 在 中，PermuteId使用28/2=14位值代替 16 位，同时注意不要忽略输入的单个位（必须小于 2^28）。l1r1

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

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

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

它是什么样子的

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

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

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

埃0LLY
ddy0ak
dDw3wm
bVuNbg
bKGX22
c0s5GZ
dfNMSp
齐SqE
cxKH4b
dNqMDA
于 2013-07-11T11:39:05.397 回答
10

您可以将五个字母的代码视为 base-62 表示法中的数字：您的“数字”是 26 个小写字母和 26 个大写字母，以及从 0 到 9 的数字。（26+26+10）个数字。给定一个从 0 到62^5（等于 916132832）的数字（例如，您的主键），您可以将其转换为五位数的 base-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;
}
于 2012-04-24T14:29:28.280 回答
3

这就是我最终做的

（自 Daniel Vérité 的回答以来更新）：

class Program
{

    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 char Base62Digit(uint 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");
        }
    }
    private static string ToBase62(uint n)
    {
        var res = "";
        while (n != 0)
        {
            res = Base62Digit(n % 62) + res;
            n /= 62;
        }
        return res;
    }
    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);
    }


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

    static void Main(string[] args)
    {

        Console.WriteLine("testing...");

            try
            {

                for (uint x = 1; x < 1000000; x += 1)
                {
                    Console.Write(GenerateCode(x) + ",");

                }

            }
            catch (Exception err)
            {
                Console.WriteLine("error: " + err.Message);
            }

        Console.WriteLine("");
        Console.WriteLine("Press 'Enter' to continue...");
        Console.Read();
    }
}
于 2012-04-24T17:30:49.060 回答