php - 创建唯一的不可猜测的 base 36 id

Question

对于类似于 URL 缩短服务的应用程序，我想创建不可猜测的 ID，我想你们都很熟悉。这是此类 ID 的示例:

http://example.com/sd23t9

什么是一种好的、有效的技术来生成这些，并且在将它们作为主键插入数据库表时发生冲突的风险最小(或没有)？

编辑:
Piskvor 提出了一个很好的观点。我应该提到我的意思是在达到 36^6 限制之前将碰撞风险降至最低。

编辑 2
嗯，废话，他的观点当然比这更能说明问题。嗯。预生成一个带有 id 的表，也许(就像我已经在其他地方读过的那样)？当我受到 36^6 和非连续约束的约束时，这可能是最有效的技术吗？

Answer 1

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%保证(没有更多可用 key )。由于birthday problem ，你会很快发生碰撞。对于如此小的 key 空间，没有办法避免冲突 - 您需要进行某种冲突恢复。

您可以生成一个 ID，直到它不发生冲突 - 但随着键空间被填充，这会逐渐变慢:想象一个 [a-z] 的键空间，其中 [a-n] 和 [p-z] 已经被占用 - 现在每一个新的随机 ID 更有可能发生冲突；当您完全填满键空间时，循环根本不会终止。

我提出的算法在这方面可能过于谨慎:如果发现冲突，它将尝试逐渐增加 ID(因为它假设“冲突 => 检查较短的键空间不可行”)。尽管效率不高，但它可能会在几次迭代内找到一个非冲突 ID。