HashMap为什么是2的幂次方

一、HashMap为什么是2的幂次方

HashMap 是 Java 集合体系中的一个底层实现工具类，采用散列表实现，因此其底层采用数组存储。数组是一种随机访问结构，可以通过固定偏移量和下标的计算方式直接跳转到指定位置。但是，散列表可以使元素在数组中的位置任意，所以必须通过散列函数计算元素所在位置，如果不重写散列函数，Java 使用的是 hashCode() 方法的返回值，而 hashCode() 返回一个整数，所以 HashMap 底层的数组必须是整数下标。

散列表按照键值对存储，也就是说要存储两个值：键和值，这里我们称之为 entry。这些 entry 存储在一个 Entry 数组中，在 Java 8 中，该数组被 Node 数组取代，每个 Node 保存一个键值对。数组的长度是固定的，而且在初始化时必须得到指定，但是作为编程人员，在写程序时很难事先预知将要存储到 Map 中的键值对的数量，因此，Java 在该初始化确定数组长度后，如果达到一定条件时，自动对该数组进行扩展，进而改变数组长度。

在 HashMap 中，数组长度是2的幂次方，这是因为计算机在计算 hash 值时就需要用到 “& size – 1″，而计算机在做除法时除法的成本远高于求余数的成本，同时采用位运算的效率通常要比模运算的效率高，因此使用2的幂次方作为数组长度，是因为形式上最能体现出求余数和位运算的最佳实践。

    /**
     * 初始化容量（必须是 2 的幂且小于 1 << 30）
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

二、HashMap扩容为什么是2倍

扩容的本质是数组扩容，数组的长度必须是2的幂次方，如果按1进行扩容数组长度的画，每次扩容都要重新计算每个元素的位置，而2倍扩容操作是一次性完成，是为了加速计算，同时也为了防止出现哈希冲突，保证散列的均匀性。

    /**
     * 加载因子，当 HashMap 所容纳的元素数量达到 totalSize * loadFactor 时，就需扩容
     */
    final float loadFactor;

    /**
     * 扩容操作，扩容后的大小必须是2的幂次方
     */
    final void resize() {
        //...
        newCap = oldCap << 1;
        //...
    }

三、HashMap的长度为什么是2的幂次方

HashMap 的长度并不是随意设置，而是必须是2的幂次方，这样一来，可以使Entry放入数组时，并且计算出它的位置 index。使用 n & (length-1) 就相当于对 length 取模，但是比直接对 length 取模效率更高，因为&运算比%运算效率更高。

在 JDK1.7 中，HashMap 有一个默认的负载因子 loadFactor，如果散列表中当前元素个数超过了数组长度与负载因子的积，就需要进行扩容，否则，当hash表中的元素个数过多，会出现大量的hash冲突，会导致HashMap变慢。JDK1.8 对扩容机制做出了调整，基本上渐进时间复杂度从 O(n) 降低到了 O(1)。

    /**
     * 初始化容量（必须是 2 的幂且小于 1 << 30）
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    /**
     * 最大容量（必须是 2 的幂且小于 1 << 30）
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 链表的最小长度
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * 链表长度过长时，转换成红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 当转化红黑树后，最小的hash表容量大小
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 加载因子，当 HashMap 所容纳的元素数量达到 totalSize * loadFactor 时，就需扩容
     */
    final float loadFactor;

四、HashMap为什么链表选取3~5个

为了解决哈希冲突，Java 在 JDK1.8 中通过弱化了 Node 结构中的 next 指针，在链表长度等于8时才考虑红黑树化后的转换。链表转换成红黑树，只针对 HashMap，ConcurrentHashMap 在 JDK1.8中并没有这种转化逻辑。由于红黑树的高度不高于 log(n)，相当于在链表长度大于8时，查找效率更高一些。

    /**
     * 当转化红黑树后，最小的hash表容量大小
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 链表长度过长时，转换成红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;

通过以上分析，可以看出 HashMap 选择 2 的幂次方作为数组长度的原因，HashMap 长度为什么是2的幂次方，扩容为什么是2倍，以及链表选取3~5个的相关原因。这些策略使得 HashMap 在底层实现中保证了时间和空间的效率。