【源】终于明白JDK8 HashMap底层数组长度,取值2次幂的原因

39次阅读

共计 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 次幂有两点好处:

能利用 & 操作代替 % 操作,提升性能
数组扩容时,只需关注“特殊位”就可以从新定位元素

性能,性能,还是性能……

正文完
 0