Git哈希值重复问题

Question

Git允许使用命令检索提交的哈希值，例如：

git rev-parse HEAD

这将提供33b316c

git rev-parse --short HEAD

其中给出的33b316cbeeab3d69e79b9fb659414af4e7829a32是一个长哈希值，实际上这种哈希值很难发生碰撞。

在实践中，短哈希值更常用。我想知道短哈希值发生碰撞的概率是多少？Git在执行诸如git checkout之类的操作时是否采取了任何措施来避免可能的碰撞？

- GA1

---

第一位是相当基本的数学，只需 [字母表大小]^[字符数]。因此 16^长度。任何措施可能都需要从源代码中挖掘出来。 - jhpratt

可能是 Git（Hub）如何处理短SHA可能的冲突？ 的重复。 - blues

这只是一点数学问题。Git 内部仅使用长哈希，短哈希的冲突并不重要。请参阅 https://dev59.com/x2w05IYBdhLWcg3wnjLC - blues

Answer 1

我在我的书中提供了一个公式——见第78-79页，但如果您正在寻找一个简单的公式，当您大约散列2^n/2个密钥时，某些哈希冲突的概率达到约50%。SHA-1哈希本身是160位，表示为40个十六进制数字，每个数字表示160位中的4位。将其截断为7个十六进制数字会留下28位，因此您将在大约2¹⁴个密钥或16384个对象处达到50％碰撞几率。如果您将对象限制为仅提交，则这是相当可观的提交数，但Git将所有对象（提交、树、注释标记对象和blob）放入单个哈希索引的键值存储中。 < p >任何给定键对的哈希碰撞概率只有2 ⁿ 中的1，即2 ²⁸ 或268百万分之一。随着键的数量增加，它迅速增加到50％的原因被称为生日悖论或birthday problem。当然，50％太可怕了；使用28位，如果我们希望总体概率低于0.1％，则应将对象数量保持在约1230以下。通过转向32位（8个字符缩写），我们将其加倍到约2460，但这仍然不是很多对象。

当您的存储中有16k个对象时，您可能应该至少使用10个十六进制数字，提供2 ⁴⁰ 个可能的哈希值和大约.99987794的p-bar值...（约占碰撞机会的.019％）。九个十六进制数字仅提供2 ³⁶ 个哈希值，产生.99804890的p-bar或0.19％的碰撞几率，我认为这太高了。

如果你能将含糊匹配代码限制在提交或者提交点上，或者只使用 Git 中的提交或已注释标签（commit-ish），内置默认值就能很好地工作。（Git 在许多情况下实际上会这样做。）但是，至少在我看来，Git 用于计算“正确”缩写长度的内部代码过于随意，太松散了，因为它在可能用于标识任何对象的上下文中使用了 50% 碰撞概率平方根技巧。

（正如评论中所指出的，Git 内部始终使用完整哈希值。只有在非 Git / Git 接口，例如 git log <hash> 或 git show <hash> 用户界面命令时，才可以键入缩写哈希值或请求缩写输出哈希值。在这里，Git 将默认使用 50% 碰撞概率数来计算要显示多少个字符，从数据库中对象数量的估计开始。如果您正在提供哈希值，则由您决定提供多少。如果您要求 Git 提供它，则仍然可以选择使用 --abbrev=number 来决定显示多少位。请注意，最小值为 4： git log abc 不会将 abc 视为哈希 ID，但是 git log abcd 将把 abcd 视为哈希 ID 的缩写。默认使用非常旧的 7 个字符，来自 Git 1.7 左右的版本。）

- torek

Answer 2

在提交次数增加的情况下，仓库短哈希列表中出现重复的几率非常高。

然而，这并不会带来太多问题，因为这些哈希值不需要是唯一的，它们只是一个方便的功能，在某些命令中提供了一种替代的指定提交方式。

当您选择向命令提供短哈希时，如果在您的仓库中解析不了到唯一的提交，则Git会提示您一个候选列表，您可以选择所需的提交。

示例输出：

$ git checkout 2334
error: short SHA1 2334 is ambiguous
hint: The candidates are:
hint:   233475fec8 commit 2018-02-14 - Merge pull request #175 in someRepo from someBranch to someOtherBranch
hint:   2334790f05 commit 2018-06-14 - Merge pull request #917 in someRepo from someBranch to yetAnotherBranch
hint:   233415cfa2 tree
hint:   233438d772 tree
hint:   23348a014a tree
error: pathspec '2334' did not match any file(s) known to git

这是关于在CLI中输入git checkout <shortHash>命令的例子，但我不确定它在脚本上下文中的行为如何。它要么会返回错误代码1，要么会自动选择其中一个备选项，我需要检查一下。

- Romain Valeri

---

git checkout <hash>将哈希视为tree-ish，因此您应该计算非Blob对象的数量，以近似于任何给定哈希子集和对象数的碰撞概率。有多少个树取决于许多因素：一组繁茂的路径名会产生更多的提交每个树，但是如果提交中的变更很少，并且限制在一个特定的子树中，许多这些树将在许多提交之间共享... - torek