5. Mapas y conjuntos (hashing)
Un mapa asocia clave → valor en tiempo casi constante O(1) promedio gracias a una función hash que proyecta la clave a un índice de cubeta.
Función hash
Debe ser determinística, repartir bien los valores y ser barata de calcular. En Java,
Object.hashCode() y Objects.hash(...) alimentan a HashMap. Dos objetos iguales por
equals deben tener el mismo hashCode.
Colisiones
Dos claves distintas pueden caer en la misma cubeta.
Encadenamiento (cada cubeta es una lista de entradas)
índice 0 1 2 3
┌──┐ ┌──┐ ┌──┐ ┌──┐
│ │ │ │ │▶│k1,v1│──▶│k5,v5│──▶ null
└──┘ └──┘ └──┘ └──┘
k1 y k5 colisionan Direccionamiento abierto (linear probing)
[ . ][ A ][ B ][ . ][ . ]
↑ intentamos C con misma cubeta que B
→ probamos siguiente celda libre - Encadenamiento: más simple de razonar; la lista puede crecer.
- Abierto: sin punteros extra; riesgo de clustering; requiere buen factor de carga y rehashing.
HashMap y HashSet
HashSet es un mapa «sin valor»: solo claves únicas. Por dentro, JDK usa tablas hash optimizadas (árboles en cubetas
muy pobladas desde Java 8). No dependas del orden de iteración.
Propuesta de diseño
Implementá una mini MiMapa<K,V> con arreglo de listas enlazadas de entradas, factor de carga 0.75 y
duplicar capacidad al superarlo. Compará tiempos con HashMap del JDK para validar tu intuición Big O.
