将初始化容量转化大于或等于最接近输入参数的2的整数次幂的数

在jdk1.8的HashMap源码中看到的这个算法,感觉写的非常巧妙

tableSizeFor(),将初始化容量转化大于或等于最接近输入参数的2的整数次幂的数:

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;
}

|是或运算符,比如说0100 | 0011 = 0111>>>是无符号右移,忽略符号位,空位都以0补齐,比如说0100 >>> 2 = 0001,现在来说一下这么做的目的:

首先>>>|的操作的目的就是把n从最高位的1以下都填充为1,以010011为例,010011 >>> 1 = 001001,然后001001 | 010011 = 011011,然后再把011011无符号右移两位:011011 >>> 2 = 000110,然后000110 | 011011 = 011111,后面的4、8、16计算过程就都省去了,int类型为32位,所以计算到16就全部结束了,最终得到的就是最高位及其以下的都为1,这样就能保证得到的结果肯定大于或等于原来的n且为奇数,最后再加上1,那么肯定是:大于且最接近输入值的2的整数次幂的数

​ 那么为什么要先cap - 1呢,我们可以先思考以下,如果传进来的本身就是2的整数幂次,比如说01000,10进制是8,那么如果不减,得到的结果就是16,显然不对。所以先减1的目的是cap如果恰好是2的整数次幂,那么返回的也是本身。

合起来得到这个tableSizeFor()方法的目的:返回大于或等于最接近输入参数的2的整数次幂的数。另外,笔者特意回去看了JDK1.7的源码,发现1.7用的是roundUpToPowerOf2()方法,里面用到里了>>以及减操作,性能上来说肯定还1.8的高。

自己用的话可以用这个:

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 + 1;
}
原文地址:https://www.cnblogs.com/tiantian152/p/14490861.html