HashMap#hash()
此方法将根据指定的key,获取其对应的hash值,hash值用来确定数组下标。
/**
* 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);
}
符号>>>
为无符号右移,高位补0。hash值的计算过程如下:
为什么不直接使用key的hashcode()
值,而是将hashcode的高16位与低16位异或结果作为hash值?
首先看一下我们是如何获取数组下标的。
// 数组长度
n = tab.length;
// 数组下标
i = (n - 1) & hash;
我们来比较一下直接使用key的hashcode值作为hash值 和 将hashcode的高16位与低16位异或结果作为hash值的区别,我们以数组长度n=16为例:
- 如果直接使用hashcode作为hash值,由于数组长度-1导致低4位为1,其余高28位均为0。导致仅仅在高28位变化的那些hashcode与15进行与运算后得到的结果一致,从而发生碰撞。已知的例子是在小表中保存连续整数的Float键集。
- 经过高16位与低16位的异或运算而得到的hash值,是一种比特传播速度、效率、系统损失之间的权衡,通过这种方式,可以在尽量减少碰撞的同时也减少系统损失。
我们把此方法上面的注释看一下就知道了。
计算key.hashCode()并将较高的散列位扩散到较低的散列位。
因为表使用的是2的幂掩码,所以仅在当前掩码以上的位上变化的哈希集总是会碰撞。(其中一个已知的例子是在小表中保存连续整数的Float键集。)因此,我们应用了一个转换,将较高位的影响向下扩散。这里涉及到比特传播的速度、效用和质量之间的权衡。
因为许多常见的哈希集已经合理地分布(因此不会从扩散中受益),而且因为我们使用树来处理箱子中的大型碰撞集,所以我们只是以最便宜的方式对一些移位的位进行XOR,以减少系统损失,并合并由于表边界而永远不会在索引计算中使用的最高位的影响。
另外,从这个方法中我们也应该知道,在hashMap中保存的key,必须重写hashcode()
方法,如String、Integer。