冰山一角之tableSizeFor方法从哪里来?

看过 Java8 版本 HashMap 源码的都知道, 里面有一段神奇的代码tableSizeFor, 用来计算内部table的大小.

1TableSizeFor

算法代码

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-43的初始容量变化, 内部table长度变化表示出来, 是这样的.

算法大意

相信对着图很容易能看出来, 这段代码的意思是n的对数,向上取整后的2次方.写成公式是, .

自我实现

大于上限的,我们暂时不处理.自己写一个版本, 差不多是这样的.

static int tableSize4(int cap) {
  if (cap == 0) return 1;
  double log = Math.log10(cap) / Math.log10(2);
  double ceil = Math.ceil(log);
  return (int) Math.pow(2, ceil);
}

不信的可以试试看, 结果和原始版本的tableSizeFor是一样的.

JDK 里又是用一段神奇的代码,高效实现了我们都会的事.

那么这段代码是从哪里来的呢?

2TableSizeFor 寻踪

首先还是翻看源码的历史记录,HashMap 是 Java2 版本引入的. 我们直接看 Java2 版本的 HashMap 如何初始化 table 就好.

Java2 版本的初始化

  if (initialCapacity == 0)
  initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
threshold = (int) (initialCapacity * loadFactor);

并没有这个计算操作, 惊喜不惊喜,意外不意外? 当时的初始容量默认值,甚至是11. 默认负载因子 0.75 倒是从那时候就定下来了.

既然找不到, 作为一名程序员, 当然, 下一个搜索版本是

Java5 版本的初始化

int capacity = 1;
while (capacity < initialCapacity)
    capacity <<= 1;

很意外, 这个版本其实就已经开始有这个功能了. 和上面的实现只是写法不太一样. 继续往前搜索, Java4 也是这个版本. 甚至, 熟悉的初始容量16,也是 Java4 版本出现的,一直到 7 这个写法都没什么变化.

Java8 版本的出现时间

要找到 Java8 的版本, 只能往后了. 最后发现是 2013 年 9 月 4 日Paul Sandoz提交的.时间线甚至和我们上一次说过的, 《Java8 的 HashMap 为什么使用红黑树》搅和在了一起。

3暗流涌动

你以为, Java8 的版本, 是改了 Java4 的版本出现的吗?

当然不是. 他替换掉的是2013年7月31 的版本.

 private static int roundUpToPowerOf2(int number) {
  return number >= MAXIMUM_CAPACITY
      ? MAXIMUM_CAPACITY
      : (number > 1) ?
      Integer.highestOneBit(
          (number - 1) << 1) : 1;
}

而这个版本的最早出现, 是2013年4月11. Java4 版本的实现,在这一天光荣退役.

   private static int roundUpToPowerOf2(int number) {
  // assert number >= 0 : "number must be non-negative";
  int rounded = number >= MAXIMUM_CAPACITY
      ? MAXIMUM_CAPACITY
      : (rounded = Integer.highestOneBit(number)) != 0
      ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
      : 1;

  return rounded;
}

有没有看到一位熟悉的老朋友? Integer.bitCount, 我们好像开始转圈圈了. 别着急,圈还在后面. 听我慢慢道来.

小结

Java8 将生未生, 世界风起云涌. 短短几个月, Java 代码数次变异, 一次比一次难以看懂. 最后尘埃落定, 得到了 Java8 里的版本. 我们再来看他一眼.

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

4Java8 版本, 再觅仙踪

我们知道 Java8 出现了这个版本了, 但是只知道了时间, 仍然不知道这个实现的源头啊?

别着急. 回忆一下, 上次研究过的. Java8 里 HashMap 的实现是从哪里来的?

ConcurrentHashMap 抄的啊.

果不其然, 打开 ConcurrentHashMap实现, 同样发现了这段代码.

  /**
 * See Hackers Delight, sec 3.2
 */
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;
}

更让人意外的是, 这段代码头上甚至写了个注释. Hackers Delight 3.2.

是他, 又是他. 黑客朋友的小确幸《Hacker’s Delight》. 我们又转回这本书了.昨天的Integer.bitCount就是出自这本书的实现. 一个圈子过后, 竟然挨着了.

5HD 3.2

那就不客气了, 直接看书吧.

这算法, 和我们一开始总结的, 还是差不多的嘛,😄.

在这个公式里, 其实求乘方并不难. 1 左移几位就是 2 的几次方,公式其实可以写成 ,这个位运算非常的快.

怎么求?才是核心问题. 那么这个怎么求呢?

其实这个也不难. 举数字为例:

写成二进制是00000000000000000000000000000000, 前面 32 个 0
写成二进制是00000000000000000000000000000001, 前面 31 个 0
写成二进制是00000000000000000000000000000010,前面 30 个 0
写成二进制是00000000000000000000000000000011,前面 30 个 0
写成二进制是00000000000000000000000000000100,前面 29 个 0
写成二进制是00000000000000000000000000000101,前面 29 个 0

我们把一个 bit 串第一个不为 0 的位前面的 0 叫做前导0. 其实等于32-(n-1)前导0的个数.

用上Integer里现成的numberOfLeadingZeros方法, 立刻就可以把tableSizeFor简化成这样.

1 << (32 - Integer.numberOfLeadingZeros(cap - 1));

如果巧妙利用<<和>>>的循环特性, 也可以把这个写法改为

 -1 >>> Integer.numberOfLeadingZeros(cap - 1);

可以考虑牢牢记住, 因为这个是 2018 年以后的标准实现写法, Java8 的神奇实现已经消失了.

6哀悼 Java8 版本tableSizeFor

因为 Java8 版本的tableSizeFor写法已经死了. 所以, 我们在这里分析一下这个写法,来作为最后的纪念.

书里关于这段说的很清楚,当硬件支持前导 0 数量指令时候, 直接用指令最快. 如果没有, 可以用一个慢一点的方法来做.

公式也直接就给出来了

“
Least power
of 2 greater than or equal to x.

    unsigned clp2(unsigned x) {
      x = x - 1;
        x = x | (x >> 1);
        x = x | (x >> 2);
        x = x | (x >> 4);
        x = x | (x >> 8);
        x = x | (x >> 16);
        return x + 1;
} ”

摘录来自:
By Henry
S.Warren ,.“ Hacker 's Delight。”