为什么HashMap容量一定要为2的幂呢?

原文链接：https://blog.csdn.net/wanghuan220323/article/details/78242449
做为面试常考的问题之一，每次都答的模模糊糊，有必要了解一下，首先来看一下hashmap的put方法的源码

public V put(K key, V value) { 
        if (key == null)                 
            return putForNullKey(value);     //将空key的Entry加入到table[0]中 
        int hash = hash(key.hashCode());     //计算key.hashcode()的hash值，hash函数由hashmap自己实现 
        int i = indexFor(hash, table.length);//获取将要存放的数组下标 
        /*
         * for中的代码用于：当hash值相同且key相同的情况下，使用新值覆盖旧值（其实就是修改功能）
         */ 
        for (Entry<K, V> e = table[i]; e != null; e = e.next) {//注意：for循环在第一次执行时就会先判断条件 
            Object k; 
            //hash值相同且key相同的情况下，使用新值覆盖旧值 
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
                V oldValue = e.value; 
                e.value = value; 
                //e.recordAccess(this); 
                return oldValue;//返回旧值 
            } 
        } 
         
        modCount++; 
        addEntry(hash, key, value, i);//增加一个新的Entry到table[i] 
        return null;//如果没有与传入的key相等的Entry，就返回null 
    } 

    /**
     * "按位与"来获取数组下标
     */ 
    static int indexFor(int h, int length) { 
        return h & (length - 1); 
    } 

hashmap始终将自己的桶保持在2的n次方，这是为什么？indexFor这个方法解释了这个问题

大家都知道计算机里面位运算是基本运算，位运算的效率是远远高于取余%运算的

举个例子：2^n转换成二进制就是1+n个0，减1之后就是0+n个1，如16 -> 10000，15 -> 01111

那么根据&位运算的规则，都为1(真)时，才为1，那0≤运算后的结果≤15，假设h <= 15，那么运算后的结果就是h本身，h >15，运算后的结果就是最后四位二进制做&运算后的值，最终，就是%运算后的余数。

当容量一定是2^n时，h & (length - 1) == h % length