【Java集合篇】为什么HashMap的Cap是2^n，如何保证？

??目录

?? 为什么是2 ^ n ?

HashMap是通过 (table.length - 1) & (key.hashCode ^ (key.hashCode >> 16)) 定位 tablelndex 的。

为什么是用 & 而不是用 % 呢 ? 因 为 & 是基于内存的二进制直接运算，比转成十进制的取模快的多。又因为 X % 2^n = X & (2n - 1)，可以把%运算转换为&运算。所以，hashMap的 capacity 一定要是 2^n。这样，HashMap计算hash的速度才够快。

??为什么 X %2^n = X & (2^n - 1) ?

假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 -1 = 7，即0111。

此时X &(2^3 - 1)就相当于取X的2进制的最后三位数。

从2进制角度来看，X/8相当于 X >>3，即把X右移3位，此时得到了X/8的商，而被移掉的部分(后二位)，则是X % 8，也就是余数。

上面的解释不知道你有没有看懂，没看懂的话其实也没关系，你只需要记住这个技巧就可以了。或者你可以找几个例子试一下。

如: 6%8 = 6，6&7= 6 10 %8 = 2，10&7 = 2

??如何保证

要想保证 HashMap 的容量始终是2^n次方，需要在Map初始化的时候，和扩容的时候分别保证。

/**
*    当我们在实现HashMap时，为了保持其容量始终为2的幂，我们可以重写其resize方法，在每次扩容时调整容量为最接近的2的幂。
*/
public class MyHashMap<K, V> extends HashMap<K, V> {  
    private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16, which is 2^4  
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;  
  
    @Override  
    protected void putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict, Node<K,V> node) {  
        // 在这里添加初始化时的逻辑  
        System.out.println("Putting key: " + key + ", value: " + value);  
        super.putVal(hash, key, value, onlyIfAbsent, evict, node);  
    }  
  
    @Override  
    protected Node<K,V>[] resize() {  
        // 获取当前容量  
        int oldCapacity = this.capacity;  
        // 计算新的容量，为最接近的2的幂  
        int newCapacity = Integer.highestPowerOfTwo(oldCapacity * 2);  
        // 调用父类的resize方法  
        return super.resize();  
    }  
}

??初始化时期保证

当我们通过 HashMap(int initialCapacity)设置初始容量的时候，HashMap并不一定会直接采用我们传入的数值，而是经过计算，得到一个新值，目的是提高hash的效率。(1 -> 1、3`-> 4、7 -> 8、9 -> 16)

在JDK 1.7和JDK 1.8中，HashMap初始化这个容量的时机不同。JDK 1.8中，在调用HashMap的构造函数定义HashMap的时候，就会进行容量的设定。而在JDK 1.7中，要等到第一次put操作时才进行这一操作。

看一下JDK是如何找到比传入的指定值大的第一个2的幂的：

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;
	n |= n >>>32;
	n |= n >>>64;
	n |= n >>>128;
	n |= n >>>256;
	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

上面的算法目的挺简单，就是: 根据用户传入的容量值(代码中的cap)，通过计算，得到第一个比他大的2的幂并返回。

请关注上面的几个例子中，标记颜色字体部分的变化情况，或许你会发现些规律。

5->8、9->16、19->32、37->64 都是主要经过了两个阶段

Step 1，5->7
Step 2，7->8
Step 1，9->15
Step 2，15->16
Step 1，19->31
Step 2，31->32

对应到以上代码中，Step1:

	n |= n >>>1;
	n |= n >>>2;
	n |= n >>>4;
	n |= n >>>8;
	n |= n >>>16;

对应到以上代码中，Step2:

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

Step 2 比较简单，就是做一下极限值的判断，然后把Step 1得到的数值+1。


Step 1 怎么理解呢?其实是对一个二进制数依次无符号右移，然后与原值取或。其目的对于一个数字的二进制，从第一个不为0的位开始，把后面的所有位都设置成1。


因为cap是int类型的，所以最多需要右移16位即可获取其最大值

随便拿一个二进制数，套一遍上面的公式就发现其目的了：

1100 1100 1100 >>>1 = 0110 0110 0110
1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110
1110 1110 1110 >>>2 = 0111 1011 1011
1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111
1111 1111 1111 >>>4 = 1111 1111 1111
1111 1111 1111 |  1111 1111 1111 = 1111 1111 1111

通过几次无符号右移和按位或运算，我们把1100 1100 1100转换成了1111 1111 1111，再把1111 1111 1111加1，就得到了1 0000 0000 0000，这就是大于1100 1100 1100的第一个2的幕。

好了，我们现在解释清楚了Step 1和Step 2的代码。就是可以把一个数转化成第一个比他自身大的2的次幂。

但是还有一种特殊情况套用以上公式不行，这些数字就是2的幂自身。如果cap=4套用公式的话。得到的会是 8，不过其实这个问题也被解决了，重点就在 int n = cap - 1; 这行代码中，HashMap会事先将用户给定的容量-1，这样就不会出现上述问题了。

总之，HashMap根据用户传入的初始化容量，利用无符号右移和按位或运算等方式计算出第一个大于该数的2的幕。

??扩容时期保证

除了初始化的时候会指定HashMap的容量，在进行扩容的时候，其容量也可能会改变。

HashMap有扩容机制，就是当达到扩容条件时会进行扩容。HashMap的扩容条件就是当HashMap中的元素个数 (size) 超过临界值 (threshold) 时就会自动扩容。

在HashMap中， threshold = loadFactor * capacity 。

loadFactor是装载因子，表示HashMap满的程度，默认值为0.75f，设置成0.75有一个好处，那就是0.75正好是3/4，而 capacity 又是2的幕。所以，两个数的乘积都是整数。

对于一个默认的HashMap来说，默认情况下，当其size大于12(16*0.75)时就会触发扩容。

下面是HashMap中的扩容方法(resize)中的一段:

if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
	newThr = oldThr << 1: // double threshold
}

因为oldThr已经是2^n了， 所以oldThr无符号左移之后，是oldThr*2，自然也是2^n。至于后续HashMap是如何扩容的，请听下回分解~