¿Generación de ID única corta de PHP usando auto_increment?

StackOverflow https://stackoverflow.com/questions/1650185

Pregunta

Me gustaría generar una identificación corta y única sin tener que buscar colisiones.

Actualmente hago algo como esto, pero la identificación que genero actualmente es aleatoria y verificar colisiones en un bucle es molesto y se volverá costoso si el número de registros aumenta significativamente.

Normalmente, preocuparse por las colisiones no es un problema, pero la identificación única que quiero generar es una cadena corta y única de 5-8 caracteres, alfanumérica, como lo hace tinyurl.

EDITAR: Me gustaría comenzar con 5 caracteres y si llego a 60 millones de entradas, pasar a 6 ... y así sucesivamente.

Para este fin, estaba pensando que podría usar un valor de auto_increment que esté oculto para los usuarios, y presentarles en su lugar un MD5 o algún otro método para generar una cadena única a partir de eso.

Las cadenas generadas no deberían parecer lineales, por lo que simplemente convertir el ID autoincrementado en base 36 [0-9A-Z] es un poco demasiado simplista, pero una función como esa es a donde voy con esto.

EDITAR: la seguridad no es un problema, ya que no se utilizará para proteger la información. Es simplemente un acceso directo a una cadena más larga. Gracias.

Gracias por sus sugerencias y disculpe la demora. Dentista ..

¿Fue útil?

Solución

Necesitará algo que sea correcto por construcción, es decir, una función de permutación: esta es una función que realiza un mapeo reversible uno a uno de un entero (su contador secuencial) a otro. Algunos ejemplos (cualquier combinación de estos también debería funcionar):

  • invertir algunos de los bits (por ejemplo, usando un XOR, ^ en PHP)
  • intercambiando los lugares de bits (($ i & amp; 0xc) > > 2 | ($ i & amp; 0x3) < < ; 2), o simplemente invirtiendo el orden de todos los bits
  • agregando un módulo de valor constante a su rango máximo (debe ser un factor de dos, si combina esto con los anteriores)

Ejemplo: esta función convertirá 0, 1, 2, 3, 5, .. en 13, 4, 12, 7, 15, .. para números hasta 15: 

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

EDIT

Una forma más fácil sería usar un generador congruencial lineal (LCG, que generalmente se usa para generar números aleatorios), que se define mediante una fórmula de la forma: 

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

Para buenos valores de a, c y m, la secuencia de X_0, X_1. X_m-1 contendrá todos los números entre 0 y m-1 exactamente una vez. Ahora puede comenzar desde un índice que aumenta linealmente y usar el valor next en la secuencia LCG como su & Quot; secret & Quot; clave.

EDIT2

Implementación: Puede diseñar sus propios parámetros LCG , pero si se equivoca, no cubrirá el rango completo (y por lo tanto tienen duplicados), así que usaré un conjunto de parámetros publicado y probado aquí de este documento : 

a = 16807, c = 0, m = 2147483647

Esto le da un rango de 2 ** 31. Con pack () puede obtener el entero resultante como una cadena, base64_encode () lo convierte en una cadena legible (de hasta 6 caracteres significativos, 6 bits por byte), por lo que esta podría ser su función: 

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

Otros consejos

Probablemente podría generar un hash MD5 de la fecha / hora actual / número aleatorio y truncarlo a la longitud que necesita (5-8 caracteres) y almacenarlo como el campo id.

Si está utilizando el almacenamiento de esta información en una base de datos, no necesita usar un bucle for para hacer la verificación de colisión, pero podría simplemente hacer una declaración de selección, algo así como 

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

donde: id sería la nueva ID generada. Si c es mayor que 0, entonces sabe que ya existe.

EDIT

Puede que esta no sea la mejor manera de hacerlo. Pero lo intentaré, así que supongo que lo que necesita es convertir los números en una cadena corta única y no está en secuencia.

Supongo que, como dijiste, la codificación base64 ya hace la conversión de números a cadenas cortas. Para evitar el problema de la secuencia, podría tener algún mapeo entre sus identificadores autogenerados a algunos & "; Random &"; valor (mapeo único). Entonces puede codificar en base64 este valor único.

Puede generar esta asignación de la siguiente manera. Tener una tabla temporal para almacenar valores de 1 - 10,000,000. Ordénelo en orden aleatorio y guárdelo en su tabla de mapas. 

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

Donde MappingTable tendría la identificación de 2 campos (su identificación autogenerada se vería en contra de esto) y mappedId (que es para lo que generaría la codificación base64).

A medida que se acerque a 10,000,000, puede volver a ejecutar el código anterior y cambiar los valores en la tabla temporal con 10,000,001-20,000,000 o algo así.

puede usar un XOR bit a bit para codificar algunos de los 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 |
+-----+---------+

Creo que esto nunca será realmente seguro, ya que solo necesita encontrar el método de cifrado detrás de la cadena corta y única para secuestrar una ID. ¿Es realmente problemático comprobar las colisiones en un bucle en su entorno?

  

Un MD5 de un número incremental   debería estar bien, pero me preocupa que si   estás truncando tu MD5 (que es   normalmente 128 bits) hasta 5-8   personajes, casi seguro   ser perjudicial es su capacidad para actuar como   una firma única ...

Completamente cierto. Especialmente si alcanza una probabilidad de colisión del 80%, un MD5 truncado será tan bueno como cualquier número aleatorio para garantizar la unicidad por sí mismo, es decir, sin valor.

Pero dado que de todos modos está utilizando una base de datos, ¿por qué no usar un ÍNDICE ÚNICO? De esta manera, MySQL realiza la comprobación de uniquness (de una manera mucho más eficiente que usar un bucle). Simplemente intente hacer el INSERT con su clave generada por MD5, y si falla, intente nuevamente ...

Si no puede usar un campo de incremento automático y desea un valor único absolutamente , use UUID . Si decide usar cualquier otra cosa (además del incremento automático), sería una tontería NO comprobar las colisiones.

Un MD5 de un número incremental debería estar bien, pero me preocupa que si está truncando su MD5 (que normalmente es de 128 bits) a 5-8 caracteres, seguramente dañará su capacidad para actuar como un firma única ...

No afiliado a StackOverflow
scroll top