创建独特的不可猜测的基数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%保证碰撞(否)更多可用的钥匙).由于生日效应,你会更快,更快地得到碰撞.有了这么小的键空间,就没有办法避免碰撞 - 你需要进行某种碰撞恢复.

你可以生成一个ID,直到它没有碰撞 - 但是当密钥空间被填充时,这将逐渐变慢:想象一个[az]的密钥空间,已经采用了[an]和[pz] - 现在每个新的随机ID都是更容易发生碰撞而不是碰撞; 当你完全填满键空间时,循环根本不会终止.

我建议的算法在这方面可能过于谨慎:如果发现冲突,它将逐渐尝试更长的ID(因为它假定"collision =>不可能检查更短的密钥空间").虽然效率不高,但可能会在几次迭代中找到非碰撞ID.