Java - 哈希算法 - 最快实现

Question

我想知道Java中MD5和SHA-2 512 (SHA512)或256哈希算法的最佳且最快实现方式。我需要一个接受字符串参数并将哈希作为结果返回的函数。谢谢。

编辑：这是为了将每个URL映射到唯一的哈希值。由于MD5在这个领域不太可靠，所以我更感兴趣的是找到SHA-2算法的最佳和最快实现方式。请注意，我知道即使是SHA-2也可能对于某些URL产生相同的哈希值，但我可以接受这种情况。

- Alireza Noori

---

我建议不要使用MD5……它已经非常不安全了。 - Zach Langley

Java自带的实现不足以满足您的需求吗？我可以在我的笔记本电脑上使用SHA-256通过MessageDigest达到每秒100MB以上的速度。即使是随机的MD5哈希碰撞的概率也很小，如果您有“数十亿”份文件，您更可能在读这篇文章的“精确秒数”内被陨石击中。对于唯一标识，MD5已经足够了。只有当它用于安全目的且有人明确试图造成碰撞时，您才需要担心（对于URL而言，这将非常困难）。 - WhiteFang34

你知道，我想找到最好的实现方式。如果有比MessageDigest更好的实现方式，为什么不使用它呢？ - Alireza Noori

看一下Guava Hashing，它有一些可能有用的哈希工具。 - Vitalii Fedorenko

FYI，这是“MessageDigest”算法的速度比较（左侧更快）：MD5 > SHA-1 > SHA-256 > MD2。（MD5约为SHA-256的两倍快……MD2慢10倍） - Pimp Trizkit

@PimpTrizkit 谢谢您 - Alireza Noori

Answer 1

首先要说的是：速度被高估了。在宣称某个算法“太慢”之前，您应该先采取措施。大多数情况下，哈希函数速度并没有什么显著的差异。如果您对安全有疑虑，则应首先选择足够安全的哈希函数，然后再关注性能。

此外，您想要散列"字符串"。Java中的String在内部是由代表Unicode代码点的char值数组中的一小块（实际上是使用UTF-16编码的Unicode 16位代码单元）组成的。哈希函数以位或字节序列作为输入。因此，您需要进行转换步骤，例如str.getBytes("UTF-8")，以将字符串转换为一堆字节。与哈希本身相比，转换步骤可能具有不可忽略的成本。

注意：要小心URL编码！在URL中，某些字节可以替换为以'%'符号开头的序列；这旨在支持不可打印字符，但也可以用于"标准"字符（例如，用'%61'替换'a'）。这意味着在String.equals()意义下不同的两个字符串实际上可能表示相同的URL（就URL处理而言）。根据您的情况，这可能是一个问题或不是一个问题。

你应该首先尝试使用Java的MessageDigest API和标准（已安装）JCE提供程序（即，调用MessageDigest.getInstance("SHA-256")），并测试结果。理论上，JCE可能将调用映射到具有“本地”代码（用C或汇编语言编写）的实现，这将比您可以使用Java获得的更快。

话虽如此... sphlib是许多加密哈希函数的开源实现，使用C和Java编写。该代码已经针对速度进行了优化，并且在实践中，Java版本的速度比Sun/Oracle的标准JRE提供的速度更快。如果前一个链接失败，请使用this link（警告：10 MB下载）。存档还包含一份报告（在2010年的second SHA-3 candidate conference上介绍），其中提供了有关SHA-2和即将推出的SHA-3的14个“第二轮”候选者的性能数据在几个平台上的测量结果。

但是，您真的应该进行现场基准测试。例如，L1缓存的影响可能会对性能产生严重影响，并且无法通过取函数代码并在隔离状态下运行来准确预测。

- Thomas Pornin

---

谢谢。这似乎是我一直在寻找的东西。非常复杂的答案。（虽然我已经计划按照您建议的去做，但对于未来的读者来说，这也是很好的）。关于URL字符的观点非常好，我会在项目中尽量注意它。 - Alireza Noori

Answer 2

修改：我最初看到这个问题时认为是什么是"最快的哈希算法"，现在已经澄清为"每种算法的最快实现方式"。这是一个有效的问题，其他人已经指出了更快的实现方式。然而，除非你需要在短时间内散列大量数据，否则速度并不会对结果产生太大影响。我怀疑使用除了标准JCE提供的内容之外的东西可能不值得时间和复杂度。

对于URL地址，您需要在现代硬件上以SHA-256为基础进行散列，每秒高达一百万次才需要更快的算法。我不能想象大多数应用程序需要超过一千个每秒（每天超过8600万个），这意味着总CPU时间花费在散列上的比例将远远低于1%。因此，即使您拥有无限快的哈希算法，您也只能将整体性能提高1％。

原始回答：获取最好和最快的两者之间存在矛盾。更好的哈希通常更慢。如果您真的需要速度，并且安全性不是那么重要，那么使用MD5。如果您需要最佳安全性，则选择SHA-256甚至SHA-512。您没有提到您要使用它做什么，因此很难推荐哪种方法。在现代硬件上，使用SHA-256应该足够快，因此您可能最安全地选择它。以下是如何实现的：

String input = "your string";
MessageDigest digest = MessageDigest.getInstance("SHA-256");
digest.update(input.getBytes("UTF-8"));
byte[] hash = digest.digest();

如果您将此用于安全目的，例如对密码进行哈希，则还应向摘要中添加盐。如果您想从哈希中获得可打印的字符串，则可以将其编码为十六进制字符串：

static char[] HEX_CHARS = "0123456789ABCDEF".toCharArray();

StringBuilder sb = new StringBuilder(hash.length * 2);
for (byte b : hash) {
    sb.append(HEX_CHARS[(b & 0xF0) >> 4]);
    sb.append(HEX_CHARS[b & 0x0F]);
}
String hex = sb.toString();

- WhiteFang34

---

我理解这个问题是“每个算法的最快实现”，而不是最快的算法。 - Paŭlo Ebermann

但是这个“toHexString”实现很不错，加一分。 - Paŭlo Ebermann

@Paŭlo：啊，你可能是对的。OP可能应该澄清一下，并向我们提供一些有关使用情况的见解。 - WhiteFang34

由于速度似乎很重要，toHexString()的实现可以通过将十六进制数字的String替换为char[]并使用HEX_DIGITS[(b & 0xF0) >> 4]而不是调用charAt()来稍微改进。在（可能有缺陷的）微基准测试中，这被证明比原来快了约30%。 - Joachim Sauer

谢谢。在你的建议之前，我在类中使用了一个私有常量字符串，并且它提高了性能，但我将把它改为字符数组。 - Alireza Noori

Answer 3

请查看以下内容：许多SHA / MD5示例

另外：同一线程：快速MD5

使用以下代码可以生成文件的MD5哈希值：String hash = MD5.asHex(MD5.getHash(new File(filename)));

- AndyMac

---

我以前见过这两种。快速MD5可能有用，但我正在寻找更多的选择。并且如上所述，我更需要快速的SHA-2实现。 - Alireza Noori

Answer 4

另一个要考虑的事情是使用MD4。它不像MD5那样安全，但计算速度更快。Windows直到XP时代都使用MD4来存储和交换密码，所以我们使用此哈希算法，因为它仍然可以为该平台提供身份验证服务。

- Daniel

---

MD4和MD5都已被攻破，我不建议使用它们。 - Zach Langley

我也是，我不打算在我的项目中将其作为主要场景使用。我只希望在用户选择需要它时它可用。 - Alireza Noori

MD4已经被完全攻破，你最好使用循环冗余校验（CRC）。 - Bruno Rohée

Answer 5

考虑BLAKE2，它比上述哈希更快且更安全。 MD5、SHA-1、SHA256和SHA-512易受长度扩展攻击。 MD5和SHA-1易发生碰撞。 MD5易受选择前缀碰撞攻击。 SHA-3和BLAKE2没有已知的安全问题，并且可以生成不同长度的摘要。 在硬件中实现时，SHA-3最快；使用软件实现时，BLAKE2最快。 BLAKE2b针对64位平台进行了优化，可产生介于1到64字节之间的任何大小的摘要。 BLAKE2s针对8到32位平台进行了优化，可产生介于1到32字节之间的任何大小的摘要。 以下是AES、MD5、SHA-256和BLAKE2b的基准测试结果。

https://blake2.net/

https://www.cryptopp.com/benchmarks.html

在第一个链接中，BLAKE2b（947 Mbits）比SHA-256（413 Mbits）和MD5（632 Mbits）快得多。

在第二个链接中，AES-256 CBC（805 Mbits）和BLAKE2b（776 Mbits）的速度大致相同，比SHA-256（275 Mbits）和MD5（602 Mbits）更快。

- Paul Des Rivieres

---

你为什么说Blake不“容易发生碰撞”？根据鸽巢原理，它不可能完全避免碰撞。 - Jack G

Answer 6

针对字符串，只需调用hashCode()，因为在内存开销上更便宜。

否则，我建议使用以下代码进行私有哈希：

public static int hash8(String val) throws UnsupportedEncodingException {
    return hash8(val.getBytes("UTF-8"));
}

public static int hash8(byte[] val) {
    int h = 1, i = 0;
    for (; i + 7 < val.length; i += 8) {
        h = 31 * 31 * 31 * 31 * 31 * 31 * 31 * 31 * h + 31 * 31 * 31 * 31
                * 31 * 31 * 31 * val[i] + 31 * 31 * 31 * 31 * 31 * 31
                * val[i + 1] + 31 * 31 * 31 * 31 * 31 * val[i + 2] + 31
                * 31 * 31 * 31 * val[i + 3] + 31 * 31 * 31 * val[i + 4]
                + 31 * 31 * val[i + 5] + 31 * val[i + 6] + val[i + 7];
    }
    for (; i + 3 < val.length; i += 4) {
        h = 31 * 31 * 31 * 31 * h + 31 * 31 * 31 * val[i] + 31 * 31
                * val[i + 1] + 31 * val[i + 2] + val[i + 3];
    }
    for (; i < val.length; i++) {
        h = 31 * h + val[i];
    }
    return h;
}

FYI: http://lemire.me/blog/2015/10/22/faster-hashing-without-effort/

- Daniel De León

---

请问您可以解释一下上述内容吗？ - Pravat Panda

避免使用hashCode()的原因是在不同的JVM间，其结果不能保证一致性（参见Object.hashCode文档）。如果您需要将哈希值存储在某处或期望得到可重复的结果，请使用标准的哈希算法。 - Danny G

@DannyG - 如果你正在哈希字符串，那么Object.hashCode就不相关了。 - Doradus