京公网安备11010502063487号git 的 hash 到底是怎么算出来的?这篇不靠记忆,直接用 hashlib 和 shasum 手算 blob、tree、commit 的 hash,逐个对照 git 的真实输出,再看改一个字节、换文件名、换对象类型分别会怎样。
内容 'hello world\n' 手算 3b18e512dba79e4c8300dd08aeb37f8e728b8dad git 3b18e512dba79e4c8300dd08aeb37f8e728b8dad 一致=True
内容 'hello world' 手算 95d09f2b10159347eece71399a7e2e907ea3df4f git 95d09f2b10159347eece71399a7e2e907ea3df4f 一致=True
内容 '' 手算 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 git e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 一致=True
对比:不加头,直接 SHA-1(内容)
22596363b3de40b06f981fb85d82312e8c0ed511 (git 里没有任何对象是这个 hash)
用 shell 工具复现(不依赖 git):
$ printf 'blob 12\0hello world\n' | shasum -a 1
3b18e512dba79e4c8300dd08aeb37f8e728b8dad -
两个众所周知的常数:
$ git hash-object -t blob /dev/null
e69de29bb2d1d6434b8b29ae775ad8c2e48c5391
$ git hash-object -t tree /dev/null
4b825dc642cb6eb9a060e54bf8d69288fbee4904git 对象的 hash 是对“类型 空格 长度 NUL 内容”整体做 SHA-1。blob 的内容是文件字节,tree 的内容是拼接好的条目,commit 的内容是那段文本。头部里的长度是内容的字节数,不含头部本身。漏掉头部直接算内容的 SHA-1,得到的值在 git 里不存在。
$ git add -A && git write-tree 0b2908bff47a97e61ba4e785c3543014a153b52e 手算 sub/ 的 tree : 45785efc36115bb31d7e861c101e58da45fbafac git: 45785efc36115bb31d7e861c101e58da45fbafac 手算根 tree : 0b2908bff47a97e61ba4e785c3543014a153b52e 手算 commit : 6ee12d6a309c603b779739cc186904e0e02618e6 git commit 的真实值: 6ee12d6a309c603b779739cc186904e0e02618e6 一致= True
tree 的内容里每个条目的 hash 是 20 字节二进制,目录模式写成 40000;commit 的内容是 tree、parent、author、committer 几行加空行加说明。先算出子对象的 hash,才能算出父对象的 hash——这就是 git 的 Merkle 结构。作者与时间戳固定后 commit 的 hash 是可复现的。
hello world\n : 3b18e512dba79e4c8300dd08aeb37f8e728b8dad hello worlD\n : 4c7ace60866af5dbdbc7a026c6102405e9aa8454 160 位里有 86 位不同(54%) $ git add -A; git ls-files -s one.txt dir/two.txt x.sh 100644 1275430f1765c63e539cb0452565563bd6aef6a6 0 dir/two.txt 100644 1275430f1765c63e539cb0452565563bd6aef6a6 0 one.txt 100755 1275430f1765c63e539cb0452565563bd6aef6a6 0 x.sh
改一个字节,约一半的位翻转;而文件名、目录位置、可执行权限都不属于 blob,所以内容相同的文件天然共用一个 blob。名字和权限由 tree 条目记录。
类型 blob → 3b18e512dba79e4c8300dd08aeb37f8e728b8dad 类型 tree → f6b9a7065e9842dca07dc67702e3215befb9e648 类型 commit → 5c0b41fcf14d33ffebf132e683c8a8394f965184 类型 tag → 9848898017f7bf39eb2f1866c8aa428d19aff367 类型只是头部的一个词,但它进了 hash,所以不能把一个 blob 冒充成 tree
同样的字节放进 blob、tree、commit、tag,头部不同,hash 不同,所以对象类型无法被混淆。
$ git version --build-options | grep -i sha SHA-1: SHA1_DC SHA-256: SHA256_BLK default-hash: sha1 生日界:随机 160 位 hash 要有约 2^80 = 1.21e+24 个对象才有 50% 概率撞车 1 亿个对象(1e8)里出现一对碰撞的概率 ≈ n²/2^161 = 3.42e-33
随机碰撞的概率在实际仓库规模下可以忽略;真正的风险是人为构造的碰撞,因此 git 使用检测碰撞特征的 SHA1_DC 实现,并提供 SHA-256 仓库(见后面的文章)。