作者:凤凰花开清风自来_406 | 来源:互联网 | 2023-01-28 12:13
源码如下:
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的幂次方整数,如给定9,返回2的4次方16。
这个算法的大致原理:
假定cap也就是给定数的的形式为00..01XXXXXXX,(X代表可为0也可为1,X前面的1为从最高位开始第一个为1的那一位)
第一步: n |= n >>> 1; 也就是n变为n与n右移一位之后异或后的值,即
n: 00..01XXXXXXX
n>>>1: 00..001XXXXXX
新n: 00..011XXXXXX
第二步: n |= n >>> 2; 也就是n变成n与n右移两位之后异或的值,即
n: 00..011XXXXXX
n>>>2: 00..00011XXXX
新n: 00..01111XXXX
后面相类似。
这个算法不断地把第一个1后面的位全部变成1。本例由00..01XXXXXXX —> 00..011111111,最后再返回n+1(2的幂次方);
与此类似的方法:
while (capacity capacity <<= 1;
}