HashMap的初始化大小为什么是2的幂

首先看下java初始化大小的源码（代码来自jdk1.8）

   //构造方法
   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);
    }
    
    //初始化长度的方法 
    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的幂的数。

运算原理案例：（假如我们传入cap=5）

核心原理：从左到右，使用左边第一个`1`填充后面的所有位置
    
int n = cap -1;   n=4   00000100
n|= n>>>1;     n做无符号右移1位再和n做 `|`运算，
               n>>>1:  00000100  -> 00000010
               |n   :  00000100   |
                       00000010   
                    ------------------
                  结果：00000110
                   
n|=n>>>2;    n做无符号右移2位再和n做 `|`运算，
               n>>>2:  00000110  -> 00000001 10(后面两位超出边界舍弃)
               |n   :  00000110   |
                       00000001   
                    ------------------
                  结果：00000111
                   
...
      以此类推就可以将任何传入的参数改变为比它大的而且是离它最近的2的幂

为什么初始化的大小必须是2的幂

原因有两点：1.加快哈希运算 2.减少哈希冲突

1.加快哈希运算

我们都知道比如向hashMap中存入一个值,通常做法是对这个值求hashCode()得到一个数hash,然后在用hash对集合长度求余数,也就是 hash%length=positon得到的结果就是存放的位置。

但是求余%的运算效率比较低。有没有更快的运算呢？答案是使用&运算。但是使用&运算怎么样才能和使用%效果一样呢？那就是，当HashMap的长度为2的幂的时候一下公式就成立了:hash%length==hash&(length-1)。

所以就可以使用&运算来求位置下标了。

2.减少哈希冲突,保证数据分散

使用2的幂为长度，则length-1后为奇数，该奇数转为2进制后最后一位肯定是1。

假如长度为4,则长度-1为3,再转为2进制==0000011，该值与任何hash做&运算都会形成==奇数==或者==偶数==两种情况,保证数据时分散的。

可能有人会想这有什么用？那么我们假如长度不是4而是3，则3-1为2,再转为2进制==0000010，该值与任何hash做&运算都会形成==偶数==,那也就是说我的奇数的下标都不能用了。这样就不仅浪费一般的空间，而且增加了hash冲突的概率.

最后编辑于：2020.01.17 11:05:14