math - programacion - ¿Es seguro asumir que un GUID siempre será único?
manual de programacion android pdf (6)
Sé que hay una posibilidad mínima de un choque, pero si generase un lote de 1000 GUID (por ejemplo), ¿sería seguro asumir que son únicos para guardar las pruebas de cada uno?
Pregunta extra
¿Una forma óptima de probar un GUID por singularidad? ¿Filtro Bloom tal vez?
En general, sí, es seguro asumirlo.
Si su generador de GUID es verdaderamente aleatorio, las posibilidades de un choque dentro de un 1000 GUID son extraordinariamente pequeñas.
Por supuesto, eso supone un buen generador de GUID. Entonces, la pregunta es realmente, ¿en qué medida confía en la herramienta que está utilizando para generar GUID y tiene sus propias pruebas?
Mientras que una colisión es posible, es ALTAMENTE improbable. (Matemáticas aquí .) Es seguro asumir que son de hecho distintos.
Por lo general, es una suposición bastante segura.
Respuesta corta: para fines prácticos, sí.
Sin embargo, ¡debes considerar la paradoja del cumpleaños!
He calculado algunas probabilidades de colisión representativas. Con UUID de 122 bits como se especifica en el artículo de Wikipedia , la probabilidad de colisión es 1/2 si genera al menos 2.71492e18 UUID. Con 10 ^ 19 UUID, la probabilidad es 0.999918. Con 10 ^ 17 UUID, 0.000939953.
Algunos números para comparar se pueden encontrar en Wikipedia. De modo que puede asignar con seguridad un UUID para cada humano que haya vivido, cada galaxia en el universo observable, cada pez en el océano y cada hormiga individual en la Tierra. Sin embargo , las colisiones son casi ciertas si genera un UUID para cada transistor que la humanidad produce en un año, cada insecto en la Tierra, cada grano de arena en la Tierra, cada estrella en el universo observable, o algo más grande.
Si genera mil millones de UUID por segundo, tomaría alrededor de 36 años obtener una probabilidad de colisión del 10%.
Eventualmente, probablemente habrá una colisión entre el conjunto de UUID generados a lo largo de la historia humana. Aún así, la probabilidad de que los UUID colisionados se usen para el mismo propósito es infinitamente pequeña, por lo que no hay ningún problema en la práctica.
Sí tu puedes. Como los GUID tienen 128 bits de largo, hay una posibilidad mínima de un choque, pero la palabra "minuto" no es lo suficientemente fuerte. Hay tantos GUID que si genera varios billones de ellos aleatoriamente, es más probable que sea alcanzado por un meteorito que tener incluso una colisión (de Wikipedia ). Y si no los está generando de forma aleatoria, pero están usando, por ejemplo , el algoritmo MAC-dirección-y-hora-marca, también serán únicos, ya que las direcciones MAC son únicas entre las computadoras y las marcas de tiempo son únicas en su computadora.
Editar 1: para responder a su pregunta de bonificación, la forma óptima de probar un conjunto de GUID para la unicidad es simplemente asumir que todos son únicos. ¿Por qué? Porque, dada la cantidad de GUID que está generando, las probabilidades de una colisión GUID son menores que las probabilidades de que un rayo cósmico se mueva un poco en la memoria de su computadora y arruine la respuesta dada por cualquier algoritmo "preciso" que le interese correr. (Consulte esta respuesta de para las matemáticas).
Hay una enorme cantidad de GUID por ahí. Para citar la Guía del autoestopista de Douglas Adams para la galaxia :
"El espacio", dice, "es grande. Realmente grande. Simplemente no vas a creer lo enormemente grande que es. Quiero decir, puedes pensar que está muy lejos en el camino hacia el químico, pero eso es solo cacahuetes en el espacio. , escucha…"
Y dado que hay alrededor de 7 × 10 22 estrellas en el universo , y poco menos de 2 128 GUID, entonces hay aproximadamente 4.86 × 10 15 -casi cinco cuatrillones -GUID por cada estrella. Si cada una de esas estrellas tuviese un mundo con una población próspera como la nuestra, entonces alrededor de todas y cada una de las estrellas, cada humano o extraterrestre que alguna vez haya vivido tendría derecho a más de cuarenta y cinco mil GUID. Para cada persona en la historia en cada estrella en el universo. El espacio GUID está en el mismo nivel de envergadura que el tamaño del universo entero. No necesitas preocuparte.
( Editar 2: Reflexionando sobre esto: wow. No me había dado cuenta de lo que esto significaba. El espacio GUID es incomprensiblemente masivo. Estoy algo sobrecogido).
Un análisis de la posibilidad de colisión está disponible en Wikipedia: http://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates
Como se menciona en el enlace, esto se verá afectado por las propiedades del generador de números aleatorios.
También existe la posibilidad de un error en el código generador de GUID; aunque las posibilidades son bajas, probablemente sean más altas que las posibilidades de una colisión basada en las matemáticas.
Un filtro Bloom podría ser apropiado; puede decirle rápidamente si un GUID es único, pero existe la posibilidad de una indicación falsa de una colisión. Un método alternativo si está probando un lote a la vez es ordenar el lote y comparar cada elemento sucesivo.