JAVA基础集合框架【四】HashMap之源码分析tableSizeFor

文章首发于：clawhub.club

---

HashMap中的tableSizeFor方法返回给定目标容量的2次幂。
感觉这里面设计的算法真是精妙，数学真是奇妙的学科。
源码如下：

/**
    * Returns a power of two size for the given target capacity.
    */
   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;
   }

源码中涉及到无符号右移，位或计算。

位或运算符（|）

运算规则：两个数都转为二进制，然后从高位开始比较，两个数只要有一个为1则为1，否则就为0。

比如：129|128.

129转换成二进制就是10000001，128转换成二进制就是10000000。从高位开始比较得到，得到10000001，即129.

无符号右移（>>>）

运算规则：按二进制形式把所有的数字向右移动对应的位数，低位移出(舍弃)，高位补0。只针对负数计算，因为对于正数来说这种运算没有意义。
比如：8 >>> 1
8的二进制：1000 ，右移1位：0100，结果为4
即相当于除2的操作。
###源码分析
第一个例子：

 * 假设cap=8
 * 第一行：n=7     二进制： 0000 0000 0000 0000 0000 0000 0000 0111
 * 第二行：n无符号右移1位： 0000 0000 0000 0000 0000 0000 0000 0011
 *          与上一步n或：  0000 0000 0000 0000 0000 0000 0000 0111
 *        n=7     二进制： 0000 0000 0000 0000 0000 0000 0000 0111
 * 第三行：n无符号右移2位： 0000 0000 0000 0000 0000 0000 0000 0001
 *          与上一步n或： 0000 0000 0000 0000 0000 0000 0000 0111
 *        n=7     二进制： 0000 0000 0000 0000 0000 0000 0000 0111
 * 第四行：n无符号右移4位： 0000 0000 0000 0000 0000 0000 0000 0000
 *          与上一步n或： 0000 0000 0000 0000 0000 0000 0000 0111
 *        n=7     二进制： 0000 0000 0000 0000 0000 0000 0000 0111
 * 第五行：n无符号右移8位： 0000 0000 0000 0000 0000 0000 0000 0000
 *         与上一步n或： 0000 0000 0000 0000 0000 0000 0000 0111
 *        n=7     二进制： 0000 0000 0000 0000 0000 0000 0000 0111
 * 第五行：n无符号右移16位： 0000 0000 0000 0000 0000 0000 0000 0000
 *          与上一步n或： 0000 0000 0000 0000 0000 0000 0000 0111
 *        n=7     二进制： 0000 0000 0000 0000 0000 0000 0000 0101
 * 第六行：n不小于0，也不大于等于1<<30 ,所以 n=n+1=8

第二个例子：

 *
 * 假设           cap=0100 0000 0000 0000 0000 0000 0000 0000   1个1
 * 1:   无符号右移1位：0010 0000 0000 0000 0000 0000 0000 0000
 *            或操作：0110 0000 0000 0000 0000 0000 0000 0000   2个1
 * 2:   无符号右移2位：0001 1000 0000 0000 0000 0000 0000 0000
 *            或操作：0111 1000 0000 0000 0000 0000 0000 0000   4个1
 * 3:   无符号右移4位：0000 0111 1000 0000 0000 0000 0000 0000
 *            或操作：0111 1111 1000 0000 0000 0000 0000 0000   8个1
 * 4:   无符号右移8位：0000 0000 0111 1111 1000 0000 0000 0000
 *            或操作：0111 1111 1111 1111 1000 0000 0000 0000   16个1
 * 4:  无符号右移16位：0000 0000 0000 0000 0111 1111 1111 1111
 *            或操作：0111 1111 1111 1111 1111 1111 1111 1111   31个1
 * 5：        结果+1：1000 0000 0000 0000 0000 0000 0000 0000   即2^30;1 << 30。最大值

总结

发现一个规律：无符号右移再位或的最终结果会将二进制首个1的后面所有位都变成1，最后结果再加1，则向前进位（前提不溢出），结果必是2的幂。