对于类似于 URL 缩短服务的应用程序，我想创建不可猜测的 id，我想你们都熟悉。以下是此类 id 的示例：
在将这些作为主键插入数据库表中时，什么是生成这些的良好且有效的技术，并且碰撞风险最小（或没有）？
编辑：
Piskvor 当然提出了一个很好的观点。我应该提到我的意思是在达到 36^6 限制之前的最小碰撞风险。
编辑 2
呃，废话，他的观点当然远不止于此。嗯。那么预生成一个带有 id 的表，也许（就像我已经在别处读过的那样）？当我被绑定到 36^6 和非连续约束时，这会是最有效的技术吗？
Set ID length. // e.g. 6
do {
Generate a short random ID of the given length
Collision?
- No:
DONE!
- Yes:
increase ID length
} while true
对于任何有限的 ID 长度，总是存在冲突的风险：从您的示例中假设您有 [a-z0-9]{6} 个 ID，只要您有 2,176,782,336 个 ID，就可以 100% 保证发生冲突（没有更多可用的密钥）。由于生日问题，你会很快发生碰撞。有了这么小的键空间，就没有办法避免冲突——你需要进行某种冲突恢复。
您可以生成一个 ID，直到它不发生冲突 - 但随着键空间的填充，这将逐渐变慢：想象一个 [az] 的键空间，已经使用了 [an] 和 [pz] - 现在每个新的随机 ID 都是更有可能发生碰撞；当你完全填满键空间时，循环根本不会终止。
我提出的算法在这方面可能过于谨慎：如果它发现冲突，它将逐渐尝试更长的 ID（因为它假设“冲突 => 检查较短的键空间不可行”）。虽然效率不高，但很可能会在几次迭代中找到非冲突 ID。
有点奇怪的想法。为什么不使用排列？例如，当您生成第一个 id 时，您有一组值 [0-9a-z]。您按字典顺序进行第一次排列。然后是第二个，依此类推。为了使它看起来不那么容易猜测，您可以更改字典顺序的规则。说“a”在“t”或类似的东西之后。您也可以使用元组而不是完整排列。这将确保没有碰撞。
这个想法实际上是关于制作某种双向哈希函数。基本上，如果您能够以某种方式对数字“1”进行编码以获得类似“q8d3dw”的内容，并且能够将“q8d3dw”解码回“1”，那么您可以确定此函数将为您提供所有值的唯一字符串从 1 到 36^6。
问题实际上是选择这个功能。简单的方法是将“1”关联到“000000”，将“2”关联到“000001”，将“12”关联到“00000b”。基本上按字典顺序排列所有可用的字符串，并在等于 id 的位置上选择字符串。然而，这真的很容易猜到。所以你可以做的是人为地改变字典顺序的规则。说而不是有一个正常的顺序（0,1,2,3...a,b,c...x,y,z），你可以把它洗一下，得到类似的东西（a,5,t,3 ...）。这将产生更模糊的结果。但是它仍然很容易猜测，因为第一个元素是“aaaaaa”，第二个是“aaaaa5”，然后是“aaaaat”。所以你可以进一步改变字典顺序的规则，制作它们取决于角色的位置。说第二个字符 id (a,5,t,3...) 的第一个字符 id (y,7,3,r...) 的顺序，等等。
现在，我不会发布任何伪代码，因为它会很长。而且我不建议你走这条路，除非你有兴趣创建这种有趣的算法:)。但是，如果您使用这条路线，它可能是一种非常有效的生成此 ID 的方法，不会发生冲突。我建议您阅读 Donald Knuth 博士的“计算机编程艺术”第 4 卷。在实现此类算法方面有很多建议。
@ivan：这是一个实现。
首先你需要 6 个字符串，下面是生成它们的代码：
$letters = range('a', 'z');
$numbers = range(0, 9);
$char_list = array_merge_recursive($letters, $numbers);
for ($i = 0; $i <= 5; $i++) {
shuffle($char_list);
echo '$mysterykey[' . $i . "] = '" . implode($char_list) . "';\n";
}
然后你可以在函数中使用它的输出：
function int_to_x36($value) {
$mysterykey[0] = 'awkbs81t3jyg20v4qhoxzcuenr65dfimlp97';
$mysterykey[1] = 'ut17qclz96n3msky8jwp4r25gdvhxo0biaef';
$mysterykey[2] = 'cewszx142nph05mi9ulafbdvy36o8gq7trjk';
$mysterykey[3] = '37hp28wjdqe5vnlzxofrsybu4im90k16agtc';
$mysterykey[4] = 'n9a3jksl5ct0eqfzo7pvgyd4m2hiu18xrb6w';
$mysterykey[5] = 'mq0nbk3zs529gu4tecli8j176vardxoypfwh';
$x36 = array();
for ($i = 5; $i >= 0; $i--) {
$x36[$i] = 0;
$y = pow(36, $i);
if ($value >= $y) {
$z = floor($value/$y);
$value = $value - ($z * $y);
$x36[$i] = $z;
}
}
$encoded = '';
for ($i = 0; $i <= 5; $i++) {
$encoded .= $mysterykey[$i][$x36[$i]];
}
return $encoded;
}
function x36_to_int($value) {
$mysterykey[0] = 'awkbs81t3jyg20v4qhoxzcuenr65dfimlp97';
$mysterykey[1] = 'ut17qclz96n3msky8jwp4r25gdvhxo0biaef';
$mysterykey[2] = 'cewszx142nph05mi9ulafbdvy36o8gq7trjk';
$mysterykey[3] = '37hp28wjdqe5vnlzxofrsybu4im90k16agtc';
$mysterykey[4] = 'n9a3jksl5ct0eqfzo7pvgyd4m2hiu18xrb6w';
$mysterykey[5] = 'mq0nbk3zs529gu4tecli8j176vardxoypfwh';
$value36 = str_split($value);
$x36 = array();
for ($i = 0; $i <= 5; $i++) {
$x36[$i] = strpos($mysterykey[$i], $value36[$i]);
}
$x = 0;
for ($i = 5; $i >= 0; $i--) {
$x += $x36[$i] * pow(36, $i);
}
return $x;
}
我确定我忽略了一些东西，但它似乎正在工作。
例如大随机数和 SHA-256 哈希？您可以稍后将其缩短以满足您的需要。
如果站点足够大，我的意思是大- 如“我们需要每秒分配数百个新 ID”（这将有其他问题，例如在一年内耗尽 36^6 键空间），您可以预先生成键并分配它们。
以下是一个伪代码示例——在这样一个大流量的站点中，您可能需要优化所使用的算法。
预生成是微不足道的 - 只需从 开始000000并一直到zzzzzz，将每一行插入表中并将它们标记为未使用：
ID | used
==============
000000 0
000001 0
...
zzzzzz 0
当您收到新 ID 的请求时，随机选择一个并将其标记为已使用（危险！并发问题！）：
SELECT ID FROM ids WHERE RAND() LIMIT 1
UPDATE ids SET used = 1, url=what_you_want_shortened WHERE ID = whatever_you_got_from_previous_query
您会遇到效率问题（例如WHERE RAND()，使用表锁定等），但这是可行的。
如果您不反对引入 .NET dll，我已经创建了一个项目来执行此操作。源代码在 GitHub 上，二进制文件在IdGenerator NuGet 包中。
它为您提供用户指定长度的有序序列和/或随机值，全部以 base-36 为单位。ID 是普遍唯一的，即使有多个 id 生成器实例或在分布式环境中也是如此。
var generator = new Base36IdGenerator(
numTimestampCharacters: 11,
numServerCharacters: 4,
numRandomCharacters: 5,
reservedValue: "",
delimiter: "-",
delimiterPositions: new[] {15, 10, 5});
// This instance would give you a 20-character Id, with an
// 11-character timestamp, 4-character servername hash,
// and 5 character random sequence. This gives you 1.6 million
// hash combinations for the server component, and 60 million
// possible combinations for the random sequence. Timestamp is
// microseconds since epoch:
Console.WriteLine(generator.NewId());
// 040VZC6SL01003BZ00R2
// Argument name specified for readability only:
Console.WriteLine(generator.NewId(delimited: true));
// 040VZ-C6SL0-1003B-Z00R2
当然，如果您对不可猜测的字符串比对有序序列更感兴趣，则可以使用 GetRandomString 方法：
// 6-characters give you a little over 2 billion possible
// combinations (36 ^ 6). 7 characters is about 78 billion.
Console.WriteLine(generator.GetRandomString(length: 6));
其背后的基本原理是：
0至所需长度Base36 编码器本身来自http://www.stum.de/2008/10/20/base36-encoderdecoder-in-c/。