Git哈希重复项

Question

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

git rev-parse HEAD

给出 33b316c 或

git rev-parse --short HEAD

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

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

Answer 1

我在 book 中给出了一个公式— 参见第 78-79 页 — 但如果您正在寻找一个简单的，一些 散列冲突的概率在 n 位散列中达到大约 50% 的点是当您进行散列时大约 2^n/2 键。 SHA-1 散列本身是 160 位，表示为 40 个十六进制数字，每个代表 160 位中的 4 个。将其截断为 7 个十六进制数字会留下 28 位，因此您将在大约 2¹⁴ 键或 16384 个对象处达到 50% 的碰撞几率。如果您将对象限制为仅提交，那是相当可观的提交数量，但 Git 将所有对象(提交、树、带注释的标记对象和 blob)放在一个散列索引的键值存储中。

任何给定键的散列值发生冲突的概率仅为 2ⁿ 中的 1，即 2²⁸ 中的 1 或2.68 亿中的 1。随着 key 数量的增加，它迅速增加到 50% 的原因被称为生日悖论或 birthday problem。 . 50%当然太可怕了；使用 28 位，如果我们希望整体概率低于 0.1%，我们应该将对象的数量保持在大约 1230 以下。通过使用 32 位(8 个字符的缩写)，我们将其加倍到大约 2460，但这仍然不是很多对象。

当你的存储中有 16k 个对象时，你可能应该使用至少 10 个十六进制数字，给出 2⁴⁰ 可能的哈希值和大约 .99987794 的 p-bar 值... (大约 0.019% 的碰撞几率)。九个十六进制数字仅给出 2³⁶ 哈希值，产生 .99804890 的 p-bar...或 0.19% 的碰撞几率，我认为这太高了。

如果您可以将模糊匹配代码限制为仅提交——或仅提交-ish，这在 Git 中意味着提交或带注释的标签——内置默认值有效很不错。 (Git 实际上会在很多情况下这样做。)但是 Git 用于计算“正确”缩写长度的内部代码，至少在我看来，也太无忧无虑了 "loosey-goosey" ，因为它在生成的哈希可能用于识别任何对象的上下文中使用 50% 碰撞概率平方根技巧。

(如评论中所述，内部 Git 始终使用完整的哈希值。它仅在非 Git/Git 界面，例如 git log <hash> 或 git show <hash> 面向用户的命令，你可以输入一个缩写的哈希值，或者要求一个缩写的输出哈希值。这里 Git 将默认使用 50% 的碰撞概率数字来计算要显示的字符数，从数据库中对象的估计数量开始. 如果你提供散列，你选择提供多少。如果你要求 Git 提供它，你仍然可以选择多少，用 --abbrev=<em>number</em> 。注意有一个绝对值最小值 4:git log abc 不会将 abc 视为哈希 ID，但 git log abcd 会将 abcd 视为缩写的哈希 ID。还有一个非常古老的默认值，即 7 个​​字符，来自 Git 1.7-美好的日子。)