256

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

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

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

但我觉得那样会有风险。但是假设一个代码库在几年内可能会有 30k 的变化，如果我使用 8 个字符，那么发生冲突的可能性有多大？12？有没有一个数字通常被认为可以接受这种事情？

4

5 回答 5

284

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

通常，八到十个字符足以在一个项目中保持唯一性。最大的 Git 项目之一，Linux 内核，开始需要 40 个字符中的 12 个来保持唯一性。

7 位数字是短 SHA 的 Git 默认值，因此对于大多数项目来说都可以。如前所述，Kernel 团队已经增加了好几次，因为他们有几十万次提交。因此，对于您的约 30k 次提交，8 或 10 位数字应该是完全可以的。

于 2013-08-08T19:54:41.357 回答
173

注意：您可以要求git rev-parse --short最短但唯一的 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 开发的早期阶段，当时七个十六进制数字很多（它涵盖了大约 250+ 百万个哈希值）。
那时我认为 65k 修订很多（这是我们即将在 BK 中实现的），每个修订往往是大约 5-10 个新对象左右，所以一百万个对象是一个很大的数字。

(BK = BitKeeper)

如今，内核甚至不是最大的 git 项目，甚至内核也有大约 220k 的修订版（比 BK 树大得多），我们正在接近 200 万个对象。
到那时，七个十六进制数字对于其中的许多人来说仍然是唯一的，但是当我们谈论对象数量和散列大小之间只有两个数量级的差异时，截断的散列值会发生冲突。
它甚至不再接近不现实——它一直在发生。

我们应该增加不切实际的小默认缩写，并添加一种方法让人们在 git config 文件中设置他们自己的每个项目的默认默认值。

core.abbrev

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

environment.c：

int minimum_abbrev = 4, default_abbrev = 7;

注意：正如marco.m 在下面评论的那样，在同一 Git 1.7.4.4 中的提交a71f09f中core.abbrevLength被重命名core.abbrev

重命名core.abbrevlength回core.abbrev

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

最近，Linus 在提交 e6c587c中添加（对于 Git 2.11，Q4 2016）：（
如Matthieu Moy的回答中所述）

在相当早的时候，我们以某种方式决定将对象名称缩写为 7 位十六进制数字，但随着项目的增长，越来越有可能看到在早期制作的如此短的对象名称并记录在日志消息中不再唯一。

目前 Linux 内核项目需要 11 到 12 个 hexdigits，而 Git 本身需要 10 个 hexdigits 来唯一标识它们拥有的对象，而许多较小的项目可能仍然可以使用原始的 7-hexdigit 的默认值。一种尺寸并不适合所有项目。

引入一种机制，我们在第一次请求时估计存储库中的对象数量，以使用默认设置缩写对象名称，并为存储库提供一个合理的默认值。基于在2^(2N)使用缩短为前 N 位的对象名称时我们会在存储库中看到与对象发生冲突的预期，使用足够数量的十六进制数字来覆盖存储库中的对象数量。
我们添加到缩短名称的每个十六进制数字（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 如何计算自己的 release 版本号有直接影响。

于 2014-01-09T08:25:01.127 回答
49

这被称为生日问题。

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

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

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

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

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

30K ~= 2 15

p ~= (n 2 )/(2m) ~= ((2 15 ) 2 )/(2*16 8 ) = 2 30 /2 33 = ⅛</p>

将其增加到 12 个字符

p ~= (n 2 )/(2m) ~= ((2 15 ) 2 )/(2*16 12 ) = 2 30 /2 49 = 2 -19

于 2017-03-02T22:36:26.957 回答
15

这个问题已经得到解答，但对于任何寻找背后数学的人来说——它被称为生日问题（维基百科）。

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

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

于 2016-08-20T20:13:24.533 回答
2

Git 版本 2.11（或者可能是 2.12？）将包含一个功能，该功能使短标识符（例如git log --oneline）中使用的字符数适应项目的大小。一旦你使用了这样的 Git 版本，你的问题的答案可能是“选择 Git 给你的任何长度git log --oneline，它足够安全”。

有关更多详细信息，请参阅更改“core.abbrev”的默认值？Git Rev News 第 20 版中的讨论并提交bb188d00f7。

于 2016-10-24T14:06:57.723 回答