【HashMap】为什么长度总是2的整数次方-蒲公英云

【HashMap】为什么长度总是2的整数次方

前言

开门见山，HashMap这样做有两点原因

提升计算效率，更快算出元素的位置
减少哈希碰撞，使得元素分布均匀

提升计算效率

我们先看put方法的细节：

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

其中hash(key)如下：

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

其中(h = key.hashCode()) ^ (h >>> 16)暂时不需要理解，会在文尾进行分析，这里只需要知道hash()方法返回二次运算后的哈希值即可。

接着回到putVal()方法中：

可以看到，对于一个key，拿到hash(key)后，之后要确定这个key在数组中的位置，我们一般倾向于对数组长度length取余，余数是几，就在数组的第几个位置上，简单方便。

但对于机器而言，位运算永远比取余运算快得多，在length为2的整数次方的情况下，hash(key)%length能被替换成高效的hash(key)&（length-1）,两者的结果是相等的。

减少哈希碰撞

如果数组长度是2的整数次方时，也就是一个偶数，length-1就是一个奇数，奇数的二进制最后一位是1，因此不管hash(key)是多少，hash(key)&(length-1)的二进制最后一位可能是0，也可能是1，取决于hash(key)。即如果hash(key)是奇数的话，则映射到数组上第奇数个位置上。

如果length是一个奇数的话，length-1就是一个偶数，偶数的二进制最后一位是0，则不管hash(key)是奇数还是偶数，该元素都会被映射到数组上第偶数个位置上，奇数位置上没有任何元素！

因此，数组长度是一个2的整数次方时，哈希碰撞的概率起码能下降一半，而且所有元素也能均匀地分布在数组上。

key.hashCode()^ (h >>> 16)

可能很多人都不知道这段代码的作用，下面我谈谈自己的想法。

首先需要理解>>>的含义，即无符号右移，高位补0。例如：

0111 1110 0000 1111 1011 0001 0101 1010
右移16位得到
0000 0000 0000 0000 0111 1110 0000 1111

为什么要使用这个运算呢，直接返回key的哈希值不好吗？

一般来说，任意一个对象的哈希值比较大，随便实例化一个对象，得到它的hash值

转换成2进制后，得到

0011 1001 1010 0000 0101 0100 1010 0101

而HashMap的长度一般就在[1，2^16]左右，取length=16为例，那么直接使用key的哈希值&(length-1)后，得到

0011 1001 1010 0000 0101 0100 1010 0101
&
0000 0000 0000 0000 0000 0000 0000 1111
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101