关于hashMap的容量为什么是2的幂次方数

先看hashMap的构造方法

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);
    }
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }

可以看见,经过构造方法的相互调用,如果默认无参的话,会得到一个大小为initialCapacity,负载因子为loadFactor的hashMap

其中initialCapacity为16,loadFactor为0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

注意构造方法的最后一句

this.threshold = tableSizeFor(initialCapacity);

重点:这里就是为什么hashMap的容量为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;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

这里我们举个例子,假如传入的initialCapacity不为2的幂次方时,假如为9

int n = cap – 1;//此时cap为9,这里的n就为8

n |= n >>> 1;//8的二进制为1000,右移一位为0100,然后0100与1000做”|”运算的结果为1100,此时n就被赋值为1100

n |= n >>> 2;//此时n为1100,右移一位为0110,然后0110与1100做”|”运算的结果为1100,此时n就被赋值为1110

n |= n >>> 4;//此时n为1110,右移一位为0111,然后1110与0111做”|”运算的结果为1111,此时n就被赋值为1111

n |= n >>> 8;//此时n为1111,右移一位为0111,然后1111与0111做”|”运算的结果为1111,此时n就被赋值为1111

n |= n >>> 16;//此时n为1111,右移一位为0111,然后0111与1111做”|”运算的结果为1111,此时n就被赋值为1111

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;//这一步如果n<0就返回1,否则就继续比较,如果n>=MAXIMUM_CAPACITY就返回MAXIMUM_CAPACITY,否则返回n+1

总结:如果initialCapacity是2的幂次方,就返回initialCapacity,否则就返回大于initialCapacity的最近的2的幂次方

为什么initialCapacity一定得是2的幂次方呢?

接下来继续看

int n=tab.length-1
int index = (n – 1) & hash;

这里返回数组下标的时候是用hashcode的值与数组长度取余

因为前面讲过,数组大小一定是2的幂次方,所以这里讲解如果不是2的幂次方会有什么后果

• 假设数组大小为15,此时n就为14,二进制为0000,1110,假如hashCode的值为0000,0111此时取余为0000,0110
• 假如hashCode的值为0000,0110此时取余为0000,0110,这里的0000,0110和0000,0111就出现了放入一个数组下标的桶里面,就会浪费一个桶

相反,如果数组大小为2的幂次方的话,(n-1)的值高位全是0,低位全是1,此时hashCode的值就完全决定了放入的桶,且碰撞概率就减小了,也不会出现桶的浪费

这里选择取余操作是因为取余是计算机底层的东西,比取模要快

原文地址：http://www.cnblogs.com/happy12123/p/16846381.html