Bug:ConcurrentHashMap的构造方法的参数'initialCapacity'？

Question

java.util.concurrent.ConcurrentHashMap的构造方法之一:

public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }

方法'tableSizeFor(...)'的参数是什么意思？

initialCapacity + (initialCapacity >>> 1) + 1

我认为参数应该是这样的:

(int)(1.0 + (long)initialCapacity / LOAD_FACTOR)

要不就:

initialCapacity

我认为参数表达式是错误的,至少是一个bug.Did我误解了什么？

我向OpenJDK发送了一个错误报告,似乎他们正式确认它很可能是一个bug:https://bugs.openjdk.java.net/browse/JDK-8202422

更新:Doug Lea评论了这个bug,似乎他同意这是一个bug.

Answer 1

我强烈认为这是一个优化技巧.

你是正确的想法.您引用的构造函数使用默认的加载因子0.75,因此要容initialCapacity纳哈希表大小至少需要的元素

initialCapacity / 0.75

(与乘以1.3333333333大致相同).然而,浮点除法很昂贵(稍微有点,不错).而且我们还需要舍入到整数.我想整数除法已经有所帮助了

(initialCapacity * 4 + 2) / 3

(这+ 2是为了确保结果被四舍五入; * 4应该是便宜的,因为它可以实现为左移).实施者做得更好:轮班比分部便宜很多.

initialCapacity + (initialCapacity >>> 1) + 1

这实际上是乘以1.5,所以给我们的结果通常会比需要的更大,但速度很快.这+ 1是为了弥补"乘法"向下舍入的事实.

细节:>>>是无符号右移,将零填充到最左边的位置.已经知道这initialCapacity是非负的,这给出了与除以2相同的结果,忽略了余数.

编辑:我可以将这些tableSizeFor轮次加到2的幂,所以即使第一次计算得到的结果略大于所需的结果,大多数情况下2的相同功率也是最终结果.例如,如果你要求10个元素的容量(为了保持计算简单),表格大小14就足够了,公式产生16个.但是14会被四舍五入到2的幂,所以我们得到16个,所以最后没有区别.如果你要求12个元素的空间,16号仍然足够,但公式得到19,然后向上舍入到32.这是更不寻常的情况.

进一步编辑:感谢您提交的评论中的信息作为JDK错误并提供链接:https://bugs.openjdk.java.net/browse/JDK-8202422.Marin Buchholz的第一条评论同意你的意见:

是的,这里有一个错误.one-arg构造函数有效地使用2/3的加载因子,而不是记录的默认值3/4 ...

我自己不会认为这是一个错误,除非你认为它是一个你偶尔会获得比你要求的更大容量的错误.另一方面,你是对的,当然(在你的示例性简洁错误报告中)存在不一致性:你会期望new ConcurrentHashMap(22)并new ConcurrentHashMap(22, 0.75f, 1)给出相同的结果,因为后者只给出了记录的默认加载因子/表密度; 但你得到的桌子大小是64,前者是32,后者是32.