1.HashMap源码学习(jdk8)

1.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;
    }

2的整数幂用二进制表示都是最高有效位为1，其余全是0，比如十进制8和32，下图只用了一个字节示意.

 

对任意十进制数转换为2的整数幂，结果是这个数本身的最高有效位的前一位变成1，最高有效位以及其后的位都变为0,核心思想是，先将最高有效位以及其后的位都变为1，最后再+1，就进位到前一位变成1，其后所有的满2变0。所以关键是如何将最高有效位后面都变为1。

 

 

 

 

 

初始容量-1
之所以在开始移位前先将容量-1，是为了避免给定容量已经是8.16这样2的幂时，不减一直接移位会导致得到的结果比预期大。比如预期16得到应该是16，直接移位的话会得到32。在上图中就是所有X本身已经是0的情况下，不减1得到的结果变大了。