Java Collections Framework and Generics

Slide 1 / 7 • Taxonomy & Hierarchy

Taxonomic Map of the Java Collections Framework

JCF architecture splits into two main branches: the Collection hierarchy (individual items) and the Map hierarchy (key-value pairs).

Jerarquía Interactiva (Hacé click en una colección) JCF Core

<<interface>> Collection<E>

List<E>

Set<E>

Queue<E>

<<interface>> Map<K, V>

Ficha Técnica: ArrayList<E> Familia: List

¿Permite Duplicados? Sí

Orden de Elementos Posicional (por índice)

Acceso por Índice O(1)

Búsqueda por Valor O(N)

Estructura interna: Arreglo dinámico que redimensiona copiando a un nuevo array (+50%) cuando se llena. Es la opción por defecto cuando necesitás acceso rápido por índice.

Slide 2 / 7 • Type Safety

Generics: Farewell to Runtime ClassCastException

Prior to Java 5, collections stored raw Objects, forcing blind runtime casting. Generics shift type bugs to compile-time.

Java 1.4: Tipos Crudos (Raw Types) Bomba de Tiempo en Runtime

// Lista sin tipo (acepta Object)
List lista = new ArrayList();
lista.add("Hola mundo");
lista.add(42); // Se cuela un Integer

// Compila sin avisar, pero al leer:
String s1 = (String) lista.get(0); // OK
String s2 = (String) lista.get(1); // ¡BOOM!
// ClassCastException: Integer cannot be cast to String

⚠️ El compilador calla. El fallo explota en el servidor en producción.

Java 5+: Colecciones Parametrizadas Escudo en Compilación

// Lista tipada con genérico <String>
List<String> lista = new ArrayList<>();
lista.add("Hola mundo");

// ¡El compilador bloquea de inmediato!
lista.add(42); 
// ERROR: incompatible types: int cannot be converted to String

String s = lista.get(0); // Sin casteo manual

🛡️ Detección estática instantánea antes de que el código se ejecute.

Slide 3 / 7 • Practical Decision Guide

The 4 Families: Interactive Decision Tree

Choosing the right collection determines performance and maintainability. Answer the criteria to reveal the optimal structure.

Asistente de Selección de Colección Paso 1 de 3

1. ¿Tus datos son pares Clave → Valor (ej. DNI → Persona)?

Colección Recomendada ArrayList<T>

La opción por defecto para listas

Si necesitás almacenar elementos individuales, permitís duplicados y requerís acceso rápido por índice posicional, ArrayList es el estándar indiscutido en la industria.

List<String> lista = new ArrayList<>();
lista.add("Elemento");
String item = lista.get(0); // O(1)

Slide 4 / 7 • Under the Hood

HashMap Anatomy: Buckets Array and Hashing Math

HashMap achieves average O(1) lookup by indexing an internal array using the key hashCode() and a bitwise mask.

Matemática del Hashing: Clave → Índice de Cubeta table.length = 16

1

Clave de entrada: String key = "juan"

2

Cálculo de Hash Code: int h = "juan".hashCode() → 3254921

3

Compresión Bit a Bit (h & (16 - 1)): 3254921 & 15 → Índice: [9]

4

Almacenamiento en Cubeta table[9]: Node("juan", valor, next = null)

¿Por qué potencias de 2? Al ser la capacidad una potencia de dos (16, 32, 64...), la operación h % 16 es idéntica a h & (16 - 1), la cual se ejecuta a nivel de microprocesador en un solo ciclo de reloj.

Estructura del Nodo Interno

// Clase interna de HashMap (Node<K,V>)
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;    // Hash precomputado
    final K key;       // Clave original
    V value;           // Valor asociado
    Node<K,V> next;    // Enlace si hay colisión
}

// El mapa es simplemente:
transient Node<K,V>[] table;

Claves inmutables: Si mutás un objeto luego de usarlo como clave en un HashMap, su hashCode() cambia y el mapa nunca más podrá encontrarlo (fuga de memoria silenciosa).

Slide 5 / 7 • Collisions & Trees

Collision Resolution and Treeification (Red-Black Trees)

When keys share a bucket, collisions occur. Java 8+ transforms linked lists into Red-Black trees once collisions exceed 8 nodes.

Evolución de una Cubeta: Lista → Árbol Java 8 Optimization

≤ 8 Nodos: Encadenamiento Lineal O(N)

N1

→

N2

→

N3

→ null

> 8 Nodos: Treeification a Red-Black Tree O(log N)

Raíz (Black)

Hijo Izq

Hijo Der

Ataques DoS prevenidos: En versiones antiguas de Java, atacantes enviaban miles de claves diseñadas para colisionar en el mismo bucket, degradando el HashMap a una lista $O(N)$ y saturando el CPU al 100%. Con árboles balanceados, el peor caso se limita a $O(\log N)$.

Constantes Críticas en HashMap

DEFAULT_INITIAL_CAPACITY 16

DEFAULT_LOAD_FACTOR 0.75

TREEIFY_THRESHOLD 8

UNTREEIFY_THRESHOLD 6

Si un bucket con árbol se reduce a 6 elementos por eliminaciones, Java lo des-arboliza volviendo a lista enlazada para ahorrar memoria.

Slide 6 / 7 • Interactive Live Lab

Interactive Live HashMap Simulator

Insert keys, watch bucket distribution, trigger collisions, and inspect the load factor and automated table resizing.

Cubetas (Buckets) en Memoria Items: 3 | Capacidad: 8 | Carga: 37%

Métricas de Rendimiento

Factor de Carga Actual

0.375 / Umbral: 0.75

¿Requiere Resize? No (Capacidad suficiente)

Efecto del Resize: Cuando $N > capacidad \times 0.75$, la tabla duplica su tamaño ($8 \to 16 \to 32$) y reubica todos los nodos con el nuevo bitmask.

Slide 7 / 7 • Bytecode & JVM Internals

Type Erasure: The Fine Print of Java Generics

Generics only exist at compile time. In bytecode, types are erased and substituted with Object plus automated compiler casts.

Código Fuente (Java Source) Lo que escribís

public class Caja<T> {
    private T contenido;

    public void guardar(T dato) {
        this.contenido = dato;
    }

    public T obtener() {
        return this.contenido;
    }
}

Bytecode Compilado (Type Erasure) Lo que ve la JVM

public class Caja {
    private Object contenido; // T se borró

    public void guardar(Object dato) {
        this.contenido = dato;
    }

    public Object obtener() {
        return this.contenido;
    }
}

Consecuencias Inevitables del Type Erasure en Java

1. Prohibido new T()

En runtime la JVM no sabe qué constructor llamar porque T ya no existe.

2. Prohibido new T[10]

Los arreglos en Java son reificados (conocen su tipo en runtime); los genéricos no.

3. No hay List<int>

Los primitivos no heredan de Object, exigiendo wrappers como Integer.