Какую часть git sha * обычно * считают необходимой для однозначной идентификации изменений в заданной кодовой базе?

Если вы собираетесь построить, скажем, структуру каталогов, в которой каталог называется коммитом в репозитории Git, и вы хотите, чтобы он был достаточно коротким, чтобы ваши глаза не кровоточили, но достаточно длинным, чтобы вероятность его столкновения было бы незначительным, сколько подстроки SHA обычно требуется?

Допустим, я хочу уникально идентифицировать это изменение: https://github.com/wycats/handlebars.js/commit/e62999f9ece7d9218b9768a908f8df9c11d7e920

Я могу использовать только первые четыре символа: https://github.com/wycats/handlebars.js/commit/e629

Но я чувствую, что это было бы рискованно. Но если исходить из кодовой базы, которая за пару лет может иметь, скажем, 30 тыс. Изменений, каковы шансы столкновения, если я использую 8 символов? 12? Есть ли номер, который обычно считается приемлемым для такого рода вещей?

На этот вопрос фактически дан ответ в главе 7 книги Pro Git :

Как правило, от восьми до десяти символов более чем достаточно, чтобы быть уникальными в рамках проекта. Один из крупнейших проектов Git, ядро ​​Linux, начинает нуждаться в 12 символах из 40 возможных, чтобы оставаться уникальным.

7 цифр - это Git по умолчанию для короткого SHA, так что это подходит для большинства проектов. Как уже упоминалось, команда Kernel увеличила свою команду в несколько раз, потому что имеет несколько сотен тысяч коммитов. Так что для ваших ~ 30k коммитов 8 или 10 цифр должно быть идеально.

Примечание: вы можете запросить git rev-parse --shortсамый короткий и в то же время уникальный SHA1.
Смотрите " git получи короткий хеш из обычного хэша "

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

Как вы можете видеть в моем примере, SHA1 имеет длину 5, даже если я указал длину 4.

Для больших репозиториев 7 недостаточно с 2010 года, а коммит dce9648 сам Линус Торвальдс (git 1.7.4.4, октябрь 2010):

Значение по умолчанию 7 приходит с довольно раннего периода разработки git, когда семь шестнадцатеричных цифр было много (оно охватывает более 250 миллионов значений хеша).
В то время я думал, что 65 000 ревизий - это много (это было то, что мы собирались выпустить в БК), и каждая ревизия имеет тенденцию иметь около 5-10 новых объектов или около того, поэтому миллион объектов был большим числом.

(BK = BitKeeper)

В настоящее время ядро ​​даже не является крупнейшим git-проектом, и даже ядро ​​имеет около 220 тыс. Ревизий ( намного больше, чем когда-либо было дерево BK), и мы приближаемся к двум миллионам объектов.
На этом этапе семь шестнадцатеричных цифр по-прежнему уникальны для многих из них, но когда мы говорим только о разнице в два порядка между количеством объектов и размером хэша, в усеченных значениях хэша будут возникать коллизии.
Это уже даже близко к нереальному - это происходит постоянно.

Мы должны как увеличить аббревиатуру по умолчанию, которая была нереально малой, так и добавить способ, позволяющий людям устанавливать свой собственный проект по умолчанию в файле конфигурации git .

core.abbrev

Установите длину объекта, имена которого сокращены до.
Если не указано, многие команды сокращаются до 7 шестнадцатеричных чисел, что может быть недостаточно для того, чтобы сокращенные имена объектов оставались уникальными в течение достаточно длительного времени.

environment.c:

int minimum_abbrev = 4, default_abbrev = 7;

Примечание: Как прокомментировал ниже по marco.m , core.abbrevLengthбыл переименован в core.abbrevв том же Git 1.7.4.4 в фиксации a71f09f

Переименовать core.abbrevlengthобратно вcore.abbrev

В --abbrev=$nконце концов, это соответствует опции командной строки.

Совсем недавно, Линус добавил совершить e6c587c (для Git 2.11, Q4 2016):
(как указано в Матьё Moy «s ответ )

В довольно ранние времена мы почему-то решили сократить имена объектов до 7-шестнадцатеричных чисел, но по мере роста проектов становится все более вероятным, что такие короткие имена объектов, сделанные в более ранние дни и записанные в сообщениях журнала, перестают быть уникальными.

В настоящее время проекту ядра Linux требуется от 11 до 12 шестнадцатеричных чисел, в то время как самому Git требуются 10 шестнадцатеричных чисел для уникальной идентификации объектов, которые у них есть, в то время как многие небольшие проекты могут по-прежнему работать с исходным 7-шестнадцатеричным значением по умолчанию. Один размер не подходит для всех проектов.

Внедрите механизм, где мы оцениваем количество объектов в хранилище по первому запросу, чтобы сократить имя объекта с настройкой по умолчанию и придумать нормальное значение по умолчанию для хранилища. Исходя из того, что мы увидим столкновение в хранилище с 2^(2N)объектами при использовании имен объектов, укороченных до первых N битов, используйте достаточное количество шестнадцатеричных чисел, чтобы покрыть количество объектов в хранилище.
Каждый шестнадцатеричный код (4 бита), который мы добавляем к сокращенному имени, позволяет нам иметь в четыре раза (2 бита) столько объектов в хранилище.

Смотрите коммит e6c587c (01.10.2016) Линуса Торвальдса ( torvalds) .
Смотрите коммит 7b5b772 , коммит 65acfea (01 октября 2016 г.) от Junio ​​C Hamano ( gitster) .
^{(Слиты Junio C Hamano - gitster- в фиксации bb188d0 , 3 октября 2016)}

Это новое свойство (предполагающее разумное значение по умолчанию для значения аббревиатуры SHA1) напрямую влияет на то, как Git вычисляет свой собственный номер версии для выпуска .

Это известно как проблема дня рождения.

Для вероятностей меньше 1/2 вероятность столкновения может быть аппроксимирована как

p ~ = (n ² ) / (2 м)

Где n - количество предметов, а m - количество возможностей для каждого предмета.

Количество возможностей для шестнадцатеричной строки равно 16 ^c, где c - количество символов.

Так что для 8 символов и 30K коммитов

30K ~ = 2 ¹⁵

р ~ = (п ² ) / (2m) ~ = ((2 ¹⁵ ) ² ) / (2 * 16 ⁸ ) = 2 ³⁰ /2 ³³ = ⅛

Увеличение до 12 символов

р ~ = (п ² ) / (2m) ~ = ((2 ¹⁵ ) ² ) / (2 * 16 ¹² ) = 2 ³⁰ /2 ⁴⁹ = 2 ^-19

На этот вопрос ответили, но для тех, кто ищет математику позади - это называется проблема дня рождения ( Википедия ).

Речь идет о вероятности того, что 2 (или более) человека из группы из N человек будут иметь день рождения в один и тот же день в году. Что аналогично вероятности 2 (или более) git коммитов из репозитория с N коммитами в общей сложности с одинаковым хеш-префиксом длины X.

Посмотрите на таблицу вероятностей . Например, для шестнадцатеричной строки хеша длиной 8 вероятность столкновения достигает 1%, когда в хранилище всего около 9300 элементов (git commit). Для 110 000 коммитов вероятность составляет 75%. Но если у вас есть хеш-строка длиной 12, вероятность столкновения в 100 000 коммитов будет ниже 0,1%.

Git версии 2.11 (или, возможно, 2.12?) Будет содержать функцию, которая адаптирует количество символов, используемых в коротких идентификаторах (например git log --oneline), к размеру проекта. После того, как вы используете такую ​​версию Git, ответом на ваш вопрос может быть «выбрать любую длину, которую Git дает вам git log --oneline, это достаточно безопасно».

Для получения дополнительной информации см. Изменение по умолчанию для «core.abbrev»? обсудите в Git Rev News издание 20 и передайте bb188d00f7 .