Código único tipo Tinyurl: algoritmo potencial para evitar colisiones

Question

Tengo un sistema que requiere un código único de 6 dígitos para representar un objeto, y estoy tratando de pensar en un buen algoritmo para generarlos. Éstos son el pre-reqs:

• estoy usando un sistema de base-20 (sin tapas, números, vocales, o l para evitar confusión y malas palabras)
  • La base-20 permite 64 millones de combinaciones
• Insertaré potencialmente de 5 a 10 mil entradas a la vez, así que en teoría usaría inserciones en bloque, lo que significa que usar una clave única probablemente no sea eficiente o bonito (especialmente si hay comienza a haber muchas colisiones)
• No está fuera de qu estion para llenar el 10% de las combinaciones por lo que hay un gran potencial para una gran cantidad de colisiones
• quiero para asegurarse de que los códigos son no consecutivas

tuve una idea que parecía que iba a funcionar, pero No soy lo suficientemente bueno en matemáticas para descubrir cómo implementarlo: si comienzo en 0 e incremento en N, luego paso a base-20, parece que debería haber algún valor para N que me permita contar cada valor de 0-63,999,999 antes de repetir cualquiera.

Por ejemplo, al pasar de 0 a 9 usando N = 3 (modo 10 mod 3): 0, 3, 6, 9, 2, 5, 8, 1, 4, 7.

¿Hay alguna ¿Método matemático mágico para calcular los valores de N para un número mayor que puede contar a través de todo el rango sin repetir? Idealmente, el número que elija saltaría de un lado a otro del conjunto de modo que no fuera obvio que hubiera un patrón, pero no estoy seguro de qué tan posible sea.

Alternativamente, un algoritmo hash que garantice la unicidad para valores de 0-64 millones funcionaría, pero soy demasiado tonto como para saber si eso es posible.

Answer 1

Todo lo que necesita es un número que no comparte factores con su espacio de clave. El valor más fácil es usar un número primo. Puede googlear para números primos grandes, o usar http://primes.utm.edu/lists/small/10000.txt

Answer 2

Mi matemática está un poco oxidada, pero creo que solo necesita asegurarse de que el MCD de N y 64 millones sea 1. Iría con un número primo (ese no se divide de manera uniforme en 64 millones) solo por si acaso.

Answer 3

Cualquier número primo que no sea un factor de la longitud de la secuencia debería ser capaz de abarcar la secuencia sin repetir. Para 64000000, eso significa que no debes usar 2 o 5. Por supuesto, si no quieres que se generen de forma consecutiva, generarlos con una separación de 2 o 5 probablemente tampoco sea muy bueno. Personalmente me gusta el número 73973!

Answer 4

No reinventar la rueda: http://en.wikipedia.org/wiki/Universally_Unique_Identifier

Answer 5

@ Nick Lewis:

Bueno, sólo si el número primo no divide a 64 millones. Entonces, para los propósitos del interrogador, números como 2 o 5 probablemente no sean aconsejables.

Answer 6

Hay otro método para obtener un resultado similar (saltando sobre el conjunto completo de los valores sin repetirlo, no sin límites), sin utilizar los números primos - utilizando maximum length sequences, que puede generar utilizando registros de desplazamiento construidos especialmente.