读HashMap源码之tableSizeFor

Dear 丶 2023-08-17 16:39 67阅读 0赞

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

源码的解释是：返回一个指定容量大小的2次幂，人话就是说返回比给定参数大的、最接近的2的n次方那个数  
  
  
即如果传入10，返回2^4 = 16、传入18，返回2^5 = 32，传入34，应该返回2^6 = 64  
测试一下

public static void main(String[] args) {
            System.out.println("传入10----"+tableSizeFor(10));
            System.out.println("传入18----"+tableSizeFor(18));
            System.out.println("传入34----"+tableSizeFor(34));
        }
    
        static final int tableSizeFor(int cap) {
            Integer MAXIMUM_CAPACITY = 1 << 30;
            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;
        }

结果：  
![在这里插入图片描述][20190929102353721.png]  
怎么来的呢？先认识一下两个运算符`|`和`>>>`  
`|`不用多说，二进制或，两个都为0才为0  
`>>>`，无符号右移  
  
无符号右移，忽略符号位，空位都以0补齐

10进制转二进制的时候，因为二进制数一般分8位、 16位、32位以及64位（java是四个字节32位） 表示一个十进制数，所以在转换过程中，最高位会补零  
来动手算一个，传入10

int n = cap - 1;

后n = 9

n |= n >>> 1;

先算`n >>> 1`，再算`n= n|前面的结果`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70]

同理，在计算\`\`\`n |= n >>> 2;\`\`，此时n已经等于13了  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70 1]

同理，在计算\`\`\`n |= n >>> 4;\`\`，此时n已经等于15了

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70 2]  
到此可以看出，它的每一次运算，都是在将有0的位转换成1，直到所有位都为1为止

最后返回的时候`return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;`如果比最大值小，就返回运算结果+1，又正好将所有的1转换成了0，且进了一位，刚好是2^x次方

采用这样的算法，精妙之处就在于二进制运算更快

[20190929102353721.png]: /images/20230809/537ddcc3842349d086d675b65afad336.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70]: /images/20230809/d3a30c0fcc9e4f189dc6177294ad90b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70 1]: /images/20230809/0f183e7b3955409293e44fac4c3a5b1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70 2]: /images/20230809/5ae041b9a93d46a5897816be47455bb9.png