PHP curto geração identificação única usando auto_increment?

Question

Eu gostaria de gerar um curto, identificação única, sem ter que verificar se há colisões.

Actualmente, eu fazer algo assim, mas o ID Eu geram atualmente é aleatório e verificação de colisões em um loop é chato e vai ficar caro se o número de registros cresce significativamente.

Normalmente se preocupar com as colisões não é um problema, mas a identificação única Eu quero gerar uma corda curta única 5-8 caracteres, alfanumérico, como tinyurl faz.

EDIT:. Gostaria de começar com 5 caracteres e se eu acertar 60 milhões de entradas, em seguida, ir para 6 .. assim por diante e assim por diante

Para este fim, eu estava pensando que eu poderia usar um valor auto_increment que está escondido dos usuários, e apresentá-los ao invés com um MD5 ou algum outro método para gerar uma seqüência única a partir daí.

cadeias de caracteres geradas não deve aparecer para ser linear, tão simplesmente converter o ID auto_incremented em base 36 [0-9A-Z] é um pouco demasiado simplista, mas uma função de algo como isso é onde eu estou indo com isso.

EDIT: Segurança não é um problema como este não vai ser usado para informações seguras. É simplesmente um atalho para uma cadeia mais longa. Obrigado.

Obrigado por suas sugestões e desculpe pelo atraso. Dentista ..

Answer 1

Você vai precisar de algo que é correto por construção, ou seja, uma permutação função: esta é uma função que faz, um mapeamento reversível de um-para-um de um inteiro (seu contador seqüencial) para outro. Alguns exemplos (qualquer combinação destes também deve funcionar):

• invertendo alguns dos bits (f.i. usando um XOR, ^ em PHP)
• trocando os lugares de bits (($ i & 0xc) >> 2 | ($ i & 0x3) << 2), ou apenas invertendo a ordem de todos os bits
• adicionando um valor constante modulo seu alcance máximo (deve ser um fator de dois, se você está combinando isso com as acima)

Exemplo: esta função irá converter 0, 1, 2, 3, 5, .. em 13, 4, 12, 7, 15, .. para números até 15:

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

Editar

Uma forma mais simples seria a utilização de um gerador linear congruente (LCG, que é geralmente utilizado para a geração de números aleatórios), que é definida por uma fórmula da forma:

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

bons valores de a, c e m, a sequência de x_0, X_1. . x_m-1 irá conter todos os números entre 0 e m-1 exatamente uma vez. Agora você pode começar a partir de um índice linearmente aumentando, e usar o próximo valor na seqüência LCG como sua chave "segredo".

EDIT2

Implementação: Você pode projetar seu próprio LCG parâmetros , mas se você errar não vai cobrir o gama completa (e, portanto, têm duplicatas) por isso vou usar um conjunto publicado e tentou de parâmetros aqui de neste artigo :

a = 16807, c = 0, m = 2147483647

Isto dá-lhe uma gama de 2 ** 31. Com pack () você pode obter o inteiro resultante como uma string, base64_encode () faz com que seja uma string legível (de até 6 caracteres significativos, 6 bits por byte) assim que esta poderia ser a sua função:

substr(base64_encode(pack("l", (16807 * $index) % 2147483647)), 0, 6)

Answer 2

Você provavelmente poderia gerar um hash MD5 do datetime número atual / random e truncar-lo para o comprimento que você precisa (5-8 caracteres) e armazená-lo como o campo id.

Se você estiver usando armazenar essas informações em um banco de dados, você não precisa usar um loop for para fazer a verificação de colisão, mas você poderia apenas fazer uma declaração de seleção - algo como

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

em que: id seria o id recém-gerado. Se c é maior que 0, então você sabe que já existe.

Editar

Isto pode não ser a melhor maneira de ir sobre ele. Mas eu vou dar-lhe um tiro, então eu acho que você precisa é alguma maneira de converter um número em uma string única curta e que não está em seqüência.

Eu acho que como você disse, base64 já codificação acontece com o número de conversão de cadeia curta. Para evitar o problema sequência que poderia ter algum mapeamento entre o id gerado automaticamente da algum valor "aleatório" (mapeamento exclusivo). Então você pode base64 codificar esse valor único.

Você pode gerar esse mapeamento como segue. Tenha um temporários armazenar valores de tabela de 1 - 10.000.000. Classificá-lo em ordem aleatória e armazená-lo em você mapa da tabela.

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

Onde MappingTable teria o ID de 2 campos (o id gerado automaticamente iria olhar para cima contra este) e mappedId (que é o que você iria gerar a codificação base64 para).

Como você se aproximar de 10.000.000 você poderia voltar a executar o código acima novamente e mudar os valores na tabela temporária com 10,000,001-20,000,000 ou algo parecido.

Answer 3

Você pode usar um XOR bit a bit para embaralhar alguns dos bits:

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 |
+-----+---------+

Answer 4

Eu acho que isso nunca vai ser realmente seguro, como você só precisa encontrar o método de criptografia por trás da cadeia exclusiva curto para sequestrar um ID. Está verificando colisões em um loop que realmente problemático em sua configuração?

Answer 5

Um MD5 de um número incrementando deve estar bem, mas me preocupo que, se você está truncando o MD5 (que é normalmente 128 bits) até 08/05 caracteres, você quase certamente ser danificá-lo de capacidade para actuar como uma única assinatura ...

completamente verdade. Especialmente se você chegar ao seu 80% de chance de colisão um MD5 truncado será tão bom como qualquer número aleatório para singularidade garantia por si só, ou seja, sem valor.

Mas desde que você está usando um banco de dados de qualquer maneira, por que não usar um índice exclusivo? Desta forma, a verificação uniquness é feito (de uma forma muito mais eficiente do que usar um loop), por si só MySQL. Basta tentar fazer o INSERT com sua chave MD5 gerado, e se ele falhar, tente novamente ...

Answer 6

Se você não pode usar um campo de incremento automático, e quer uma absolutamente valor único, uso UUID . Se você decidir usar qualquer outra coisa (além de incremento automático), você seria tolo para não buscar por colisões.

Answer 7

Este post tem algo parecido com o que você está depois.

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

Answer 8

Um MD5 de um número incrementando deve estar bem, mas me preocupo que se você está truncando o MD5 (que é normalmente 128 bits) para baixo para 5-8 caracteres, você quase certamente será danificá-lo da capacidade de agir como um assinatura única ...