HashMap的常见问题

为什么数组长度必须是2的n次方？

	/**
     * 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;
    }
复制代码

在初始化一个HashMap时会调用上面这个方法，方法注释说明了它的作用是返回一个2的次方数作为数组容量。

但是为什么要规定必须是2的n次方呢？

原因和计算数组下标有关，下面这些代码是put方法中用来判断数组下标位置是否已经有Node的部分。

	if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
复制代码

可以发现数组下标 i = hash & (n – 1) 的。HashMap是通过这种与运算的方式来快速获得数组下标的。

hash & (len – 1)

我们先来看len=16的情况，len-1=15=01111

观察表上结果可以发现两个规律：

1. 所有的下标都在0~15的范围内
2. 下标分布十分的均匀，以16个数为周期循环

再来看len=17的情况：

可以发现len=17时，计算出来的数组下标全部都是 0 ，这就会使所有的Node全部落在一个桶中，导致十分严重的冲突。

总结

通过上面两张表我们可以发现，之所以把数组容量规定为2的幂次，作用有两个：

• 保证len-1的最高位为0，使下标值不可能越界
• 使len-1除最高位全是1，这样可以不改变hash值，使得下标更加分散，减少冲突的发生

HashMap是如何计算hash的

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

上面的代码是jdk1.8的hash方法，jdk1.7的思路类似但是更复杂，这里不介绍。

首先，如果key是null，hash方法会返回0，这也就是为什么null key一定是存在数组下标0位置的。

key不为null时调用了Object类的hashCode()方法，然后进行了位运算。这里我们来分析为什么调用了hashCode还要位运算。

异或运算和右移运算

异或是二进制运算的一种，java中用 ^ 表示。异或运算会将每一位二进制位相比，相同的得0，不同的得1。

右移是将二进制数去除右侧低位，在左侧高位补零的运算。

比如：

0101011 >>> 2 = 0001010
复制代码

key.hashCode()

java中规定了，当我们重写了Object类的equals方法后必须重写hashCode方法。这是因为两个对象相等hashCode也必须相等。

既然我们可以改写hashCode方法，那么hashMap直接使用这个hashCode就不合理了。这也就是为什么还要计算hash的原因之一。

回到 hash & (len – 1)

之前提到HashMap使用这个表达式计算数组下标的，计算时需要考虑到key的分布来减少冲突的发生。

表达式中 hash 是 32位，len-1的高位全是0，低位是1。也就是说我们只会用到hash 32位二进制位的一部分。

比如len是16，那么我们只会用到hash值32位中的4位。

这下再回到hash（）方法就清晰了。

1. 这里将h右移了16位，16这个数正好将hash值分为两半
2. 如果要用到16位的hash做与运算，那么len = 2 ^ 17。这个容量明显是很难达到的，也就是说hashcode至少有一半的长度没有利用起来。

结论

• 右移后再与原值异或，最大的作用就是使hashcode的每一位都得到充分的利用。充分利用的32位值也可以减小冲突发生的可能。
• 用户可能重写了hashCode方法，hash()方法可以打乱重写逻辑，避免重写可能导致的冲突几率提高

为什么负载因子是0.75

	/*Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million
复制代码

HashMap源码中有以上的一段注释。大概意思是说，在随机的hashcode条件下，Node在哪个桶中符合泊松分布。并给出了在负载因子是0.75时，同一个桶中链表不同长度的概率。

其中链表长度为8的概率已经是 千万分之六，几乎是不可能出现的。至于是怎么算出来的… …（我也没算过）

结论1：负载因子在0.75时，链表长度很难达到8。

抛开数学的东西，我们来考虑负载因子的大小对HashMap的影响。

• 负载因子大于1明显不可能，这样HashMap永远都不会扩容，将导致严重的冲突
• 负载因子很接近1，这会使数组要达到满载时才会触发扩容，也会让冲突频繁
• 负载因子很小，数组会频繁触发扩容，这样的好处是key会变得分散，冲突会减少。但是扩容会占用大量时间，而且数组元素会很散，使空间利用率变低。

结论2：负载因子应该是一个0.5附近的值，以此来平衡过大和过小的情况。