HashMap перефразирует/изменяет размер емкости

У HashMap есть такая фраза из него:

Если начальная емкость больше максимального количества записей, деленная на коэффициент нагрузки, никаких операций перефразирования никогда не произойдет.

Обратите внимание на то, как документация говорит о переименовании, а не изменении размера - даже если переименование произойдет только тогда, когда будет изменен размер; то есть когда внутренний размер ведер становится вдвое большим.

И, конечно же, HashMap предоставляет такой конструктор, где мы могли бы определить эту начальную емкость.

Создает пустой HashMap с указанной начальной мощностью и коэффициентом загрузки по умолчанию (0.75).

Хорошо, кажется достаточно простым:

// these are NOT chosen randomly...    
List<String> list = List.of("DFHXR", "YSXFJ", "TUDDY", 
          "AXVUH", "RUTWZ", "DEDUC", "WFCVW", "ZETCU", "GCVUR");

int maxNumberOfEntries = list.size(); // 9
double loadFactor = 0.75;

int capacity = (int) (maxNumberOfEntries / loadFactor + 1); // 13

Таким образом, емкость составляет 13 (внутренне это 16 - следующая мощность двух), таким образом мы гарантируем, что часть документации не будет содержать никаких повторов. Хорошо давайте протестировать это, но сначала введем метод, который войдет в HashMap и посмотрит на значения:

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

    Field table = map.getClass().getDeclaredField("table");
    table.setAccessible(true);
    Object[] nodes = ((Object[]) table.get(map));

    // first put
    if (nodes == null) {
        // not incrementing currentResizeCalls because
        // of lazy init; or the first call to resize is NOT actually a "resize"
        map.put(key, value);
        return;
    }

    int previous = nodes.length;
    map.put(key, value);
    int current = ((Object[]) table.get(map)).length;

    if (previous != current) {
        ++HashMapResize.currentResizeCalls;
        System.out.println(nodes.length + "   " + current);
    }
}

А теперь давайте протестируем это:

static int currentResizeCalls = 0;

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

    List<String> list = List.of("DFHXR", "YSXFJ", "TUDDY",
            "AXVUH", "RUTWZ", "DEDUC", "WFCVW", "ZETCU", "GCVUR");
    int maxNumberOfEntries = list.size(); // 9
    double loadFactor = 0.75;
    int capacity = (int) (maxNumberOfEntries / loadFactor + 1);

    Map<String, String> map = new HashMap<>(capacity);

    list.forEach(x -> {
        try {
            HashMapResize.debugResize(map, x, x);
        } catch (Throwable throwable) {
            throwable.printStackTrace();
        }
    });

    System.out.println(HashMapResize.currentResizeCalls);

}

Ну, resize было вызвано и, следовательно, записи, в которых повторялось, а не документация.

Как сказано, ключи не были выбраны случайным образом. Они были настроены так, чтобы они static final int TREEIFY_THRESHOLD = 8; свойство - когда ковш преобразуется в дерево. Ну не очень, так как нам нужно также MIN_TREEIFY_CAPACITY = 64 для появления дерева; пока не произойдет resize, или ковш удвоится по размеру; таким образом происходит перестановка записей.

Я могу только намекнуть на то, почему в этом предложении неверна документация HashMap, поскольку до java-8 ведро не было преобразовано в Дерево; таким образом, свойство будет сохраняться, начиная с java-8 и далее, что не соответствует действительности. Поскольку я не уверен в этом, я не добавляю это в качестве ответа.

Ответы

Ответ 1

Строка из документации,

Если начальная емкость больше максимального количества записей, деленная на коэффициент нагрузки, никаких операций перефразирования никогда не произойдет.

датируется до того, как в JDK 8 (JEP 180) была добавлена реализация tree-bin. Вы можете увидеть этот текст в документации JDK 1.6 HashMap. Фактически, этот текст датируется полностью в JDK 1.2, когда была введена структура коллекций (включая HashMap). Вы можете найти неофициальные версии документов JDK 1.2 по всему Интернету или загрузить версию из архивов, если хотите сами убедиться.

Я считаю, что эта документация была правильной до тех пор, пока не была добавлена реализация tree-bin. Однако, как вы уже заметили, теперь есть случаи, когда это неверно. Политика заключается не только в том, что изменение размера может происходить, если количество записей, деленное на коэффициент загрузки, превышает емкость (на самом деле, длина таблицы). Как вы отметили, изменения размера могут также возникать, если количество записей в одном ведре превышает TREEIFY_THRESHOLD (в настоящее время 8), но длина таблицы меньше MIN_TREEIFY_CAPACITY (в настоящее время 64).

Вы можете увидеть это решение в treeifyBin() HashMap.

    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {

Эта точка в коде достигается, когда в одном ведре содержится больше записей TREEIFY_THRESHOLD. Если размер таблицы не превышает MIN_TREEIFY_CAPACITY, этот бит обрабатывается деревом; в противном случае таблица просто изменяется.

Обратите внимание, что это может оставить ячейки с большим количеством записей, чем TREEIFY_THRESHOLD при небольших размерах таблицы. Это непросто продемонстрировать. Во-первых, некоторый отражающий код HashMap-dumping:

// run with --add-opens java.base/java.util=ALL-UNNAMED

static Class<?> classNode;
static Class<?> classTreeNode;
static Field fieldNodeNext;
static Field fieldHashMapTable;

static void init() throws ReflectiveOperationException {
    classNode = Class.forName("java.util.HashMap$Node");
    classTreeNode = Class.forName("java.util.HashMap$TreeNode");
    fieldNodeNext = classNode.getDeclaredField("next");
    fieldNodeNext.setAccessible(true);
    fieldHashMapTable = HashMap.class.getDeclaredField("table");
    fieldHashMapTable.setAccessible(true);
}

static void dumpMap(HashMap<?, ?> map) throws ReflectiveOperationException {
    Object[] table = (Object[])fieldHashMapTable.get(map);
    System.out.printf("map size = %d, table length = %d%n", map.size(), table.length);
    for (int i = 0; i < table.length; i++) {
        Object node = table[i];
        if (node == null)
            continue;
        System.out.printf("table[%d] = %s", i,
            classTreeNode.isInstance(node) ? "TreeNode" : "BasicNode");

        for (; node != null; node = fieldNodeNext.get(node))
            System.out.print(" " + node);
        System.out.println();
    }
}

Теперь добавьте кучу строк, которые все попадают в одно и то же ведро. Эти строки выбираются так, что их значения хэша, рассчитанные HashMap, равны 0 mod 64.

public static void main(String[] args) throws ReflectiveOperationException {
    init();
    List<String> list = List.of(
        "LBCDD", "IKBNU", "WZQAG", "MKEAZ", "BBCHF", "KRQHE", "ZZMWH", "FHLVH",
        "ZFLXM", "TXXPE", "NSJDQ", "BXDMJ", "OFBCR", "WVSIG", "HQDXY");

    HashMap<String, String> map = new HashMap<>(1, 10.0f);

    for (String s : list) {
        System.out.println("===> put " + s);
        map.put(s, s);
        dumpMap(map);
    }
}

Начиная с начального размера таблицы 1 и смехотворного коэффициента загрузки, это помещает 8 записей в одиночный ковш. Затем, каждый раз, когда добавляется другая запись, таблица изменяется (удваивается), но все записи оказываются в одном и том же ведре. Это в конечном итоге приводит к таблице размера 64 с одним ведром, имеющим линейную цепочку узлов ("базовые узлы") длиной 14, прежде чем добавлять следующую запись, наконец, преобразует ее в дерево.

Вывод программы следующий:

===> put LBCDD
map size = 1, table length = 1
table[0] = BasicNode LBCDD=LBCDD
===> put IKBNU
map size = 2, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU
===> put WZQAG
map size = 3, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG
===> put MKEAZ
map size = 4, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ
===> put BBCHF
map size = 5, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF
===> put KRQHE
map size = 6, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE
===> put ZZMWH
map size = 7, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH
===> put FHLVH
map size = 8, table length = 1
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH
===> put ZFLXM
map size = 9, table length = 2
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM
===> put TXXPE
map size = 10, table length = 4
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE
===> put NSJDQ
map size = 11, table length = 8
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ
===> put BXDMJ
map size = 12, table length = 16
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ
===> put OFBCR
map size = 13, table length = 32
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ OFBCR=OFBCR
===> put WVSIG
map size = 14, table length = 64
table[0] = BasicNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ OFBCR=OFBCR WVSIG=WVSIG
===> put HQDXY
map size = 15, table length = 64
table[0] = TreeNode LBCDD=LBCDD IKBNU=IKBNU WZQAG=WZQAG MKEAZ=MKEAZ BBCHF=BBCHF KRQHE=KRQHE ZZMWH=ZZMWH FHLVH=FHLVH ZFLXM=ZFLXM TXXPE=TXXPE NSJDQ=NSJDQ BXDMJ=BXDMJ OFBCR=OFBCR WVSIG=WVSIG HQDXY=HQDXY