Git 哈希重复

Question

Git 允许使用以下命令检索提交的哈希值：

git rev-parse HEAD

这给出33b316c 或

git rev-parse --short HEAD

这让33b316cbeeab3d69e79b9fb659414af4e7829a32 我知道实践中长哈希永远不会发生冲突。

在实践中，短哈希值的使用更为频繁。我想知道短的碰撞的概率是多少？git 是否采取任何措施来克服可能的冲突（例如使用时git checkout）？

Answer 1

我在我的书中给出了一个公式\xe2\x80\x94see pp. 78-79\xe2\x80\x94 但是如果你正在寻找一个简单的公式，那么某些哈希冲突的概率达到大约 50% 的点n 位哈希是指对大约 2 ^{n/2 个}密钥进行哈希处理。SHA-1 哈希本身为 160 位，表示为 40 个十六进制数字，每个数字代表 160 位中的 4 个。^{将其截断为 7 个十六进制数字剩下 28 位，因此在大约 2 ×14}个键或 16384 个对象处，您将达到 50% 的碰撞机会。如果将对象限制为仅提交，那么提交数量相当不错，但 Git 将所有对象\xe2\x80\x94 提交、树、带注释的标记对象和 blob\xe2\x80\x94 放在单个散列中 -索引键值存储。

\n\n

任何给定密钥对的哈希冲突的概率仅为 2 ⁿ中的 1 ，即 2 ²⁸中的 1或 2.68 亿中的 1。随着密钥数量的增加，它增长如此之快到 50% 的原因被称为生日悖论或生日问题。50%当然太可怕了；对于 28 位，如果我们希望总体概率低于 0.1%，我们应该将对象数量保持在约 1230 以下。通过使用 32 位（8 个字符缩写），我们将其加倍到约 2460，但这仍然是物体不是很多。

\n\n

当您的商店中有 16k 个对象时，您可能应该使用至少 10 个十六进制数字，给出 2 ^{40 个}可能的哈希值和大约 0.99987794 的 p-bar 值...（大约 0.019% 的冲突几率）。九个十六进制数字仅给出 2 ^{36 个}哈希值，产生 0.99804890 的 p-bar...或 0.19% 的碰撞几率，我认为这太高了。

\n\n

如果您可以将模糊匹配代码限制为仅 commits\xe2\x80\x94 或仅commit-ish，这在 Git 中意味着提交或带注释的标签\xe2\x80\x94 ，则内置默认值工作得很好。（事实上​​，Git 在很多情况下都会这样做。）但是，至少在我看来，Git 用于计算“正确”缩写长度的内部代码实在是太粗心了，太“松散”了，因为它在结果哈希可用于识别任何内容的上下文中使用 50% 碰撞概率平方根技巧。

\n\n

（正如评论中所指出的， Git内部总是使用完整的哈希值。仅在非 Git / Git 界面，例如，git log <hash>或git show <hash>面向用户的命令，您可以输入缩写的哈希值，或要求缩写的哈希值。输出哈希值。这里 Git 将默认使用 50% 碰撞概率数字来计算要显示的字符数，从数据库中对象数量的估计开始。如果您提供哈希值，您可以选择如何显示提供多少。如果您要求 Git 提供它，您仍然可以使用 来选择多少。请注意，绝对最小值为 4：不会视为哈希 ID，但会视为哈希 ID 的缩写。还有一个非常古老的默认值，即 7 个​​字符，来自 Git 1.7 左右的时代。）--abbrev=numbergit log abcabcgit log abcdabcd

\n

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

例如，这是git checkout <shortHash>在 CLI 中输入的，但我不确定它在脚本上下文中的行为方式。要么出现退出代码 1 错误，要么自动采用其中一位候选者，我必须对此进行检查。