ConcurrentHashMap size()性能

Question

什么是运行时间表现ConcurrentHashMap size()？查看源代码(这是Java7)我无法弄明白,我没有在文档中看到它.

这是代码

 public int size() {
        // Try a few times to get accurate count. On failure due to
        // continuous async changes in table, resort to locking.
        final Segment<K,V>[] segments = this.segments;
        int size;
        boolean overflow; // true if size overflows 32 bits
        long sum;         // sum of modCounts
        long last = 0L;   // previous sum
        int retries = -1; // first iteration isn't retry
        try {
            for (;;) {
                if (retries++ == RETRIES_BEFORE_LOCK) {
                    for (int j = 0; j < segments.length; ++j)
                        ensureSegment(j).lock(); // force creation
                }
                sum = 0L;
                size = 0;
                overflow = false;
                for (int j = 0; j < segments.length; ++j) {
                    Segment<K,V> seg = segmentAt(segments, j);
                    if (seg != null) {
                        sum += seg.modCount;
                        int c = seg.count;
                        if (c < 0 || (size += c) < 0)
                            overflow = true;
                    }
                }
                if (sum == last)
                    break;
                last = sum;
            }
        } finally {
            if (retries > RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j)
                    segmentAt(segments, j).unlock();
            }
        }
        return overflow ? Integer.MAX_VALUE : size;
    }

Answer 1

好吧,我对代码的解读是复杂性O(1).

首先,如果您查看其余代码,您将看到这完全segments.length取决于创建地图时的值.重新分配地图时,它不会更改.concurrencyLevel

因此,在非竞争情况下,很容易看到for(;;)循环内的东西将被执行两次,并且内部外观的迭代次数是segments.length; 即这是O(1)整体的.

在竞争情况下,性能会变差,因为for(;;)循环可能会多次执行.但我仍然认为复杂性O(1)与地图大小有关N.

但话说size()回来,它看起来像是一个昂贵的操作,如果争用足以使算法不得不依赖锁定整个地图,那将是一个并发瓶颈; 即retries达到RETRIES_BEFORE_LOCK(我看过的版本中有2个).