Java 8中用于字符串键的替代哈希算法是什么？

Question

Java 8提供了替代哈希算法，以提高处理大量键哈希码冲突时的性能。有人能解释一下这是什么，并说明它将如何工作吗？

- Pramod Kumar

---

+1 这可以用来避免拒绝服务攻击。 - Peter Lawrey

谢谢，我会记住的。 - Pramod Kumar

@PeterLawrey，当您提到DoS时，您是指此错误报告还是其他内容？ - Andrzej Doyle

Answer 1

为了更加贴合这个问题，JDK 8中已经移除了可选的哈希算法。详情请查看：http://docs.oracle.com/javase/8/docs/technotes/guides/collections/changes8.html 和 http://openjdk.java.net/jeps/180。

值得注意的是，当哈希桶中的条目数超过一定阈值时，该桶将从使用条目的链表转为平衡树。

HashMap中的hash(Object key)函数已经进行了修改，对于String对象没有特殊处理。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

- mankadnandan

Answer 2

来自core-lib-devs@openjdk的这封电子邮件:

• 引入了一个新的接口Hashable32。
• Hashable32提供了一个方法hash32()。
• String实现了Hashable32和hash32()方法。
• HashMap等识别String并调用hash32()而不是hashCode()。

代码的修订：

• Murmur3：https://code.google.com/p/smhasher/wiki/MurmurHash3
• althashing "7" webrev： http://cr.openjdk.java.net/~mduigou/althashing7/8/webrev/
• althashing "8" webrev： http://cr.openjdk.java.net/~mduigou/althashing8/8/webrev/

- ewernli

---

据我所知，旧哈希算法的最大缺陷是它有时会对长字符串返回零，并且指定特定实现会排除在VM上实现“hash-string”函数的可能性，该函数旨在在该特定机器上实现最佳性能（例如，64位机器可能使用操作8个字节组的函数，然后将结果压缩为32位）。我想知道多少代码确实依赖于旧字符串哈希的确切值，以及允许“兼容性解决方案”需要付出多大努力？ - supercat

Answer 3

应该注意到，转向使用MurmurHash3并不能防止DoS攻击：http://emboss.github.com/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/

- Søren Boisen