7

我想生成一个简短的唯一 ID，而无需检查冲突。

我目前正在做这样的事情，但是我当前生成的 ID 是随机的，并且在循环中检查冲突很烦人，并且如果记录数量显着增加，则会变得昂贵。

通常担心冲突不是问题，但我想要生成的唯一 ID 是一个简短的唯一字符串 5-8 个字符，字母数字，就像 tinyurl 一样。

编辑：我想从 5 个字符开始，如果我达到 6000 万个条目，然后转到 6.. 以此类推。

为此，我在想我可以使用对用户隐藏的 auto_increment 值，然后用一种MD5或其他方法向他们展示以从中生成唯一的字符串。

生成的字符串不应该是线性的，因此简单地将 auto_incremented ID 转换为base 36[0-9A-Z] 有点过于简单，但我将使用类似的函数。

编辑：安全不是问题，因为这不会用于保护信息。它只是一个较长字符串的快捷方式。谢谢你。

感谢您的建议，并对延误表示歉意。牙医..

4

8 回答 8

6

您需要通过构造正确的东西，即置换函数：这是一个将一个整数（您的顺序计数器）一对一的可逆映射到另一个的函数。一些示例（这些的任何组合也应该有效）：

  • 反转一些位（使用 XOR 的 fi，PHP 中的 ^）
  • 交换位的位置 (($i & 0xc) >> 2 | ($i & 0x3) << 2)，或者只是颠倒所有位的顺序
  • 添加一个常数值以您的最大范围为模（如果您将其与上面的相结合，则必须是两倍）

示例：此函数会将 0, 1, 2, 3, 5, .. 转换为 13, 4, 12, 7, 15, .. 直到 15 的数字：

$i=($input+97) & 0xf;
$result=((($i&0x1) << 3) + (($i&0xe) >> 1)) ^ 0x5;

编辑

更简单的方法是使用线性同余生成器（LCG，通常用于生成随机数），它由以下形式的公式定义：

X_n+1 = (a * X_n + c) mod m

对于a、c 和 m 的良好值，X_0、X_1 .. X_m-1 的序列将包含 0 和 m-1 之间的所有数字恰好一次。现在您可以从线性增加的索引开始，并使用 LCG 序列中的下一个值作为您的“秘密”密钥。

编辑2

实施：您可以设计自己的 LCG 参数，但如果您弄错了，它将无法覆盖整个范围（因此会有重复），因此我将使用本文中已发布并尝试过的一组参数：

a = 16807, c = 0, m = 2147483647

这为您提供了 2**31 的范围。使用 pack() 您可以将结果整数作为字符串获取，base64_encode() 使其成为可读字符串（最多 6 个有效字符，每字节 6 位），因此这可能是您的函数：

substr(base64_encode(pack("l", (16807 * $index) % 2147483647)), 0, 6)
于 2009-10-30T16:39:08.190 回答
1

您可能会生成当前日期时间/随机数的 MD5 哈希并将其截断为您需要的长度（5-8 个字符）并将其存储为 id 字段。

如果您使用将此信息存储在数据库中，则不需要使用 for 循环来进行冲突检查，但您可以只执行一个 select 语句 - 类似于

SELECT count(1) c FROM Table WHERE id = :id

其中 :id 将是新生成的 id。如果 c 大于 0，那么您知道它已经存在。

编辑

这可能不是最好的方法。但我会试一试，所以我想你需要的是以某种方式将一个数字转换为一个唯一的短字符串，而不是按顺序排列。

我想正如你所说，base64 编码已经将数字转换为短字符串。为了避免序列问题，您可以在自动生成的 id 到某个“随机”值（唯一映射）之间进行一些映射。然后您可以对这个唯一值进行 base64 编码。

您可以按如下方式生成此映射。有一个临时表存储从 1 到 10,000,000 的值。以随机顺序对其进行排序并将其存储到您的地图表中。

INSERT INTO MappingTable (mappedId) SELECT values FROM TemporaryTable ORDER BY RAND()

其中 MappingTable 将具有 2 个字段 id（您的自动生成的 id 将对此进行查找）和 mappedId（您将为其生成 base64 编码）。

当您接近 10,000,000 时，您可以再次重新运行上述代码并将临时表中的值更改为 10,000,001-20,000,000 或类似的值。

于 2009-10-30T14:50:54.883 回答
1

您可以使用按位异或来打乱一些位：

select thefield ^ 377 from thetable;

+-----+---------+
| a   | a ^ 377 |
+-----+---------+
| 154 |     483 |
| 152 |     481 |
|  69 |     316 |
|  35 |     346 |
|  72 |     305 |
| 139 |     498 |
|  96 |     281 |
|  31 |     358 |
|  11 |     370 |
| 127 |     262 |
+-----+---------+
于 2009-10-30T18:23:36.343 回答
0

我认为这永远不会真正安全，因为您只需要找到短唯一字符串背后的加密方法即可劫持 ID。在你的设置中检查循环中的碰撞真的有问题吗？

于 2009-10-30T14:42:44.883 回答
0

递增数字的 MD5 应该没问题，但我担心如果您将 MD5（通常为 128 位）截断为 5-8 个字符，您几乎肯定会破坏它作为唯一签名的能力。 ..

完全正确。特别是如果您达到 80% 的碰撞几率，截断的 MD5 将与任何随机数一样好，以保证其自身的唯一性，即毫无价值。

但是，既然您无论如何都在使用数据库，为什么不只使用 UNIQUE INDEX 呢？这样，唯一性检查由 MySQL 本身完成（以比使用循环更有效的方式）。只需尝试使用您的 MD5 生成的密钥进行 INSERT，如果失败，请重试...

于 2009-10-30T15:02:50.693 回答
0

如果您不能使用自动增量字段，并且想要一个绝对唯一的值，请使用UUID。如果您决定使用其他任何东西（除了自动增量），那么不检查碰撞是很愚蠢的。

于 2009-10-30T19:57:15.870 回答
0

这篇博文与您所追求的内容相近。

http://kevin.vanzonneveld.net/techblog/article/create_short_ids_with_php_like_youtube_or_tinyurl/

于 2010-02-25T18:29:25.377 回答
-1

递增数字的 MD5 应该没问题，但我担心如果您将 MD5（通常为 128 位）截断为 5-8 个字符，您几乎肯定会破坏它作为唯一签名的能力。 ..

于 2009-10-30T14:44:29.887 回答