java - example - HashMap rehash/redimensionar capacidad

java se 8 hashtable

Question

Un HashMap tiene tal frase de su documentación:

Si la capacidad inicial es mayor que la cantidad máxima de entradas dividida por el factor de carga, nunca se realizarán operaciones de repetición.

Observe que la documentación dice " rehash" , no " redimensionamiento" , incluso si un rehash solo ocurrirá cuando "redimensionará"; es decir, cuando el tamaño interno de los cubos es el doble de grande.

Y, por supuesto, HashMap proporciona un constructor de este tipo donde podríamos definir esta capacidad inicial .

Construye un HashMap vacío con la capacidad inicial especificada y el factor de carga predeterminado (0.75).

OK, parece bastante fácil:

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

Entonces, la capacidad es 13 (internamente es 16 - la siguiente potencia de dos), de esta manera garantizamos que la documentación no contemple ningún problema. Ok, probemos esto, pero primero introduzcamos un método que entrará en un HashMap y observará los valores:

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);
    }
}

Y ahora probemos esto:

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);

}

Bueno, se resize y, por lo tanto, las entradas se repitieron, no como dice la documentación.

Como se dijo, las teclas no fueron elegidas al azar. Estos se configuraron de modo que static final int TREEIFY_THRESHOLD = 8; propiedad - cuando un cubo se convierte en un árbol. Bueno, no realmente, ya que necesitamos golpear también MIN_TREEIFY_CAPACITY = 64 para que aparezca el árbol; hasta que ocurra el cambio de resize , o se duplique el tamaño de un cubo; De este modo se repite el recuento de entradas.

Solo puedo sugerir por qué la documentación de HashMap es incorrecta en esa oración, ya que antes de java-8, un cubo no se convertía en un árbol; por lo tanto, la propiedad se mantendría, desde java-8 y en adelante eso ya no es cierto. Como no estoy seguro de esto, no lo estoy agregando como respuesta.

Answer 1

La línea de la documentación,

Si la capacidad inicial es mayor que la cantidad máxima de entradas dividida por el factor de carga, nunca se realizarán operaciones de repetición.

de hecho, las fechas anteriores a la implementación de la caja del árbol se agregaron en JDK 8 ( JEP 180 ). Puede ver este texto en la documentación de JDK 1.6 HashMap . De hecho, este texto se remonta a JDK 1.2 cuando se introdujo el marco de colecciones (incluido HashMap). Puede encontrar versiones no oficiales de los documentos JDK 1.2 en la web, o puede descargar una versión de los archives si desea ver por sí mismo.

Creo que esta documentación fue correcta hasta que se agregó la implementación de tree-bin. Sin embargo, como ha observado, ahora hay casos en los que es incorrecto. La política no es solo que el cambio de tamaño puede ocurrir si el número de entradas divididas por el factor de carga excede la capacidad (realmente, la longitud de la tabla). Como notó, los tamaños también pueden ocurrir si el número de entradas en un solo cubo excede TREEIFY_THRESHOLD (actualmente 8) pero la longitud de la tabla es menor que MIN_TREEIFY_CAPACITY (actualmente 64).

Puedes ver esta decisión en el método treeifyBin() de HashMap.

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

Este punto en el código se alcanza cuando hay más de TREEIFY_THRESHOLD entradas en un solo grupo. Si el tamaño de la tabla es igual o superior a MIN_TREEIFY_CAPACITY, esta bandeja se encuentra en forma de árbol; de lo contrario, la tabla simplemente se redimensiona.

Tenga en cuenta que esto puede dejar las papeleras con más entradas que TREEIFY_THRESHOLD en tamaños de tabla pequeños. Esto no es terriblemente difícil de demostrar. Primero, algunos códigos reflexivos de 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();
    }
}

Ahora, agreguemos un montón de cuerdas que caen en el mismo cubo. Estas cadenas se eligen de modo que sus valores hash, calculados por HashMap, sean todos 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);
    }
}

A partir de un tamaño de tabla inicial de 1 y un factor de carga ridículo, esto pone 8 entradas en el cubo solitario. Luego, cada vez que se agrega otra entrada, la tabla se redimensiona (se duplica) pero todas las entradas terminan en el mismo grupo. Con el tiempo, esto resulta en una tabla de tamaño 64 con un grupo que tiene una cadena lineal de nodos ("nodos básicos") de longitud 14, antes de agregar la siguiente entrada, finalmente se convierte en un árbol.

La salida del programa es la siguiente:

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