Java源码的二进制骚操作-HashMap构造函数

发表于 | 分类于 | 次

Java 源码的二进制骚操作-HashMap构造函数

1. 问题：指定capacity构造hashmap，为什么经过一连串的移位跟或运算就能得到2的n次幂

2. 目标：为了找到大于等于A的，最小的，2的n次幂

3. 思路：

1
2
3
4
5
6
7
8
9
10
11
比如为了找到大于等于10的，最小的，2的n次幂16
对于一个数A将其转化为一串二进制，如10，16
10 => 00000000 00000000 00000000 00001010
16 => 00000000 00000000 00000000 00010000
只需要将A的，最高位为1的，后面的二进制全部变为1，然后在+1就可以了
如下：
1、找最高位为1的地方：00000000 00000000 00000000 00001（最高位为1）010
2、后面的二进制全部变为1
00000000 00000000 00000000 00001（最高位为1）111
3、再+1
00000000 00000000 00000000 00010000

4. 源码，源码位置：HashMap.tableSizeFor方法

1
2
3
4
5
6
7
8
9
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;
}

5. 分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
源码里面，一上来就减1，然后各种位移运算，接着就返回了。。。
无妨，待我细细讲来
这里假设cap = 10
/**
首先为什么要减1，因为目标是找到大于等于A的，最小的n次幂
如果不减1，而刚好cap参数就是2的n次幂的时候，
那就要引入if/else分支来判断，直接返回
所以-1是为了后面的位移运算能兼容cap参数直接等于2的n次幂，
和非2的n次幂，现在不理解没事，看完后面的再回来看就能理解了，
换个cap参数试一下就知道
**/
1、int n = cap - 1;
/**
cap = 10，n = cap - 1 = 9;
n的二进制为 00000000 00000000 00000000 00001（最高位为1）001
第一次运算无符号右移一位，最高为为1的位像右移动了1位
二进制为 00000000 00000000 00000000 00000100
位移之后与原来的数做或运算，好，为什么是或运算
因为1的所有或运算都等于1
在最高位已经右移了一位的情况下，做或运算一定能得到，最高位连续两位为1
如下：
00000000 00000000 00000000 00001001：原来的数
|：或操作
00000000 00000000 00000000 00000100：右移错开了一位
00000000 00000000 00000000 000011（最高位两位连续为1）00：或的结果
**/
2、  n |= n >>> 1;
/**
在有了最高位两位连续为1的情况下，
再右移两位，做或运算，一定能得到，最高位四位连续为1
**/
3、  n |= n >>> 2;
/**
同理，在有了最高位四位连续为1的情况下，
再右移四位，做或运算，一定能得到，最高位8位连续为1，
这里由于cap=10，所以到了这里右移得到的数据全为0，
与0或操作之后得到的数都等于原来的值，
可以选个大点的cap值就知道了
**/
4、  n |= n >>> 4;
/**
在有了最高位8位连续为1的情况下，
再右移8位，做或运算，一定能得到，最高位16位连续为1
**/
5、  n |= n >>> 8;
/**
在有了最高位16位连续为1的情况下，
再右移16位，做或运算，一定能得到，最高位32位连续为1
**/
6、  n |= n >>> 16;
//最后再做一些兼容运算
7、  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

6. 位操作是最适合计算机的，但读起来真的是反人类啊