转载

从HashMap控制Node下标界限的方法来理解掩码的概念

以前一直对 掩码 这个概念十分模糊，这两天在学习 HashMap 的时候，了解到了掩码在工程当中的实际应用，感觉对于 掩码 这个概念的理解加深了。

HashMap中掩码的应用

在 HashMap 中，节点 Node 是存放于一个 Node[] （节点数组）中的，这个数组会根据 loadFactor （装载因子）扩容，并且其 capacity （节点数组长度的上限）总会是上一次扩容前 capacity 的两倍。每个节点都会有一个 hash 值（散列值），而这个 hash 可以认为是比较随意的，最起码不会是正好总能落在 Node[] 的 index 上下界里的，肯定会有超过 Node[] 大小范围的值，如果直接用 hash 当作 index 来在 Node[] 存储，必然会造成 下标越界 ，那么，该如何处理这一情况呢？ HashMap 的作者通过 掩码 来保证了节点不会在节点数组上 下标越界 ：

假设有一个节点hash值为如下（节点的hash是用专门的方法计算出来的，详情请看HashMap源码）
0000000000000000000000001111_1011 //也就是十进制的251，假设当前capacity为16，也就是Node[]的index界限为15,。节点的hash值251已远远超出了15，如果拿这个值作为下标必然会越界

HashMap作者使用capacity - 1作为掩码(mask)，那么掩码就是 16 - 1 = 15，也就是二进制的00000000000000000000000000001111
0000000000000000000000000000_1111 //mask

将Node的hash与掩码做逻辑与操作得到的值换成十进制是11，已经在Node[]的index界限范围内了
0000000000000000000000001111_1011 //hash
&
0000000000000000000000000000_1111 //mask
￬
0000000000000000000000000000_1011 //index

通过分析，我们可以看到，在这里，掩码的作用实际上是掩盖掉了被操作数据超过掩码大小范围的部分，其实可以理解为"管中窥豹"，你的视线只能涉及管口范围内的部分，其他部分视线被掩盖住了；也可以理解成去看一个带着面具(mask)的人脸，你只能看到面具没有遮盖的部分（眼睛），其他部分被掩盖住了
000000000000000000000000[1111]_1011 //造成hash比Node[]的index界限大的原因是因为hash有方括号标示出来的这四个1（也就是比掩码最高一位1还要靠前的1），所以要让hash能够当作index来用的话，就需要消除掉这四个1
[0000000000000000000000000000]_1111 //掩码前面的这些0相当于面具的遮盖部分，后面的4个1就相当于面具中能够露出眼睛的部分

掩码中的0位会将被操作数对应位清零（因为0 & 0 = 0 并且 0 & 1 = 0）也就是将被操作数对应位"掩盖"了
0000000000000000000000001111
&
0000000000000000000000000000
￬
0000000000000000000000000000

最终能看到的"面具露出来的部分"就是index（为二进制11，小于Node[]的index界限15）
0000000000000000000000000000_1011

总结

本次通过学习 HashMap 中控制 Node 下标界限的方法，间接地加深了对于 掩码 概念的理解，就像其英文”mask”原本的意思一样，掩码其实就是被操作数的”面具”。

原文 https://since1986.github.io/blog/9f829116.html

正文到此结束

所属分类：编程技术 Java

本文标签： map ask src https 总结 git HTML node CTO HashMap 源码 GitHub IO 数据 1111 UI http
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二