Java编程：浅析 HashMap 中数组的 size 为什么必须是 2 的整数次幂

以你之姓@ 2022-06-09 08:10 195阅读 0赞

直入主题：HashMap 中数组的 size 必须是 2 的幂，是为了将 key 的 hash 值均匀的分布在数组的索引上，下面我们来进行分析。如有不正之处，欢迎批评指正。

HashMap 中使用 indexFor 方法来计算 key 所在的数组的索引，实现逻辑为 key 的 hash 值与数组的长度值减 1 进行与运算，代码如下：

/** * Returns index for hash code h. */
        static int indexFor(int h, int length) {
            return h & (length - 1);
        }

我们举两个例子来说明原因。  
例一： 假定 length = 50 （非 2 的整数次幂），二进制值为 0011 0010，这里我们使用 8 位二进制数来进行计算。length - 1 = 49，二进制值为 0011 0001。我们计算任何整数与 49 进行与运算的可能的结果如下：

0000 0000 //0
    0000 0001 //1
    0001 0000 //16
    0001 0001 //17
    0010 0000 //32
    0010 0001 //33
    0011 0000 //48
    0011 0001 //49

可能的结果值为：0、1、16、17、32、33、48、49，对于一个长度为 50 的数组，我们只命中了其中的 8 个索引值，产生了索引值的非均匀分布。

例二： 假定 length = 32（2的五次幂），二进制值为 0010 0000，这里我们使用 8 位二进制数来进行计算。length - 1 = 31，二进制值为 0001 1111。我们计算任何整数与 31 进行与运算的可能的结果如下：

0000 0000 //0
    0000 0001 //1
    0000 0010 //2
    0000 0011 //3
    0000 0100 //4
    0000 0101 //5
    0000 0110 //6
    0000 0111 //7
    0000 1000 //8
    0000 1001 //9
    0000 1010 //10
    0000 1011 //11
    0000 1100 //12
    0000 1101 //13
    0000 1110 //14
    0000 1111 //15
    0001 0000 //16
    0001 0001 //17
    0001 0010 //18
    0001 0011 //19
    0001 0100 //20
    0001 0101 //21
    0001 0110 //22
    0001 0111 //23
    0001 1000 //24
    0001 1001 //25
    0001 1010 //26
    0001 1011 //27
    0001 1100 //28
    0001 1101 //29
    0001 1110 //30
    0001 1111 //31

可能的结果值为：0 到 31，对于一个长度为 32 的数组可能的索引值范围也刚好是 0 到 31，以此类推，当 HashMap 中数组的 size 为 2 的整数次幂时，可以保证 key 的 hash 值被均匀的分布到数组上。因此建议大家尽量将 HashMap 的 initialCapacity 值设置为 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);
    
        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
    
        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
    }

其中如下代码保证 capacity 的值为 2 的整数次幂，保证了 key 索引值的均匀分布。

// Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;