/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
下面是JDK 1.6的早期版本
/**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions. This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
有人能解释一下应用这种散列比在早期版本的 java 中所做的有什么好处吗?这将如何影响 key 分发的速度和质量,我指的是在 jdk 8 中实现的新哈希函数以及它是如何实现这一点以减少冲突的?
最佳答案
在 hashCode
方法表现相当糟糕的情况下,HashMap
的性能会急剧下降。例如,假设您的 hashCode
方法只生成了一个 16
位数。
这通过异或
自身右移16
的散列码解决了这个问题。如果在此之前人数分布均匀,它应该仍然如此。如果它很糟糕,这应该会有所改善。
关于java - 理解 java 8 中 HashMap 类的 hash() 方法的方法注释,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36554000/