Ошибка: параметр 'initialCapacity' метода конструирования ConcurrentHashMap? - PullRequest
Новая
       98

Ошибка: параметр 'initialCapacity' метода конструирования ConcurrentHashMap?

0 голосов
/ 29 апреля 2018

один из методов построения 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

Обновление: Даг Ли прокомментировал ошибку, кажется, он согласен, что это ошибка.

Ответы [ 2 ]

0 голосов
/ 29 апреля 2018

Когда вы говорите (int)(1.0 + (long)initialCapacity / LOAD_FACTOR), это имеет смысл для HashMap, , а не для ConcurrentHashMap (не в том же смысле, как для HashMap).

Для HashMap, емкость - это число buckets до изменения размера, для ConcurrentHashMap это число записей до изменения размера.

Проверить это довольно просто: 

private static <K, V> void debugResize(Map<K, V> map, K key, V value) throws Throwable {

    Field table = map.getClass().getDeclaredField("table");
    AccessibleObject.setAccessible(new Field[] { table }, true);
    Object[] nodes = ((Object[]) table.get(map));

    // first put
    if (nodes == null) {
        map.put(key, value);
        return;
    }

    map.put(key, value);

    Field field = map.getClass().getDeclaredField("table");
    AccessibleObject.setAccessible(new Field[] { field }, true);
    int x = ((Object[]) field.get(map)).length;
    if (nodes.length != x) {
        ++currentResizeCalls;
    }

}


public static void main(String[] args) throws Throwable {

    // replace with new ConcurrentHashMap<>(1024) to see a different result
    Map<Integer, Integer> map = new HashMap<>(1024);

    for (int i = 0; i < 1024; ++i) {
        debugResize(map, i, i);
    }

    System.out.println(currentResizeCalls);

}

Для HashMap изменение размера произошло один раз, для ConcurrentHashMap это не произошло.

И рост 1.5 вовсе не новость, ArrayList имеет ту же стратегию.

Сдвиги, ну, они дешевы (э-э), чем обычная математика; но также потому, что >>> не подписано.

0 голосов
/ 29 апреля 2018

Полагаю, это трюк для оптимизации.

Вы правильно поняли. Приведенный вами конструктор использует коэффициент загрузки по умолчанию 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. Первый комментарий Марин Буххольц согласен с вами:

Да, здесь есть ошибка. Конструктор с одним аргументом эффективно использует коэффициент загрузки 2/3, а не задокументированное значение по умолчанию 3/4…

Я бы сам не считал это ошибкой, если бы вы не рассматривали ее как ошибку, из-за которой вы иногда получаете большую емкость, чем просили. С другой стороны, вы, конечно, правы (в вашем примерном кратком сообщении об ошибке), что есть несоответствие: вы ожидаете, что new ConcurrentHashMap(22) и new ConcurrentHashMap(22, 0.75f, 1) дадут тот же результат, так как последний просто дает задокументированный коэффициент загрузки по умолчанию / плотность стола; но размеры таблиц равны 64 для первого и 32 для второго.

...