Java Academy · Lección

Treeification y rendimiento

Cómo gestiona Java 8+ las colisiones

Treeification y rendimiento es una lección gratuita de Java Academy en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Java Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Java Academy incluye 4 lecciones en total.

El problema de las colisiones

Antes de Java 8, un bucket con muchas colisiones se convertía en una larga lista enlazada. La búsqueda en ese bucket se degradaba a O(n).

Un atacante podía aprovecharlo con claves diseñadas para provocar una denegación de servicio, haciendo que todas generaran un hash para el mismo bucket.

public class Main {
    public static void main(String[] args) {
        // All these strings can be made to collide in one bucket
        System.out.println("FB".hashCode() == "Ea".hashCode());
    }
}

Conversión en árbol en Java 8

Java 8 incorporó la conversión en árbol. Cuando un solo bucket contiene demasiadas entradas, la lista enlazada se convierte en un árbol rojo-negro equilibrado.

La búsqueda en ese bucket pasa a ser O(log n) en lugar de O(n).

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < 1000; i++) m.put(i, i);
        System.out.println("Lookups stay fast: " + m.get(742));
    }
}

El umbral: TREEIFY_THRESHOLD

La constante TREEIFY_THRESHOLD es 8. Un bucket se convierte en un árbol cuando alcanza 8 entradas.

Pero hay una segunda condición: la tabla también debe tener al menos el tamaño de MIN_TREEIFY_CAPACITY (64); de lo contrario, el mapa cambia de tamaño.

public class Main {
    public static void main(String[] args) {
        int TREEIFY_THRESHOLD = 8;
        int MIN_TREEIFY_CAPACITY = 64;
        System.out.println("Treeify when bucket size >= " + TREEIFY_THRESHOLD);
        System.out.println("...and table capacity >= " + MIN_TREEIFY_CAPACITY);
    }
}

Redimensionar primero, convertir en árbol después

Si un bucket se desborda, pero la tabla aún es pequeña (menos de 64), HashMap redimensiona primero la tabla.

El redimensionamiento suele redistribuir las entradas y eliminar el punto problemático, por lo que la conversión en árbol es el último recurso para distribuciones de hash realmente deficientes.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16);
        for (int i = 0; i < 50; i++) m.put(i, i);
        // Many resizes happened before any treeify would
        System.out.println("size = " + m.size());
    }
}

Volver a una lista

Los árboles no son permanentes. Si las eliminaciones reducen un bucket por debajo de UNTREEIFY_THRESHOLD (6), el árbol vuelve a ser una lista enlazada.

La diferencia entre 8 (conversión en árbol) y 6 (vuelta a una lista) evita cambios constantes en uno y otro sentido en el límite.

public class Main {
    public static void main(String[] args) {
        System.out.println("TREEIFY_THRESHOLD   = 8");
        System.out.println("UNTREEIFY_THRESHOLD = 6");
        System.out.println("Gap prevents flip-flopping at the edge");
    }
}

Los árboles necesitan un orden basado en Comparable o en la identidad

Un árbol rojo-negro debe ordenar sus entradas. HashMap compara primero los códigos hash; los empates se resuelven mediante Comparable si las claves lo implementan y, en caso contrario, mediante un desempate estable basado en los nombres de las clases y la identidad.

Las claves que son Comparable (como String o Integer) proporcionan el orden más limpio para el árbol.

public class Main {
    public static void main(String[] args) {
        System.out.println("String is Comparable: " + ("a" instanceof Comparable));
        System.out.println("Integer is Comparable: " + (Integer.valueOf(1) instanceof Comparable));
    }
}

Impacto práctico

En la mayoría de los programas reales con códigos hash adecuados, nunca verá una conversión en árbol. Los buckets se mantienen cortos.

La conversión en árbol es una red de seguridad que limita la búsqueda en el peor caso a O(log n), incluso cuando el hash es deficiente o malicioso.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("alpha", 1);
        m.put("beta", 2);
        m.put("gamma", 3);
        // Tiny buckets, plain linked lists, no trees needed
        System.out.println(m.get("beta"));
    }
}

Un hashCode constante fuerza la conversión en árbol

Si devuelve deliberadamente un hashCode constante, todas las claves llegan al mismo bucket. Con una capacidad de 64 o más, ese bucket se convierte en un árbol.

Esto demuestra la red de seguridad, pero es una mala señal de diseño. Corrija el hashCode.

import java.util.HashMap;
import java.util.Map;

public class Main {
    static class Bad implements Comparable<Bad> {
        final int v;
        Bad(int v) { this.v = v; }
        @Override public int hashCode() { return 1; } // forces collisions
        @Override public boolean equals(Object o) { return o instanceof Bad b && b.v == v; }
        @Override public int compareTo(Bad o) { return Integer.compare(v, o.v); }
    }
    public static void main(String[] args) {
        Map<Bad, Integer> m = new HashMap<>();
        for (int i = 0; i < 100; i++) m.put(new Bad(i), i);
        System.out.println("All in one bucket, still works: " + m.get(new Bad(50)));
    }
}

Coste de memoria de los árboles

Los nodos de árbol son más grandes que los nodos de una lista enlazada normal porque almacenan referencias al padre, al nodo izquierdo, al derecho y al color.

Esta es otra razón por la que la conversión en árbol es una alternativa de último recurso, no la opción predeterminada: los árboles intercambian memoria por velocidad en el peor caso.

public class Main {
    public static void main(String[] args) {
        System.out.println("Node: hash, key, value, next");
        System.out.println("TreeNode: + parent, left, right, prev, red flag");
        System.out.println("=> trees cost more memory per entry");
    }
}

Cómo evitar la conversión en árbol

Casi nunca conviene depender de la conversión en árbol. Evítela de estas formas:

Escribiendo un hashCode() bien distribuido.
Utilizando tipos integrados o records como claves.
Dimensionando previamente el mapa para reducir las colisiones.

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class Main {
    record Key(int a, int b) {}
    public static void main(String[] args) {
        Map<Key, Integer> m = new HashMap<>(256);
        for (int i = 0; i < 200; i++) m.put(new Key(i, i * 31), i);
        System.out.println("Even distribution, fast lookups: " + m.get(new Key(10, 310)));
    }
}

Resumen del rendimiento

Costes de las operaciones de HashMap:

Buen hash: O(1) de media.
Bucket con lista enlazada: O(n) por bucket en el peor caso.
Bucket convertido en árbol: O(log n) por bucket.

La conversión en árbol limita el peor caso, pero un buen hashCode le mantiene en O(1).

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(1 << 14);
        for (int i = 0; i < 10000; i++) m.put(i, i);
        System.out.println("10k entries, O(1) get: " + m.get(9999));
    }
}

Comprobación rápida

Compruebe sus conocimientos sobre la conversión en árbol.

Repaso

Ha aprendido cómo HashMap gestiona las colisiones actualmente:

Los buckets se convierten en árboles con 8 entradas cuando la capacidad es de al menos 64.
Los árboles ofrecen una búsqueda en el peor caso de O(log n).
Los buckets vuelven a ser listas enlazadas cuando tienen menos de 6 entradas.
Un buen hashCode significa que rara vez activará esta red de seguridad.

Ha completado el curso sobre los componentes internos de HashMap.

public class Main {
    public static void main(String[] args) {
        System.out.println("Treeification course complete");
    }
}

Preguntas frecuentes

¿La lección «Treeification y rendimiento» es gratis?

Sí — el texto completo de «Treeification y rendimiento» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Java Academy, actualiza a CoddyKit PRO. El curso de Java Academy incluye 4 lecciones en total.

¿Qué aprenderé en «Treeification y rendimiento»?

Cómo gestiona Java 8+ las colisiones Practicas Java Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar Java Academy?

No se requiere experiencia previa. Java Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.

¿Cuánto tiempo toma la lección «Treeification y rendimiento»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de Java Academy?

Sí. Cada lección de Java Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

← Volver a Java Academy