HashMap переразметить / изменить размер емкости

Question

A HashMap имеет такую ​​фразу из документации:

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

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

И, конечно, 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 и далее, что больше не верно.Поскольку я не уверен в этом, я не добавляю это как ответ.

Answer 1

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

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

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

Я считаю, что эта документация вернапока реализация бункера дерева не была добавлена.Однако, как вы заметили, сейчас есть случаи, когда это неверно.Политика заключается не только в том, что изменение размера может происходить, если количество записей, деленное на коэффициент загрузки, превышает емкость (на самом деле, длину таблицы).Как вы заметили, изменения могут также происходить, если количество записей в одном сегменте превышает 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:

// 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