Geek asks and answers

Parallel complexity of hashmap () method

I am wondering if the method size()called in ConcurrentHashMaphas the same complexity as the method size()for a regular HashMap.

+3
source share
5 answers

This is not true. In my version, the JDK HashMap.size()has difficulty O(1), whereas ConcurrentHashMap.size()at best, you have to iterate over segments. In the worst case scenario, it blocks all segments, which can be quite an expensive operation in a multi-threaded scenario.

Of course, this is rather another question. The answer largely depends on how many threads access the map, and what exactly they do.

+5
source

size() HashMap O(1), . size() ConcurrentHashMap, , ( > O (1))

(openjdk-6)

+5

ConcurrentHashMap.size() JDK 8 , LongAdder.

, ConcurrentHashMap.size() ( "O (1)" nerd), HashMap.size() . ? . JDK 7, , Java 1.7 Java 1.8.

+3

size() ConcurrentHashMap , , 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;
}
0

, size() - , , . , - , , , , , , .

size() , .

0

More articles:


All Articles