庆祝拿offer，立个flag，同时记录HashMap源码解析

约定不等于承诺〃 2022-05-19 13:29 262阅读 0赞

不知道怎么描述现在的心情，昨天面试了一家很想去的公司，今天拿到offer，感谢老天突然这么垂青，以前的努力都没有白费，写的博客，买的课，一定要抓住这个机会好好努力。

第一轮面试的时候问了很多问题没有回答出来，例如：Spring的bean是如何加载的，java类是如何被加载的，mysql的事务传播行为有哪些等等，觉得自己的基础太差了，现在可能有很多开发跟我一样吧，新技术层出不穷，我们的眼睛盯着微服务，盯着Docker，盯着K8S，盯着ServiceMesh，但是这些技术在小公司真的能用上吗，在我们自己手头真的能用上吗，忽略了最基础的java jvm，忘记了大学学过了计算机网络，操作系统，数据结构和算法，一次面试也让我茅塞顿开，以后要更多的着重于基础的东西，不要好高骛远。

flag是什么呢，以后开始看java关键类型的源码，重新看一遍《深入理解JAVA虚拟机》，重新看一遍大学教材《计算机网络》《计算机操作系统》《数据结构》，每周至少更新一篇自己的收获。

不在速度快，贵在坚持

今天是HashMap！

> 此处去看了代码一个小时………

妈呀直接被构造函数里的`tableSizeFor`方法就难住了，看了好久为什么会有这么巧妙的方法啊

static final int tableSizeFor(int cap) {
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

这个方法的目的是为了返回与参数`cap`相等或者比它大的最小的2的整数次幂，看看它怎么实现的。

都知道二进制里面2的整数次幂一定是1后面跟n个0，例如10，1000，10000这种，而不管我们传入的参数是多少，都把它转成二进制之后，比它大的最小的2的整数次幂是什么呢？

如果参数转成二进制是n位，那么最小的二进制就是1后面加n个0

有一种例外情况是，参数转成二进制本身就是1后面n个0，也就是说参数本身就是2的整数次幂，那么我们最后需要的值就是它本身了

回过头来看这个方法，先忽略方法的第一行，从第二行开始：  
`>>>`是无符号右移，`>>`是有符号右移，有啥区别呢，有符号右移就是正数左边补0，负数左边补1，也就是不管是正数还是负数数字都在变小的。  
而无符号位移可以理解成咱不管数字前面的正负号，不管正数负数，都是左边补0。

回头再看代码: `n |= n >>> 1;`  
首先n本身第一位肯定是1吧，n右移1位之后第一位就变0了，再跟n本身做个`或`，前两位肯定都是1了

> 备注：n的二进制位数肯定永远和一开始是一致的，比如一开始是100，再怎么做位移最大就是111，所以下面提到1111之类的就不赘述了，是不考虑n的初始位数的，只是为了说明道理

这个时候再把n右移两位：`n |= n >>> 2;`  
右移两位之后前面四位是0011，再与目前是11开头的n做个`或`，现在n是1111开头了吧  
后面的4，8，16依次类推就行了  
4搞完之后n变成8个1开头，8之后是16个1开头，16之后是32个1开头

由于这个值允许的最大值是方法最后一行中出现的`MAXIMUM_CAPACITY`，它的值是固定的`1<<30`，也就是2的29次方，所以有32个1已经足够让n变成最大值，不用再继续了

所以这几行代码是做什么的呢，就是为了获得参数二进制位数的1  
参数是1000，就把它变成1111;  
参数是110001，就把它变成111111;  
依次类推

得到这个值之后想获得2的整数次幂只需要+1就可以啦  
1111 + 1 = 10000  
111111 + 1 = 1000000

这里细心地话就会发现一个问题了，我本来1000就是2的整数次幂，结果给变成了10000，这也就是为什么会出现第一行代码的原因了，先无脑减1，再进行这一系列骚操作，就不会出现这种尴尬的情况了