HashMap之tableSizeFor

发表于 分类于

无用知识点系列二：HashMap之tableSizeFor方法解析。

tableSizeFor方法

1
2
3
4
5
6
7
8
9
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;
}

在 hashMap 和 ConcurrentHashMap 中，对于有参构造的时候，用通过 tableSizeFor 方法定位离参数最近的 2 次幂容量。现在我们来解析一下这个方法。

tableSizeFor方法解析

  1. n = c - 1；按下不表
  2. n |= n >>> 1；将 n 右移一位之后再进行或运算。首先我们知道或运算有 1 则为 1。那么这次运算之后，这个数最高位为 1，因为与自身右移 1 位再或运算，则最高位和其下一位也为 1。
  3. n |= n >>> 2；这次运算原理如上，可以得知能让最前面两个 1 与右移后的自己运算，能保证从最高位算起的前 4 位为 1。
  4. … 一路套娃到 16 之后，因为 int 最高 32 位，可以保证从最高位为 1 的数之后一定全为 1。
  5. return n + 1；由上可得，在从 n 最高位为 1 的数之后都是 1，加 1 之后一定是进位后的 2^n。

举个例子 有个数是 1XXXXXXX（范围为：128~255），在第一次过后这个数为 11XXXXXX，第二次过后则为 1111XXXX， 第三次为11111111。之后几次保持不变。此时 n + 1 则为 100000000 即 2^8 = 256。所以不管 1 后面是什么，运算后一定是在其最高位之前一位的 2 的次方。

为什么要第一步 n-1

接下来我们要看看，为什么要在之前做一步 n - 1 的运算，这是因为设计者考虑到参数刚好为 2^n，这时候就不需要再去找 2^(n+1)，而是直接将其作为当前容量，否则我们在传入 128 的时候，因为没有减 1，经过一系列右移或运算之后，得到的结果为 256，这显然与我们的目标不一致了，因此设计者才将其减 1 后运算。保证参数刚好为 2^n 之时不出错。

作者的话

今天的风儿甚是喧嚣，可惜已没人听得懂我这句话什么意思。