共计 2044 个字符，预计需要花费 6 分钟才能阅读完成。
jdk1.8 中的 hashmap 作了很多改进：红黑树的引入，链表尾插，以及底层数组长度保持 2 的次幂。本文专注于分析 2 次幂设定的原因，且听我慢慢道来……
与“取余”等价的算法
众所周知，hashmap 是数组链表结构：hash 算法用于将 key 散列，经计算分散到数组槽中；而两个 key 算出了同样的值，即产生 hash 冲突时，就需要将槽中的单个节点升级成链表。由于 get 时需要对链表其进行遍历，链表越长检索效率越差。那么，计算出的 key 值落点越平均，hash 冲突的可能性越小。
key 值落点的计算方式为，key 的 hash 值与数组长度作取余操作，记作 key.hascode % array.length。从数学角度考虑，保持 array.length 为质数会使得计算结果更均衡，hashTable 就是这么做的（数组初始值 11）。但 hashmap 中 array.length 偏偏选择了 2 的次幂，是个合数……何故？完全出于性能考虑！先给出结论——当 array.ength 长度是 2 的次幂时，key.hashcode % array.length 等于 key.hashcode & (array.length – 1)。下面重点看下这个结论是怎么得出来的。
举个例子：假如 array.length = 2^4 = 16，二进制 10000。这个数减去 1 的结果是 1111，也就是 array.length -1 = 1111。（下面这段中的数字都是二进制）再假设一个 key 的值为 10011011001（很随意写的一个数），与 1111 做 & 操作，得到的结果是 1001（高位部分 1001101 都舍去了）。而 1001 必然是一个小于 10000 的数，对于一个小于 10000 的数而言，1001 % 10000 得到的就是 1001 自己。那么刚刚舍弃的高位部分 1001101 0000（后面补上了四个 0000）就一定能被 10000 整除吗？答案是肯定的：因为 10011010000 可以拆成 10000000000+10000000+1000000+10000，这几个数都能通过 10000 的 n 次左移得到，也就相当于这几个数都能被 10000 整除。那他们的和，也就是 10011010000，一定也可以被 10000 整除。因此，最终结论就是：10011011001 & (10000 – 1) = 10011011001 & 1111 = 1001 = 10011011001 % 10000
放张简图再唠叨一遍以示总结，加深下印象：
再强调一次：当 array.ength 长度是 2 的次幂时，key.hashcode % array.length 等于 key.hashcode & (array.length – 1)
好，如果你读懂了例子部分，相信你已经基本明白这个结论是站得住脚的（虽然不是纯数学型的讲解）。那么 hashmap 的作者 Doug Lea 大神，为什么如此执着于用 & 操作替换 % 操作呢？因为对于二进制生物计算机来说，& 的效率要高于 %！（与、或、非都可看作二进制基本操作，同或、异或次之，+ – * ÷ % 等都基于前面的）
扩容时方便定位
这还不算完，好处不止这一处。当 hashmap 需要扩容，重新计算链表元素的 hashcode，以进行元素的重新定位时，依然能从“数组 2 次幂”的这个设定中借力！
hashmap 数组扩容时，新数组 length = 原数组 length * 2，沿用前面的例子（array.length = 2^4 = 16，二进制 10000），array.length 乘以 2 , 即二进制左移一位，由 10000 变成 100000。此时需要重新计算数组槽中的元素位置，如果槽中是链表，链表中每个元素都需要重新计算位置（这里不考虑红黑树）。
计算的公式不变，key.hashcode & (array.length – 1)，由于数组的翻倍（10000->100000），导致 array.length – 1 发生了改变（1111->11111）。此时，扩容前原本被舍弃的高位部分的最后 1 位，也将参与计算。
在扩容这个历史的拐点，这一位就显得很特别：如果这个位置是 0，余数计算的将保持结果不变，意味着扩容后此元素还在这个槽中（槽编号没发生改变）；如果这个位置是 1，余数计算结果就变成了原槽索引 + 原 array.length。也就是说，hashmap 扩容的元素迁移过程中，由于数组大小是 2 次幂的巧妙设定，使得只要检查“特殊位”就能确定该元素的最终定位。
给出一个较完整的扩容示意图进行说明：
扩容前
红绿黄三个元素，由各自的 hashcode 取余后都淤积在数组槽 13，组成以链表形式
扩容后
红、绿二星所表示的元素的 hashcode“特殊位”为 0，取余依然定位在槽 13；而黄星表示的元素，hashcode“特殊位”为 1，取余后结果 = 原槽索引 + 原数组大小 = 13 + 16 = 29。（这个结果也和图中黄星的 hashcode 二进制低位值 11101 一致）
总结
对 hashmap 而言，数组长度始终保持 2 次幂有两点好处：
能利用 & 操作代替 % 操作，提升性能
数组扩容时，只需关注“特殊位”就可以从新定位元素
性能，性能，还是性能……
