Git 如何如此快速地计算 SHA 哈希值？

Question

我知道 git 很快，但我最近才发现它到底有多快。

在我的一个项目中，我正在尝试计算一个巨大文件（82 MB，85 万行）的 SHA-256 哈希，计算它花了一分钟多的时间（包括哈希和其他一些小操作） ).

即使使用 SHA-1，我也花了 30 多秒，而 git 似乎只用了一两秒。

我正在使用 java 的 Security API 通过组合文件的所有行在 Scala 中计算哈希值。

val lines = Source.fromFile(filePath, "UTF-8").getLines().toList
MessageDigest.getInstance("SHA-256")
.digest(lines.mkString("\n").getBytes).map("%02x".format(_)).mkString

那么，Git 是如何做到这么快的，或者更重要的问题是，为什么我的方法这么慢？

编辑：对于那些不熟悉 scala 语法的人，lines 会将文件的所有行放在 List 和 mkString 方法中 returns 一串列表中的所有元素与给定的分隔符相结合。

Answer 1

哈希计算在编译时重定向到 cache.h 中的特定实现。底层平台可以提供优化的（例如，汇编程序或机器相关的 C 编码的）哈希例程。当然，您的 Java 实现可能也可能不提供这样的例程。

如果平台没有自己的实现，Git provides one written in C 可以在大内存块上运行，并且仍然有一些手动调整和内联 asms 架构和编译器 ifdefs.

Answer 2

重新发布我之前的评论（扩展）。

你所做的是：

读取字节
将它们转换为字符
将字符流拆分为多行
将这些行存储到列表中
再次将这些行连接成一个字符串
再取其字节数
计算那些字节的散列

步骤 2-6 似乎没有必要。我建议从初始 FileInputStream 中以块（例如 4k）读取字节并将它们提供给 MessageDigest 进行更新。那只会执行步骤 1 和 7。

InputStream is = new FileInputStream(fileName);
byte[] buffer = new byte[4096];
while (true) {
    int read = is.read(buffer);
    if (read < 0) {
        break;
    }
    md.update(buffer, 0, read);
}
is.close(); // better be done in finally

至于 sha1 性能，这是我为 time sha1sum <file> 得到的结果，其中文件为 179Mb：

real    0m0.607s
user    0m0.588s
sys 0m0.016s

Answer 3

Git 无疑更快，但 SHA-1 的 30 秒并不是那么好。

所以我运行在 java 中进行了测试：

public static void main(String[] args) throws Exception{
    long startTime = System.currentTimeMillis();

    byte[] bytes = createSha1(new File("src\main\resources\200mb_file.zip"));
    System.out.println(new String(bytes));

    long endTime = System.currentTimeMillis();
    long duration = (endTime - startTime);
    System.out.format("Duration: %dms\n", duration);
}

private static byte[] createSha1(File file) throws Exception  {
    MessageDigest digest = MessageDigest.getInstance("SHA-1");
    InputStream fis = new FileInputStream(file);
    int n = 0;
    byte[] buffer = new byte[8192];
    while (n != -1) {
        n = fis.read(buffer);
        if (n > 0) {
            digest.update(buffer, 0, n);
        }
    }
    return digest.digest();
}

输出：

Duration: 1531

我猜导致速度缓慢的原因是您将其输入列表而不是直接将其用作流。

Git 如何如此快速地计算 SHA 哈希值？

How does Git compute SHA hashes so quickly?

java

git

hash

scala

sha