162°

Java集合--tableSizeFor

在看 HashMap 源码的时候有这么一段代码

private static final int MAXIMUM_CAPACITY = 1 << 30;

private static final int tableSizeFor(int c) {
    int n = c - 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;
}

第一眼看上去完全看不懂,这几个右移按位或是什么意思

运行一个例子看看

private static final int MAXIMUM_CAPACITY = 1 << 30;

private static int tableSizeFor(int c) {
    int n = c - 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;
}

public static void main(String[] args) {
    System.out.println(tableSizeFor(6));
    System.out.println(tableSizeFor(7));
    System.out.println(tableSizeFor(10));
    System.out.println(tableSizeFor(15));
    System.out.println(tableSizeFor(18));
}

// 输出
8
8
16
16
32

输入6,7 都是输出8

输入10, 15 输出16

输入18 输出32

输出的都是2的指数幂,其实这个方法是用于找到大于等于输入参数的的最小的2的指数幂。为什么需要这样的方法,因为hashmap的容量大小都是2的指数幂。

以输入22为例子, n = c - 1, n 为 21

每一次右移之后与上一次的结果做按位或操作(只要有一个位是1,结果就是1),通过几次操作之后将原本二进制最高位为1的后面几位全部至1,最后再加1,得到一个2的指数幂。

至于为什么一开始要执行 n = c - 1; 这是为了防止 c 已经是2的幂,如果 c 已经是2的幂, 又没有执行这个减1操作,则执行完后面的几条无符号右移操作之后,返回的结果将是这个c的2倍。

 

 

本文由【gaob2001】发布于开源中国,原文链接:https://my.oschina.net/u/232911/blog/2872356

全部评论: 0

    我有话说: