HashMap的长度为什么必须是2的n次方
首先咱们看下HashMap中的源码当中那里奠定了长度是2的n次方，并且是凑近cap这个值最近的2的n次方
static final int tableSizeFor(int cap) { // 首先cap-1使得n的最初一位和cap最初一位相对不一样 int n = cap - 1; // 向右无符号的挪动了1位，并应用或运算使n的所有有1的位上全副是1 n |= n >>> 1; // 向右无符号挪动2位，应用或运算将低位填充为1 n |= n >>> 2; // 同理可得 n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; // 曾经向右挪动多个位，最终 00011111 = 31 那么 +1 既成为了2的n次方 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}由上方代码能够看出，上方的办法是将cap无符号的向右挪动，再启动期间，应用|运算保障低位全副是1。
看起来有点简单，那咱们举个例子：
- 首先咱们传入
cap初始值为17 - 通过
int n = cap -1也就是17-1后n = 16 - 将n进行如下的位挪动和逻辑运算，最初失去
n = 31 - 返回是依据三目运算符，得值返回值是
n + 1 = 32，正好是 2的5次方
通过上方的容量计算，咱们曾经确定在HashMap中capacity 肯定是2的n次方，那么为什么咱们必须要
- &运算速度快，至多比%取模运算快
能保障索引值必定在 capacity 中，不会超出数组长度，
(n - 1) & hash，当为2的n次方时，会满足一个公式：(n - 1) & hash = hash % n
两种运算效率差异到底有多少，这里能够间接做个测试：
public static void main(String[] args) { int times = Integer.MAX_VALUE; /* 此处计算2^31-1次9999整数对1024的取模，应用的数学计算 * 屡次执行放大工夫 */ long currentTimeMillis = System.currentTimeMillis(); int a = 0; for (long i = 0; i < times; i++) { a = 9999 % 1024; } long currentTimeMillis2 = System.currentTimeMillis(); /* 此处计算2^31-1次9999整数对1024的取模，应用的位运算 * 因为要求 hash&(n-1) 中n必须为2的n次方，这里取1024 */ int b = 0; for (long i = 0; i < times; i++) { b = 9999 & (1024 - 1); } long currentTimeMillis3 = System.currentTimeMillis(); System.out.println(a + "," + b);//最初的后果应该是一样的 System.out.println("数学计算耗时: " + (currentTimeMillis2 - currentTimeMillis));// 1839ms System.out.println("位运算耗时: " + (currentTimeMillis3 - currentTimeMillis2));// 852ms}那么当咱们在HashMap初始化时，如果指定非2的n次方整数为初始化容量initialCapacity，那么会不会以致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; // 此处能够看到下一次扩容的值曾经通过转换，是2的n次方，并且只有在put时才会有Entry数组的创立 this.threshold = tableSizeFor(initialCapacity);}由下面的源码咱们能够看到，HashMap的容量通过了tableSizeFor办法解决，能保障容量永远都是2次幂。