3

我想知道size()调用的方法是否与通常的 HashMap 方法ConcurrentHashMap具有相同的复杂性。size()

4

5 回答 5

9

JDK 8中ConcurrentHashMap.size()的新实现使用了一种很酷的算法，他们从LongAdder复制粘贴。

实际上，复杂度ConcurrentHashMap.size()几乎是恒定的（书呆子语言中的“O(1)”），并且与之相比的实时成本HashMap.size()可以忽略不计。不相信我？打开我的基本测试项目并自己运行。我当前的机器上没有安装 JDK 7，与 Java 1.8 相比，获得有关 Java 1.7 时间成本的反馈会很酷。

于 2014-04-10T18:42:08.773 回答
5

size()on的复杂性HashMap是O(1)，因为大小存储在一个字段中。如果我们查看size()on的实现ConcurrentHashMap，我们会发现它更大（> O(1)）

参考（openjdk-6）

于 2012-05-25T12:48:26.700 回答
4

它不是。在我的 JDK 版本中，HashMap.size()它具有O(1)复杂性，而ConcurrentHashMap.size() 在最好的情况下必须遍历这些段。在最坏的情况下，它将锁定所有段，这在多线程场景中可能是一项非常昂贵的操作。

当然，哪个更快是完全不同的问题。答案很大程度上取决于有多少线程正在访问映射，以及它们到底在做什么。

于 2012-05-25T12:48:21.393 回答
0

ConcurrentHashMap 中 size() 方法的复杂性本质上是一个 O(N) 操作（主要随段数而变化），正如您在源代码中看到的那样。HashMap 是一个 O(1) 操作。

/**
 * Returns the number of key-value mappings in this map.  If the
 * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
 * <tt>Integer.MAX_VALUE</tt>.
 *
 * @return the number of key-value mappings in this map
 */
public int size() {
    final Segment<K,V>[] segments = this.segments;
    long sum = 0;
    long check = 0;
    int[] mc = new int[segments.length];
    // Try a few times to get accurate count. On failure due to
    // continuous async changes in table, resort to locking.
    for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
        check = 0;
        sum = 0;
        int mcsum = 0;
        for (int i = 0; i < segments.length; ++i) {
            sum += segments[i].count;
            mcsum += mc[i] = segments[i].modCount;
        }
        if (mcsum != 0) {
            for (int i = 0; i < segments.length; ++i) {
                check += segments[i].count;
                if (mc[i] != segments[i].modCount) {
                    check = -1; // force retry
                    break;
                }
            }
        }
        if (check == sum)
            break;
    }
    if (check != sum) { // Resort to locking all segments
        sum = 0;
        for (int i = 0; i < segments.length; ++i)
            segments[i].lock();
        for (int i = 0; i < segments.length; ++i)
            sum += segments[i].count;
        for (int i = 0; i < segments.length; ++i)
            segments[i].unlock();
    }
    if (sum > Integer.MAX_VALUE)
        return Integer.MAX_VALUE;
    else
        return (int)sum;
}
于 2012-05-25T12:50:14.513 回答
0

这是一个无关紧要的问题，因为在并发可变结构上调用 size() 本质上是毫无意义的事情。它只会告诉你大小是多少，除了记录它之外，你实际上无法对这些信息做任何事情。

如果您尝试使用 size() 而不锁定结构，您将遇到竞争条件。

于 2012-05-26T10:50:50.850 回答