什么是较便宜的哈希算法？

Question

我并不了解哈希算法。

在Java中，我需要实时计算传入文件的哈希值，然后将该文件转发到远程系统（类似于S3），该系统要求MD2 / MD5 / SHA-X格式的文件哈希值。这个哈希值不是为了安全考虑而计算的，而只是为了一致性检查。

我能够使用Java标准库的DigestInputStream实时计算这个哈希值，但是想知道哪种算法最好，以避免使用DigestInputStream时出现性能问题？

我的一位前同事进行了测试，并告诉我们实时计算哈希值可能比在unix命令行或文件上计算要耗费更多的时间。

---

关于过早优化的编辑： 我在一家公司工作，旨在帮助其他公司数字化其文档。 这意味着我们有一个批处理程序，处理来自其他公司的文档传输。我们未来的目标是每天处理数百万份文件，实际上，这个批处理程序的执行时间对我们的业务非常敏感。

如果每天处理100万份文件，哈希值优化可以减少3小时的执行时间，这个优化可节省10毫秒。

- Sebastien Lorber

---

你应该能够在一台不错的机器上使用单个核心哈希超过100MB/s，所以除非你正在使用千兆互联网，否则它不应该成为瓶颈。 - CodesInChaos

过早优化是万恶之源。我认为您应该选择一个在技术上足够满足您想要实现的目标的哈希函数，如果它被证明存在性能问题，则进行相应的更改。 - ppeterka

@CodesInChaos 我尝试对80MB的文件使用MessageDigest，似乎需要比消耗InputStream多约300ms的时间。 - Sebastien Lorber

@ppeterka66，我没有提供整个上下文，并不意味着你可以随便发表评论。请注意，这个问题可能会导致批处理程序的改进，以便处理大量文件。批处理中的文件哈希步骤可能需要每个文件块长达20分钟的时间，因此减少哈希时间可能会使批处理程序的执行时间缩短到原来的20％，这对我们的业务案例非常敏感。 - Sebastien Lorber

@SebastienLorber，有了260MB/s的速度，只有在你拥有2Gb/s的网络连接时哈希才会成为限制。如果这真的是一个限制，你可以切换到本地代码。本地MD5应该在500到1000 MB/s之间。 - CodesInChaos

Answer 1

如果你只是想在传输过程中检测意外损坏等问题，那么一个简单的（非加密）校验和就足够了。但请注意，例如16位校验和将无法检测到2的16次方中的一次随机损坏。而且它不能防止有人故意修改数据。

维基百科页面Checksums列出了各种选项，包括一些常用（且便宜）的选项，如Adler-32和CRC。

但是，我同意@ppeterka的看法。这似乎是“过早优化”。

- Stephen C

Answer 2

我知道很多人不相信微基准测试，但让我分享一下我的测试结果。

输入：

bigFile.txt = 大约143MB大小的文件

hashAlgorithm = MD2、MD5、SHA-1

测试代码：

       while (true){
            long l = System.currentTimeMillis();
            MessageDigest md = MessageDigest.getInstance(hashAlgorithm);
            try (InputStream is = new BufferedInputStream(Files.newInputStream(Paths.get("bigFile.txt")))) {
                DigestInputStream dis = new DigestInputStream(is, md);
                int b;
                while ((b = dis.read()) != -1){
                }
            }
            byte[] digest = md.digest();
            System.out.println(System.currentTimeMillis() - l);
        }

results:

MD5
------
22030
10356
9434
9310
11332
9976
9575
16076
-----

SHA-1
-----
18379
10139
10049
10071
10894
10635
11346
10342
10117
9930
-----

MD2
-----
45290
34232
34601
34319
-----

似乎 MD2 比 MD5 或 SHA-1 稍微慢一些。

- nkukhar

---

谢谢，但逐字节读取会导致性能不佳。我可以在没有哈希的情况下在200毫秒内读取该文件，在使用MD5时需要300毫秒，这似乎是最好的结果。 - Sebastien Lorber

然而，MD2、MD5、SHA-1或任何加密校验和都不是适合此工作的正确工具。您正在测量垃圾车的加速度，以确定其在微基准测试中是否适合参加印第赛车比赛。 - President James K. Polk

@GregS，你能解释一下你的意思吗？ - Sebastien Lorber

@SebastienLorber：你的问题表明你想检测意外文件损坏而不是有意的文件操作。像Adler-32或CRC（参见Stephen C的答案）这样的校验和比MD-x或SHA-x更快且更适合。 - President James K. Polk

实际上，我们发送文件到远程主机时进行哈希检查（我认为这是法国数字化准则中的合法事项），并不支持校验和算法。 - Sebastien Lorber

Answer 3

像NKukhar一样，我尝试进行微基准测试，但使用不同的代码并获得了更好的结果：

public static void main(String[] args) throws Exception {
    String bigFile = "100mbfile";


    // We put the file bytes in memory, we don't want to mesure the time it takes to read from the disk
    byte[] bigArray = IOUtils.toByteArray(Files.newInputStream(Paths.get(bigFile)));
    byte[] buffer = new byte[50_000]; // the byte buffer we will use to consume the stream

    // we prepare the algos to test
    Set<String> algos = ImmutableSet.of(
            "no_hash", // no hashing
            MessageDigestAlgorithms.MD5,
            MessageDigestAlgorithms.SHA_1,
            MessageDigestAlgorithms.SHA_256,
            MessageDigestAlgorithms.SHA_384,
            MessageDigestAlgorithms.SHA_512
    );

    int executionNumber = 20;

    for ( String algo : algos ) {
      long totalExecutionDuration = 0;
      for ( int i = 0 ; i < 20 ; i++ ) {
        long beforeTime = System.currentTimeMillis();
        InputStream is = new ByteArrayInputStream(bigArray);
        if ( !"no_hash".equals(algo) ) {
          is = new DigestInputStream(is, MessageDigest.getInstance(algo));
        }
        while ((is.read(buffer)) != -1) {  }
        long executionDuration = System.currentTimeMillis() - beforeTime;
        totalExecutionDuration += executionDuration;
      }
      System.out.println(algo + " -> average of " + totalExecutionDuration/executionNumber + " millies per execution");
    }
  }

这会在一台性能良好的i7开发者机器上，对于一个100mb的文件产生以下输出：

no_hash -> average of 6 millies per execution
MD5 -> average of 201 millies per execution
SHA-1 -> average of 335 millies per execution
SHA-256 -> average of 576 millies per execution
SHA-384 -> average of 481 millies per execution
SHA-512 -> average of 464 millies per execution

- Sebastien Lorber

---

也用"CRC32"进行测试。 - ppeterka