通常*认为有多少git sha是唯一标识给定代码库中的更改所必需的？

Question

如果您要构建一个目录结构,其中一个目录以Git存储库中的提交命名,并且您希望它足够短以使您的眼睛不流血,但足够长以使其碰撞的可能性可以忽略不计,通常需要多少SHA子串？

假设我想要唯一地识别这种变化:https://github.com/wycats/handlebars.js/commit/e62999f9ece7d9218b9768a908f8df9c11d7e920

我可以使用前四个字符:https: //github.com/wycats/handlebars.js/commit/e629

但我觉得这样会有风险.但是,假设一个代码库,在几年内,可能会有30k的变化,如果我使用8个字符,碰撞的几率是多少？12？是否有一些通常被认为可接受的数字？

Answer 1

这个问题实际上在Pro Git书的第7章中得到了回答:

通常,八到十个字符足以在项目中独一无二.最大的Git项目之一Linux内核在可能的40个字符中开始需要12个字符才能保持独特.

7位数是短SHA的Git默认值,因此对于大多数项目来说都没问题.如上所述,内核团队已经多次增加了他们的内容,因为它有几十万次提交.因此,对于您的~30k提交,8或10位数应该是完全正常的.

Answer 2

注意:您可以要求git rev-parse --short最短且唯一的SHA1.
请参阅" git get regular hash from regular hash "

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

正如您在我的示例中所看到的,即使我指定长度为4,SHA1的长度也为5.

对于大回购,自2010年以来7还不够,并且由Linus Torvalds本人提交dce9648(git 1.7.4.4,2010年10月):

默认值7来自git开发的相当早期,当七个十六进制数字很多时(它涵盖大约2.5亿个哈希值).
那时候我认为65k的修改很多(这是我们要用BK命中的),并且每个版本往往大约有5-10个新对象,所以一百万个对象是一个很大的数字.

(BK = BitKeeper)

这些天来,内核甚至不是最大的Git项目,甚至内核约220K版本(多比BK树曾是大),我们正在接近200万级的对象.
此时,七个十六进制数字对于它们中的许多仍然是唯一的,但是当我们谈论对象数量和散列大小之间仅有两个数量级的差异时,在截断的散列值中将存在冲突.
它甚至不再接近不切实际 - 它总是发生.

我们都应该增加不切实际的小默认缩写,并为人们添加一种在git配置文件中设置自己的默认每个项目的方法.

core.abbrev

设置长度对象名称缩写为.
如果未指定,则许多命令缩写为7个hexdigits,这可能不足以使缩写的对象名称在足够长的时间内保持唯一.

environment.c:

int minimum_abbrev = 4, default_abbrev = 7;

注意:评论下面通过marco.m,core.abbrevLenght更名为中core.abbrev在相同的Git 1.7.4.4在提交a71f09f

重命名core.abbrevlength回来core.abbrev

--abbrev=$n毕竟它对应于命令行选项.

最近,Linus在提交e6c587c中添加了(对于Git 2.11,2016年第4季度):(
如Matthieu Moy的回答中所述)

在相当早的时候,我们不知何故决定将对象名称缩减为7-hexdigits,但随着项目的增长,越来越有可能看到在早些时候制作的这种短对象名称并记录在日志消息中不再是唯一的.

目前Linux内核项目需要11到12个十六进制数,而Git本身需要10个十六进制数来唯一地识别它们拥有的对象,而许多较小的项目可能仍然可以使用原始的7-hexdigit默认值.单一尺寸不适合所有项目.

引入一种机制,在第一次请求使用默认设置缩写对象名称时,我们估计存储库中的对象数量,并为存储库提供一个合理的默认值.基于期望2^(2N)当使用缩短为前N位的对象名称时,我们将在存储库中看到与对象的冲突,使用足够数量的hexdigits来覆盖存储库中的对象数.
我们添加到缩短名称的每个hexdigit(4位)允许我们在存储库中有四倍(2位)的对象.

请参阅Linus Torvalds()提交的e6c587c(2016年10月1日). 请参阅Junio C Hamano()提交7b5b772,提交65acfea(2016年10月1日).^{(由Junio C Hamano合并- -在提交bb188d0,2016年10月3日)}torvalds
gitster
gitster

这个新属性(猜测SHA1缩写值的合理默认值)直接影响Git如何计算自己的版本号以便发布.

Answer 3

这被称为生日问题.

对于小于1/2的概率,碰撞的概率可以近似为

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

其中n是项目数,m是每个项目的可能性数.

十六进制字符串的可能性数量是16 ^c,其中c是字符数.

所以对于8个字符和30K提交

30K~ = 2 ¹⁵

P〜=(N ²)/(2M)〜=((2 ¹⁵)²)/(2*16 ⁸)= 2 ³⁰ /2 ³³ =⅛

将其增加到12个字符

P〜=(N ²)/(2M)〜=((2 ¹⁵)²)/(2*16 ¹²)= 2 ³⁰ /2 ⁴⁹ = 2 ^-19

Answer 4

这个问题已得到解答,但对于那些寻找数学背后的人来说 - 它被称为生日问题(维基百科).

这是关于在一年中同一天有2个(或更多)N群人的生日的概率.这类似于来自存储库的2个(或更多)git提交的概率,其总共具有N个提交,具有相同的长度为X的哈希前缀.

查看概率表.例如,对于长度为8的散列十六进制字符串,当存储库只有大约9300个项目(git提交)时,发生冲突的概率达到1%.对于110 000次提交,概率为75%.但是如果你有长度为12的哈希十六进制字符串,则100 000次提交中的冲突概率低于0.1%.