Сложность метода Concurrent hashmap size()

Мне интересно, имеет ли метод size(), вызываемый на ConcurrentHashMap, ту же сложность, что и метод size() для обычной хэш-карты.

5 3
concurrency concurrenthashmap java.util.concurrent

5 ответов:

Это не так. в моей версии JDK, HashMap.size() имеет O(1) сложность, тогда как ConcurrentHashMap.size() в лучшем случае приходится перебирать отрезки. В худшем случае он заблокирует все сегменты, что может быть довольно дорогостоящей операцией в многопоточном сценарии.

Конечно, что быстрее - это совсем другой вопрос. Ответ во многом зависит от того, сколько потоков получают доступ к карте и что именно они делают.

5

Новая реализация ConcurrentHashMap.size () в JDK 8 использует классный алгоритм, который они вроде как копируют, вставленные из LongAdder.

В сущности, сложность ConcurrentHashMap.size() почти постоянна ("O(1)" на языке ботаников), а затраты реального времени по сравнению с HashMap.size() ничтожны. Не веришь мне? Откройте Мой базовый тестовый проект и запустите его самостоятельно. У меня нет JDK 7, установленного на моей текущей машине, было бы здорово получить обратную связь по стоимости времени с Java 1.7 по сравнению с Java 1.8.

6

Сложность size() на HashMap равна O(1), поскольку размер хранится в поле. Если мы посмотрим на реализацию size() на ConcurrentHashMap, то увидим, что она больше (>O(1))

Ссылка (openjdk-6)

5

Сложность метода 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