必知必会--HashMap容量细节

前言

HashMap作为Java中最常用的数据结构之一，在工作中使用HashMap的频率和你遇见NullPointException一样多。作为最常用的数据结构之一，我们都知道HashMap的容量为2次幂。当被问到为什么是2次幂时，大家应该都能回答出来，是为了将结点均匀分散到数组中。当容量为2次幂能够均匀分散结点，3次幂为什么不能？HashMap中如何解决Hash碰撞？在HashMap的构造方法中可以传入容量，如果传入非2次幂怎么办？看完这篇文章你会解决其中的疑问。

ps:代码来源于JDK1.8

正文

HashMap底层数据结构为数组+链表+红黑树。当我们向HashMap中插入一个对象，HashMap会通过Index映射算法得到该对象插入到数组的下标index。此时HashMap分辨这个位置有没有值以及值类型。如果index没有值，将当前对象放入当前位置。如果index有值，判断对象的key是否与该值的key相等（key的hash值相等以及key本身相等），如果key相等则覆盖该值，如果key不相等，将对象插入该值的尾部（链表和红黑树不同的处理）。

Index映射算法

int index = (n - 1) & hash
           

对于为什么采用&运算而不是%。1：&运算比%运算效率高很多；2：当n为2次幂，(n-1)&hash等同于hash%n。

如果HashMap的容量不是2次幂

假设当前HashMap的初始容量为17，即n等于17时。

1：n=17则n-1=16，16的二进制表示为0010000。

2：如果我现在向HashMap中插入两个键值对，key1=A，Key2=B。假设通过Hash算法得知A的hash值为1010110，B的Hash值为0110000

3：分别算出key等于A，B时所映射的index

0010000  0010000

1010110  0110000

-------------------------

0010000  0010000

Hash值差别那么大，得到的index值确实相同。这是由于&运算的特殊性导致的，在二进制中&符号两边的元素只要有一个为0，"&"操作执行后的结果就为0。因此当n=17时，计算出来的index只有两个值，0或者16。

如果我们向这个HashMap中保存大量的键值对，所有的键值对都会堆积在数据的第0个或者第16个位置，而第1-15个位置会一直是null。

为什么当n为二次幂时，可以让键值对均匀分散，不会造成键值对堆积呢？

当n为二次幂，n-1的二进制表示中所有的低位均为1，如果n是16，n-1的二进制表示就是01111。这个时候通过（n-1）&hash得到的值能够分散到0-15的每一个位置中，而且分散到每一个位置的概率都相同，不会发生键值对堆积在某几个位置的现象。

讲到这里大家对HashMap的容量为什么是二次幂应该有了解，为了让键值对均匀分散到数组中。如果键值对只是堆积在某几个位置，这完全浪费了数组其余位置的资源，同时还增加了HashMap获取键值对的复杂度，对cpu资源也是一种浪费。

HashMap如果解决碰撞

说到Hash碰撞，来思考这一个问题，如果有很多key的hash值低位不变化，只是在高位变化，这样岂不是也会造成键值对的堆积。比如010110000，110110000，000010000。如果此时n等于32，计算出来的index都等于16。我们关注一下如何计算一个key的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);
    }
           

在注释中我们可以找到这个问题的答案

翻译：计算key的hashcode值，同时将hash值的高位传递给低位。因为表的长度使用二次幂，因此仅在高位变化的散列总是发生冲突（已知的例子是在小的表中保存连续整数的浮点键）。所有我们就利用了一个转换，将高位向下转移。这是一个在速度，效率，位移动上的交易。因为许多的Hash值是合理分布的（所有不利于传递）。并且我们使用红黑树去处理更多hash值的碰撞情况。所有我们用一些减少系统消耗并且廉价的方式去转移一些字节，以及可以利用高位的值来计算index值，否则高位不会参与到index的计算中。

为了避免Hash值低位不变，仅高位变化的情况，HashMap的设计者在设计Hash算法时利用^运算使得Hash值的高位与低位相互碰撞，让Hash值的高位与低位同时参与index的计算中。

HashMap如何将任意值转化为一个二次幂的值

我们发现在HashMap的构造方法中可以传入容量这个参数。如果传入的值是非二次幂，那是不是会造成键值对堆积的情况。

/**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
           

HashMap初始化会根据initialCapacity分为三种情况

情况1：如果传入的initialCapacity小于0，抛异常。

情况2：如果initialCapacity大于最大容量，将最大容量赋予给initialCapacity。

最后3：调用tableSizeFor方法，将initialCapacity转化为一个二次幂的值，然后赋予给threshold。HashMap初始化时，使用threshold作为HashMap数组的长度。

因此如果通过HashMap的构造函数传入的容量是一个非二次幂，HashMap会通过tableSizeFor方法将这个值转化为二次幂。

/**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
           

这部分有点难理解，举个例子说明

假设传入的参数cap是一个非二次幂，cap=17

1.n-1=16。二次幂表示为0010000（一个1）

2.n |= n >>> 1。计算得到n等于0011000（两个1）

3.n |= n >>> 2。计算得到n等于0011110（四个1）

4.n |= n >>> 4。计算得到n等于0011111（五个一）

5.n |= n >>> 8。计算得到n等于0011111（五个一）

6.n |= n >>> 16。计算得到n等于0011111（五个一）

7.n+1等于0100000，十进制等于32。

总结

1.当HashMap的数组长度为二次幂，能够将键值对均匀分散到数组的每一个位置上。

2.index映射算法和%能够达成一样的效果，并且效率更高效。

3.Hash算法在设计时利用移位和异或运算符^来避免Hash碰撞。

4.如果通过HashMap的构造函数传入的容量是一个非二次幂，HashMap会通过tableSizeFor方法将这个值转化为二次幂的值。