Java HashMap 中为何需要 hash() 方法？

源码解释

在 Java 的 HashMap 源码中，put() 和 get() 方法会首先获取 key 的哈希值。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

而这个 hash(key) 方法并不是简单地直接返回对象 key 的 hashCode()。

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

从上面代码可以看到 key 的哈希值的计算方法：取对象 key 的原始哈希值，低16位与高16位做异或得出最终的哈希值。

h >>> 16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。

为什么要这么做呢？

原理说明

这个与HashMap中table下标的计算有关。

1 2	n = table.length; index = （n-1） & hash;

因为，table 的长度都是2的幂，因此 index 仅与 hash 值的低 n 位有关，hash 值的高位都被与操作置为0了。
假设 table.length = 2^4 = 16。

由上图可以看到，只有 hash 值的低4位参与了运算。

这样做很容易产生碰撞。设计者权衡了speed, utility, quality，将高16位与低16位异或来减少这种影响。设计者考虑到现在的 hashCode 分布的已经很不错了，而且当发生较大碰撞时也用树形存储降低了冲突。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算（table 长度比较小时），从而引起的碰撞。

参考源码中的注释：

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  
 * 计算 key.hashCode() 并把高位和移位进行异或。 
 *
 * 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.)  
 * 因为存放 Node 的 table 使用2的幂（2^n-1）作为计算数组下标时的掩码，
 * 如果元素的哈希值都集中在掩码范围内，那么哈希碰撞的概率很大。（已知的例子有
 * 浮点数的哈希值都集中在一个较小的范围呢）
 *
 * 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);
}

有的地方也称这段代码为”扰动函数“，并做了做实验对比了添加”扰动函数“之后冲突减少的比例（达10%）。参考 https://www.zhihu.com/question/20733617/answer/111577937

–

文章参考来源：https://www.cnblogs.com/liujinhong/p/6576543.html