Si usted va a construir, por ejemplo, una estructura de directorios donde un directorio es nombrado por un commit en un repositorio de Git, y usted quiere que sea lo suficientemente corto como para hacer que tus ojos no sangran, pero lo suficiente como para que la probabilidad de colisión sería insignificante, ¿cuánto de la SHA la subcadena se requiere en general?

Digamos que yo quiero para identificar este cambio: https://github.com/wycats/handlebars.js/commit/e62999f9ece7d9218b9768a908f8df9c11d7e920

Puedo utilizar tan poco como los primeros cuatro caracteres:
https://github.com/wycats/handlebars.js/commit/e629

Pero siento que sería muy arriesgado. Pero ssuming un código base que, a través de un par de años, podría tener—dicen—30k cambios, ¿cuáles son las posibilidades de colisión si yo uso 8 caracteres? 12? Hay un número que generalmente se considera aceptable para este tipo de cosas?

5 Comentarios

  1. 204

    Esta pregunta es en realidad responde en El capítulo 7 de la Pro Git libro:

    Generalmente, entre ocho y diez caracteres son más que suficientes para ser únicos
    dentro de un proyecto. Uno de los mayores Git proyectos, el kernel de Linux,
    está empezando a necesitar 12 caracteres de los posibles 40 a permanecer
    único.

    7 dígitos es el Git predeterminado para un corto SHA, así que está bien para la mayoría de los proyectos. El Núcleo del equipo han aumentado de ellos varias veces, como se ha mencionado, porque la han varios cientos de miles de se compromete. Así que para su ~30k compromete, 8 o 10 dígitos debe estar perfectamente bien.

    • También tenga en cuenta que git es bastante inteligente cuando se trata de esto. Puede establecer la abreviatura corto, digamos, a 4, y git será de 4 dígitos para como muchos hash como puede, pero cambiar a 5 o más cuando se sabe que la abreviatura no es única…
    • Tenga en cuenta también, sin embargo, que esto sólo se aplica por el momento Git imprime el SHA. Si en «guardar» abreviado SHAs (por ejemplo, en los registros, correos electrónicos, mensajería instantánea, etc.) y luego utilizarlo para referirse a los comete, que podría no ser único! Aunque, sin duda, raro para el normal longitudes como de 7 a 12 caracteres, si tienes que ir a 4 o 5, y obtener unos diez mil nuevos objetos (o cometa, dependiendo del contexto), este hecho podría volver a morder.
  2. 123

    Nota: usted puede pedir git rev-analizar-a corto para el menor y, sin embargo, único SHA1.

    Consulte «git obtener corto hash de regular hash«

    git rev-parse --short=4 921103db8259eb9de72f42db8b939895f5651489
    92110
    

    Como se puede ver en el ejemplo, el SHA1 tiene una longitud de 5 incluso si especifica una longitud de 4.


    Para grandes repos, 7 no es suficiente desde el 2010, y cometer dce9648 por Linus Torvalds a sí mismo (git 1.7.4.4, Octubre de 2010):

    El valor predeterminado de 7 viene desde bastante temprano en git desarrollo, cuando siete dígitos hexadecimales fue mucho (que cubre alrededor de 250 millones de valores de hash).

    Pensaba entonces que 65k revisiones fue mucho (que era lo que estábamos a punto de golpear en BK), y cada revisión tiende a ser aproximadamente de 5 a 10 nuevos objetos o así, así que un millón de objetos era un número grande.

    (BK = BitKeeper)

    Estos días, el kernel no es el más grande proyecto git, e incluso el kernel tiene acerca de 220k revisiones (mucho más grande que el BK árbol nunca fue) y estamos cerca de dos millones de objetos.

    En ese momento, de siete dígitos hexadecimales todavía es único para un montón de ellos, pero cuando estamos hablando de dos órdenes de magnitud de diferencia entre el número de objetos y el hash de tamaño, no se ser colisiones en truncada valores de hash.

    Ya no es ni siquiera cerca de a poco realista, esto sucede todo el tiempo.

    Debemos aumentar el valor predeterminado abbrev que era demasiado pequeño, y agregar una forma para que las personas a establecer sus propios predeterminado por proyecto en el git config archivo.

    core.abbrev
    

    Establecer la longitud de los nombres de objeto que se abreviado.

    Si no se especifica, muchos de los comandos de abreviar a 7 hexdigits, que puede no ser suficiente para abreviado los nombres de objeto para una estancia única de tiempo lo suficientemente largo.

    medio ambiente.c:

    int minimum_abbrev = 4, default_abbrev = 7;
    

    Nota: Como comenta más abajo por marco.m, core.abbrevLenght fue rebautizado en core.abbrev en ese mismo Git 1.7.4.4 en cometer a71f09f

    Cambiar el nombre de core.abbrevlength de vuelta a core.abbrev

    Corresponde a --abbrev=$n opción de línea de comandos, después de todo.


    Más recientemente, Linus añadido en cometer e6c587c (para Git 2.11, Q4 2016):

    (como se mencionó en Matthieu Moy‘s respuesta)

    Bastante en los primeros días de alguna manera nos decidió abreviar los nombres de objeto a 7 hexdigits, pero como proyectos de crecer, cada vez es más y más probabilidades de ver un corto nombres de objeto hecho en los días anteriores, y se registran en el registro de mensajes ya no es único.

    Actualmente el kernel de Linux a las necesidades del proyecto 11 a 12 hexdigits, mientras Git sí mismo las necesidades de 10 hexdigits para identificar los objetos que tienen, mientras que muchos de los proyectos más pequeños todavía pueden estar bien con el original de 7 hexdigit predeterminado. Una talla no sirve para todos los proyectos.

    Introducir un mecanismo, donde se estima el número de objetos en el repositorio en la primera solicitud para abreviar el nombre de un objeto con la configuración predeterminada y llegar a una cuerdo predeterminado para el repositorio. Basada en la expectativa de que nos veríamos en colisión en un repositorio con 2^(2N) objetos al utilizar nombres de objeto acortado a los primeros N bits, el uso de suficiente número de hexdigits para cubrir el número de objetos en el repositorio.

    Cada hexdigit (4 bits) para agregar el nombre abreviado nos permite tener cuatro veces (2 bits) como muchos objetos en el repositorio.

    Ver cometer e6c587c (01 Oct 2016) por Linus Torvalds (torvalds).

    Ver cometer 7b5b772, cometer 65acfea (01 Oct 2016) por Junio C Hamano (gitster).

    (Fusionada con Junio C Hamano — gitster en cometer bb188d0, 03 de Octubre de 2016)

    Que la nueva propiedad (adivinando un reasonnable predeterminado para SHA1 abbrev valor) tiene un efecto directo en la manera Git calcular su propio número de versión para el lanzamiento.

    • Esta respuesta proporciona una manera de comprobar lo que el más largo «acortado» hash en un único repositorio es: stackoverflow.com/a/32406103/1858225
    • Tenga en cuenta que core.abbrevLength se ha cambiado el nombre a core.abbrev.
    • Gracias. He modificado la respuesta en consecuencia. Y han vinculado a la Git commit que los registros que se nombre nuevo para core.abbrev.
    • Sólo voy a agregar a esto que puede ejecutar git rev-parse --short=10 --verify HEAD para generar 10 caracteres. ESTÁBAMOS usando git log -1 --format=%h, pero que sólo se genera 7 caracteres y nos dieron una colisión.
    • Gracias por la explicación, el docs (git-scm.com/docs/git-rev-parse) están obsoletos.
    • qué quiere decir que el enlace ya no es válido? O su contenido no se corresponde a la fecha?
    • el contenido no está actualizado. He enviado un parche.
    • OK. Yo no lo veo aún en spinics.net/lists/git

  3. 27

    Esto se conoce como el problema del cumpleaños.

    Para las probabilidades menos de 1/2 de la probabilidad de una colisión puede ser aproximada como

    p ~= (n2)/(2m)

    Donde n es el número de elementos y m es el número de posibilidades para cada elemento.

    El número de posibilidades para una cadena hexadecimal es 16c donde c es el número de caracteres.

    Así, por 8 caracteres y 30K comete

    30K ~= 215

    p ~= (n2)/(2m) ~= ((215)2)/(2*168) = 230/233 = ⅛

    Aumentando a 12 caracteres

    p ~= (n2)/(2m) ~= ((215)2)/(2*1612) = 230/249 = 2-19

    • Exactamente la pregunta que me estaba tratando de resolver, gracias! La probabilidad de la tabla vinculada en @Messa la respuesta también es útil.
    • excelente, no necesitamos nada más, pero más como este, explicar no sólo lo que es, sino también cómo se van a…
  4. 11

    Esta pregunta ha sido respondida, pero para cualquier persona en busca de las matemáticas que hay detrás – se llama problema del Cumpleaños (Wikipedia).

    Es acerca de la probabilidad de tener 2 (o más) personas de un grupo de N personas han cumpleaños el mismo día en el año. Que es analógico a probabily de 2 (o más) en git desde el repositorio de tener N se compromete en total tiene el mismo hash prefijo de longitud X.

    Vistazo a la La probabilidad de la tabla. Por ejemplo para los hash cadena hexadecimal de longitud 8 la probabilidad de tener un choque alcanza el 1% cuando el repositorio tiene 9300 elementos (git). 110 000 compromete la probabilidad es del 75 %. Pero si usted tiene hash cadena hexadecimal de longitud 12 la probabilidad de colisión en 100 000 comete está por debajo del 0,1 %.

  5. 2

    Git versión 2.11 (o tal vez 2.12?) contendrá una característica que se adapta el número de caracteres utilizados en corto identificadores (por ejemplo,git log --oneline) para el tamaño del proyecto. Una vez que el uso de dicha versión de Git, la respuesta a tu pregunta puede ser «escoger cualquier longitud Git le da con git log --oneline, es lo suficientemente seguro».

    Para obtener más detalles, consulte Cambiar el valor predeterminado para «core.abbrev»? discusión en Git Rev Noticias de la edición 20 y cometer bb188d00f7.

Dejar respuesta

Please enter your comment!
Please enter your name here