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 之时不出错。

作者的话

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