15.为什么HashMap的容量是2的幂次方

是为快速定位元素在底层数组中的下标

HashMap是通过hash&(n-1)来定位元素的下标的，n为数组的大小，也就是HashMap底层数组的容量。

数组长度-1正好是相当于一个“低位掩码”–掩码的低位最好全是1，这样&运算才会有意义，否则结果一定是0。

2幂次方刚好是偶数，偶数-1是奇数，奇数的二进制最后一位是1，也就保证了hash&(length-1)的最后一位可能为0，也可能为1（取决于hash的值），这样可以保证哈希值的均匀分布。

换句话说，& 操作的结果就是将哈希值的⾼位全部归零，只保留低位值。

a&b 的结果是：a、b 中对应位同时为 1，则结果为 1，否则为 0。例如 5&3=1，5 的⼆进制是 0101，3 的⼆进制是 0011，5&3=0001=1。

假设某哈希值的⼆进制为 10100101 11000100 00100101 ，⽤它来做 & 运算，我们来看⼀下结果。

已知 HashMap 的初始⻓度为 16，16-1=15，⼆进制是 00000000 00000000 00001111 （⾼位⽤ 0 来补⻬）：

  10100101 11000100 00100101

& 00000000 00000000 00001111
----------------------------------

  00000000 00000000 00000101

因为 15 的⾼位全部是 0，所以 & 运算后的⾼位结果肯定也是 0，只剩下 4 个低位 0101 ，也就是⼗进制的 5。这样，哈希值为 10100101 11000100 00100101 的键就会放在数组的第 5 个位置上。

对数组下标取模定位数组下标，这块有没有优化策略？

快速回答：HashMap 的策略是将取模运算 hash % table.length 优化为位运算 hash & (length - 1) 。因为当数组的⻓度是 2 的 N 次幂时， hash & (length - 1) = hash % length 。

⽐如说 9 % 4 = 1，9 的⼆进制是 1001，4 - 1 = 3，3 的⼆进制是 0011，9 & 3 = 1001 & 0011 = 0001 = 1。

再⽐如说 10 % 4 = 2，10 的⼆进制是 1010，4 - 1 = 3，3 的⼆进制是 0011，10 & 3 = 1010 & 0011 = 0010 = 2。当数组的⻓度不是 2 的 n 次⽅时， hash % length 和 hash & (length - 1) 的结果就不⼀致了。

⽐如说 7 % 3 = 1，7 的⼆进制是 0111，3 - 1 = 2，2 的⼆进制是 0010，7 & 2 = 0111 & 0010 = 0010 = 2。从⼆进制⻆度来看，hash / length = hash / $2^n$ = hash >> n，即把 hash 右移 n 位，此时得到了 hash / $2^n$ 的商。

⽽被移调的部分，则是 hash % $2^n$，也就是余数。

$2^n$ 的⼆进制形式为 1，后⾯跟着 n 个 0，那 $2^n$ - 1 的⼆进制则是 n 个 1。例如 8 = $2^3$，⼆进制是1000，7 = $2^3$ - 1，⼆进制为 0111。

hash % length 的操作是求 hash 除以 $2^n$ 的余数。在⼆进制中，这个操作的结果就是 hash 的⼆进制表示中最低 n 位的值。

因为在 $2^n$ 取模的操作中，⾼于 $2^n$ 表示位的所有数值对结果没有贡献，只有低于这个阈值的部分才决定余数。

⽐如说 26 的⼆进制是 11010，要计算 26 % 8，8 是 $2^3$，所以我们关注的是 26 的⼆进制表示中最低 3 位：11010 的最低 3 位是 010。

010 对应于⼗进制中的 2，26 % 8 的结果是 2。

当执⾏ hash & (length - 1) 时，实际上是保留 hash ⼆进制表示的最低 n 位，其他⾼位都被清零。举个例⼦，hash 为 14，n 为 3，也就是数组⻓度为 $2^3$，也就是 8。

:::info
1110 (hash = 14)

& 0111 (length - 1 = 7)

  ------------------------0110 (结果 = 6)

:::

保留 14 的最低 3 位，⾼位被清零。

从此，两个运算 hash % length 和 hash & (length - 1) 有了完美的闭环。在计算机中，位运算的速度要远⾼于取余运算，因为计算机本质上就是⼆进制嘛。

说说什么是取模运算？

在 Java 中，通常使⽤ % 运算符来表示取余，⽤ Math.floorMod() 来表示取模。

当操作数都是正数的话，取模运算和取余运算的结果是⼀样的；只有操作数出现负数的情况下，结果才会不同。

取模运算的商向负⽆穷靠近；取余运算的商向 0 靠近。这是导致它们两个在处理有负数情况下，结果不同的根本原因。

当数组的⻓度是 2 的 n 次幂时，取模运算/取余运算可以⽤位运算来代替，效率更⾼，毕竟计算机本身只认⼆进制。

⽐如说，7 对 3 取余，和 7 对 3 取模，结果都是 1。因为两者都是基于除法运算的，7 / 3 的商是 2，余数是 1。对于 HashMap 来说，它需要通过 hash % table.length 来确定元素在数组中的位置。

⽐如说，数组⻓度是 3，hash 是 7，那么 7 % 3 的结果就是 1，也就是此时可以把元素放在下标为 1 的位置。当 hash 是 8，8 % 3 的结果就是 2，也就是可以把元素放在下标为 2 的位置。

当 hash 是 9，9 % 3 的结果就是 0，也就是可以把元素放在下标为 0 的位置上。是不是很奇妙，数组的⼤⼩为 3，刚好 3 个位置都利⽤上了。