java - 漏洞 : parameter 'initialCapacity' of ConcurrentHashMap's construct method?

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

我认为参数表达式是错误的，至少是一个错误。我是不是理解错了什么？

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

更新:Doug Lea 评论了这个错误，似乎他同意这是一个错误。

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 的第一条评论同意你的观点:

Yes, there is a bug here. The one-arg constructor effectively uses a load-factor of 2/3, not the documented default of 3/4…

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