例如,如果您要构建一个目录结构,其中一个目录以Git存储库中的提交命名,并且希望它足够短以使您的眼睛不流血,但又足够长以使它发生碰撞的几率可以忽略不计,那么通常需要多少SHA子字符串呢?

假设我想唯一地标识这个更改:https://github.com/wycats/handlebars.js/commit/e62999f9ece7d9218b9768a908f8df9c11d7e920

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

但我觉得那太冒险了。但是假设一个代码库,在几年的时间里,可能会有3万次更改,如果我使用8个字符,碰撞的几率是多少?12 ?对于这种事情,有没有一个通常被认为是可以接受的数字?


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

一般来说,8到10个字符就足够唯一了 在一个项目中。最大的Git项目之一,Linux内核, 在40个角色中是否需要12个角色才能留下来 独一无二的。

对于短SHA, 7位数是Git的默认值,所以对于大多数项目来说都没问题。内核团队已经将他们的数量增加了几倍,因为他们有几十万个提交。因此,对于~30k次提交,8或10位数字应该完全没问题。


注意:你可以问git rev-parse——最短但唯一的SHA1。 参见“git从常规哈希中获得短哈希”

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

在我的例子中可以看到,即使我指定的长度为4,SHA1的长度也为5。


对于大型回购,从2010年开始,7已经不够了,并由Linus Torvalds自己提交dce9648 (git 1.7.4.4, 2010年10月):

默认值7来自git开发的早期,当时7个十六进制数字已经很多了(它涵盖了大约2.5亿+哈希值)。 当时我认为65000次修订已经很多了(这是我们在《BK》中将要达到的目标),而且每次修订都倾向于大约5-10个新对象,所以100万个对象是一个很大的数字。

(BK = BitKeeper)

These days, the kernel isn't even the largest git project, and even the kernel has about 220k revisions (much bigger than the BK tree ever was) and we are approaching two million objects. At that point, seven hex digits is still unique for a lot of them, but when we're talking about just two orders of magnitude difference between number of objects and the hash size, there will be collisions in truncated hash values. It's no longer even close to unrealistic - it happens all the time. We should both increase the default abbrev that was unrealistically small, and add a way for people to set their own default per-project in the git config file.

core.abbrev

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

environment.c:

int minimum_abbrev = 4, default_abbrev = 7;

注:如下马尔科的评论。米,核心。abbrevLength在core中被重命名。abbrev在同一Git 1.7.4.4提交a71f09f

重命名的核心。缩略语回到核心 它对应于——abbrev=$n命令行选项。


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

In fairly early days we somehow decided to abbreviate object names down to 7-hexdigits, but as projects grow, it is becoming more and more likely to see such a short object names made in earlier days and recorded in the log messages no longer unique. Currently the Linux kernel project needs 11 to 12 hexdigits, while Git itself needs 10 hexdigits to uniquely identify the objects they have, while many smaller projects may still be fine with the original 7-hexdigit default. One-size does not fit all projects. Introduce a mechanism, where we estimate the number of objects in the repository upon the first request to abbreviate an object name with the default setting and come up with a sane default for the repository. Based on the expectation that we would see collision in a repository with 2^(2N) objects when using object names shortened to first N bits, use sufficient number of hexdigits to cover the number of objects in the repository. Each hexdigit (4-bits) we add to the shortened name allows us to have four times (2-bits) as many objects in the repository.

参见Linus Torvalds (Torvalds)提交e6c587c(2016年10月1日)。 参见Junio C Hamano (gitster)的commit 7b5b772, commit 65acfea(2016年10月1日)。 (由Junio C Hamano—gitster—在commit bb188d0中合并,2016年10月3日)

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


这个问题已经有了答案,但是对于那些想要探究背后数学原理的人来说,这个问题被称为生日问题(维基百科)。

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

看看概率表。例如,对于长度为8的哈希十六进制字符串,当存储库只有大约9300个条目(git提交)时,发生冲突的概率达到1%。对于11万次提交,概率是75%。但是如果你有一个长度为12的哈希十六进制字符串,那么在10万次提交中发生碰撞的概率低于0.1%。


Git 2.11版(也许是2.12版?)将包含一个特性,可以根据项目的大小来调整短标识符(例如Git log——oneline)的字符数。一旦你使用了这样的Git版本,你的问题的答案可以是“选择Git给你的任何长度的Git日志——一行,它是足够安全的”。

有关详细信息,请参见更改“core.abbrev”的默认值?在Git Rev News edition 20中讨论并提交bb188d00f7。


这就是所谓的生日问题。

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

p ~= (n2)/(2m)

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

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

对于8个字符和30K提交

30k ~= 215

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

增加到12个字符

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