Git 内部原理之 Git 对象哈希

来源:彭金金 , jingsam.github.io/2018/06/10/git-hash.html

在上一篇文章中,将了数据对象、树对象和提交对象三种Git对象,每种对象会计算出一个hash值。那么,Git是如何计算出Git对象的hash值?本文的内容就是来解答这个问题。

Git对象的hash方法

Git中的数据对象、树对象和提交对象的hash方法原理是一样的,可以描述为:

header = "<type> " + content.length + "\0" hash = sha1(header + content)

上面公式表示,Git在计算对象hash时,首先会在对象头部添加一个header。这个header由3部分组成:第一部分表示对象的类型,可以取值blob、tree、commit以分别表示数据对象、树对象、提交对象;第二部分是数据的字节长度;第三部分是一个空字节,用来将header和content分隔开。将header添加到content头部之后,使用sha1算法计算出一个40位的hash值。

在手动计算Git对象的hash时,有两点需要注意:

  1. header中第二部分关于数据长度的计算,一定是字节的长度而不是字符串的长度;
  2. header + content的操作并不是字符串级别的拼接,而是二进制级别的拼接。

各种Git对象的hash方法相同,不同的在于:

  1. 头部类型不同,数据对象是blob,树对象是tree,提交对象是commit;
  2. 数据内容不同,数据对象的内容可以是任意内容,而树对象和提交对象的内容有固定的格式。

接下来分别讲数据对象、树对象和提交对象的具体的hash方法。

数据对象

数据对象的格式如下:

blob <content length><NULL><content>

从上一篇文章中我们知道,使用git hash-object可以计算出一个40位的hash值,例如:

$ echo -n "what is up, doc?" | git hash-object --stdin bd9dbf5aae1a3862dd1526723246b20206e5fc37

注意,上面在echo后面使用了-n选项,用来阻止自动在字符串末尾添加换行符,否则会导致实际传给git hash-object是what is up, doc?\n,而不是我们直观认为的what is up, doc?。

为验证前面提到的Git对象hash方法,我们使用openssl sha1来手动计算what is up, doc?的hash值:

$ echo -n "blob 16\0what is up, doc?" | openssl sha1 bd9dbf5aae1a3862dd1526723246b20206e5fc37

可以发现,手动计算出的hash值与git hash-object计算出来的一模一样。

在Git对象hash方法的注意事项中,提到header中第二部分关于数据长度的计算,一定是字节的长度而不是字符串的长度。由于what is up, doc?只有英文字符,在UTF8中恰好字符的长度和字节的长度都等于16,很容易将这个长度误解为字符的长度。假设我们以中文来试验:

$ echo -n "中文" | git hash-object --stdin efbb13322ba66f682e179ebff5eeb1bd6ef83972 $ echo -n "blob 2\0中文" | openssl sha1 d1dc2c3eed26b05289bddb857713b60b8c23ed29

我们可以看到,git hash-object和openssl sha1计算出来的hash值根本不一样。这是因为中文两个字符作为UTF格式存储后的字符长度不是2,具体是多少呢?可以使用wc来计算:

$ echo -n "中文" | wc -c 6

中文字符串的字节长度是6,重新手动计算发现得出的hash值就能对应上了:

$ echo -n "blob 6\0中文" | openssl sha1 efbb13322ba66f682e179ebff5eeb1bd6ef83972

树对象

树对象的内容格式如下:

tree <content length><NUL><file mode> <filename><NUL><item sha>...

需要注意的是,<item sha>部分是二进制形式的sha1码,而不是十六进制形式的sha1码。

我们从上一篇文章摘出一个树对象做实验,其内容如下:

https://jingsam.github.io/2018/06/10/1

$ git cat-file -p d8329fc1cc938780ffdd9f94e0d364e0ea74f579 100644 blob 83baae61804e65cc73a7201a7252750c76066a30 test.txt

我们首先使用xxd把83baae61804e65cc73a7201a7252750c76066a30转换成为二进制形式,并将结果保存为sha1.txt以方便后面做追加操作:

$ echo -n "83baae61804e65cc73a7201a7252750c76066a30" | xxd -r -p > sha1.txt

$ cat tree-items.txt

���a�Ne�s� rRu

vj0%

接下来构造content部分,并保存至文件content.txt:

$ echo -n "100644 test.txt\0" | cat - sha1.txt > content.txt $ cat content.txt 100644 test.txt���a�Ne�s� rRu vj0%

计算content的长度:

$ cat content.txt | wc -c 36

那么最终该树对象的内容为:

$ echo -n "tree 36\0" | cat - content.txt tree 36100644 test.txt���a�Ne�s� rRu vj0%

最后使用openssl sha1计算hash值,可以发现和实验的hash值是一样的:

$ echo -n "tree 36\0" | cat - content.txt | openssl sha1 d8329fc1cc938780ffdd9f94e0d364e0ea74f579

提交对象

提交对象的格式如下:

commit <content length><NUL>tree <tree sha> parent <parent sha> [parent <parent sha> if several parents from merges] author <author name> <author e-mail> <timestamp> <timezone> committer <author name> <author e-mail> <timestamp> <timezone> <commit message>

我们从上一篇文章摘出一个提交对象做实验,其内容如下:

$ echo 'first commit' | git commit-tree d8329fc1cc938780ffdd9f94e0d364e0ea74f579 db1d6f137952f2b24e3c85724ebd7528587a067a $ git cat-file -p db1d6f137952f2b24e3c85724ebd7528587a067a tree d8329fc1cc938780ffdd9f94e0d364e0ea74f579 author jingsam <jing-sam@qq.com> 1528022503 +0800 committer jingsam <jing-sam@qq.com> 1528022503 +0800 first commit

这里需要注意的是,由于echo 'first commit'没有添加-n选项,因此实际的提交信息是first commit\n。使用wc计算出提交内容的字节数:

$ echo -n "tree d8329fc1cc938780ffdd9f94e0d364e0ea74f579 author jingsam <jing-sam@qq.com> 1528022503 +0800 committer jingsam <jing-sam@qq.com> 1528022503 +0800 first commit\n" | wc -c 163

那么,这个提交对象的header就是commit 163\0,手动把头部添加到提交内容中:

commit 163\0tree d8329fc1cc938780ffdd9f94e0d364e0ea74f579 author jingsam <jing-sam@qq.com> 1528022503 +0800 committer jingsam <jing-sam@qq.com> 1528022503 +0800 first commit\n

使用openssl sha1计算这个上面内容的hash值:

$ echo -n "commit 163\0tree d8329fc1cc938780ffdd9f94e0d364e0ea74f579 author jingsam <jing-sam@qq.com> 1528022503 +0800 committer jingsam <jing-sam@qq.com> 1528022503 +0800 first commit\n" | openssl sha1 db1d6f137952f2b24e3c85724ebd7528587a067a

可以看见,与实验的hash值是一样的。

总结

这篇文章详细地分析了Git中的数据对象、树对象和提交对象的hash方法,可以发现原理是非常简单的。数据对象和提交对象打印出来的内容与存储内容组织是一模一样的,可以很直观的理解。对于树对象,其打印出来的内容和实际存储是有区别的,增加了一些实现上的难度。例如,使用二进制形式的hash值而不是直观的十六进制形式,我现在还没有从已有资料中搜到这么设计的理由,这个问题留待以后解决。

原文发布于微信公众号 - 精讲JAVA(toooooooozi)

原文发表时间:2018-07-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏landv

C语言_函数【转】

53730
来自专栏跟着阿笨一起玩NET

数据库模糊搜索时,关键字中有%号,怎么办?

本文转载:http://www.cnblogs.com/lmfeng/archive/2013/02/26/2932963.html

38520
来自专栏知识图谱

创建分布式图数据库JanusGraph对象

36830
来自专栏专注 Java 基础分享

字节码文件的内部结构之谜

如果计算机的 CPU 只有「x86」这一种,或者操作系统只有 Windows 这一类,那么或许 Java 就不会诞生。Java 诞生之初就曾宣扬过它的初衷,「一...

41090
来自专栏LIN_ZONE

PHP 反射的简单使用

20940
来自专栏老马说编程

计算机程序的思维逻辑 (7) - 如何从乱码中恢复 (下)?

乱码 上节说到乱码出现的主要原因,即在进行编码转换的时候,如果将原来的编码识别错了,并进行了转换,就会发生乱码,而且这时候无论怎么切换查看编码的方式,都是不行...

21780
来自专栏Python

浅淡python中with的用法,上下文管理器

例子一 首先来看一段代码: class Foo(object): def __init__(self): print('实例化一个对象...

228100
来自专栏spring源码深度学习

java基础thread——java5之后的多线程(浅尝辄止)

虽然我们可以理解同步代码块和同步方法的锁对象问题,但是我们并没有直接看到在哪里加上了锁,在哪里释放了锁,为了更清晰的表达如何加锁和释放锁,JDK5以后提供了一个...

10010
来自专栏猿人谷

总结---4

全局变量与全局静态变量的区别: (a)若程序由一个源文件构成时,全局变量与全局静态变量没有区别。  (b)若程序由多个源文件构成时,全局变量与全局静态变量不同:...

20670
来自专栏青玉伏案

算法与数据结构(二) 栈与队列的线性和链式表示(Swift版)

数据结构中的栈与队列还是经常使用的,栈与队列其实就是线性表的一种应用。因为线性队列分为顺序存储和链式存储,所以栈可以分为链栈和顺序栈,队列也可分为顺序队列和链队...

193100

扫码关注云+社区

领取腾讯云代金券