Necesitas igualdad de objetos, arreglos y costo esperado. La lección explica el contrato entre equals y hashCode.
CONTENIDO ORIGINAL
Avanza en orden. Cada lección está redactada para Palta es Cool, utiliza ejemplos propios y termina con una actividad cuya respuesta puedes desplegar.
ANTES DE EMPEZAR
Ubícate antes de avanzar
Al terminar deberías poder relacionar Tabla hash y factor de carga con Colisiones y resolver un caso nuevo.
Reserva entre 75 y 120 minutos o divide el laboratorio en dos sesiones.
04 / PREPARA EL LABORATORIO
Instala un JDK actual y utiliza un editor o IDE con soporte para Java. Trabaja en un proyecto de laboratorio separado.
Abrir la guía de herramientas →Diagnóstico rápido: ¿cómo se relacionan Tabla hash y factor de carga y Colisiones? ＋
No necesitas acertar todavía. Escribe una hipótesis de dos líneas y compárala con tu respuesta al finalizar; si puedes corregirla y justificar el cambio, hubo aprendizaje.
Aprende el tema paso a paso
Diseñarás acceso por clave comprendiendo tanto el caso promedio rápido como las colisiones y los contratos que lo sostienen.
Al terminar podrás
- Una función hash distribuye; no demuestra igualdad
- Encadenamiento y direccionamiento abierto conservan búsquedas distintas
- equals y hashCode deben contar la misma historia
01
De clave a índice
Una función hash distribuye; no demuestra igualdad
hashCode transforma una clave en un entero y la capacidad lo lleva a un índice válido. Claves diferentes pueden producir el mismo índice. El factor de carga size/capacidad ayuda a decidir cuándo redimensionar para evitar demasiadas colisiones.
El mismo objeto sin cambios debe conservar su hash.
Índice y hash no son identificadores únicos.
La distribución importa además del costo de calcular.
¿Por qué Math.floorMod es más seguro que hash % capacidad?
Mostrar respuesta ＋
Porque entrega un índice no negativo incluso cuando hashCode devuelve un entero negativo.
02
Colisiones y borrado
Encadenamiento y direccionamiento abierto conservan búsquedas distintas
El encadenamiento guarda una colección por casilla. El direccionamiento abierto busca otra posición mediante sondeo. En este último, borrar no puede convertir siempre la casilla en vacía: una marca de eliminado conserva el camino de búsqueda de claves desplazadas.
VACÍA permite detener una búsqueda.
ELIMINADA permite continuar y reutilizar.
OCUPADA exige comparar la clave con equals.
¿Qué estado debe dejar la posición 6?
Mostrar respuesta ＋
ELIMINADA (una marca de borrado), no VACÍA; así la búsqueda continúa y una inserción futura puede reutilizarla.
03
Claves correctas
equals y hashCode deben contar la misma historia
Si dos claves son iguales según equals, deben producir el mismo hashCode. Una clave mutable puede volverse imposible de encontrar si cambia después de insertarse. En una aplicación normal, Map y HashMap ofrecen una implementación robusta; construir una tabla propia sirve para aprender y experimentar.
Igualdad implica mismo hash, no al revés.
Prefiere claves inmutables.
El rendimiento esperado O(1) depende de distribución y carga.
¿Qué ocurre si equals dice que dos claves son iguales pero sus hashCode difieren?
Mostrar respuesta ＋
Pueden terminar en zonas diferentes de la tabla y el mapa puede no encontrar un valor mediante una clave que debería considerarse equivalente.
Tu recorrido en tres ideas
- Una función hash distribuye; no demuestra igualdad
- Encadenamiento y direccionamiento abierto conservan búsquedas distintas
- equals y hashCode deben contar la misma historia
Construye un diccionario resistente a colisiones
Combina hash, igualdad, colisiones, estados de casilla, factor de carga y redimensionamiento.
CASO
Muchas claves caen en la misma zona y después se eliminan algunas antes de nuevas inserciones.
Procedimiento
- Implementa sondeo lineal con VACÍA, OCUPADA y ELIMINADA.
- Fuerza colisiones y prueba búsquedas a través de casillas eliminadas.
- Redimensiona, vuelve a insertar y contrasta operaciones con HashMap.
Evidencia mínima
- Claves distintas con el mismo índice inicial.
- Búsqueda correcta después de borrados.
- Factor de carga y conteo antes y después del resize.
Mostrar razonamiento modelo ＋
Una casilla eliminada no corta el sondeo. Redimensionar exige recalcular posiciones porque cambia la capacidad; copiar las casillas sin reinsertar rompe el acceso.
Para ir más lejos¿Qué patrón de claves mostraría una función hash con mala distribución?
CIERRE DE LA SECCIÓN
Comprueba que puedes usarlo
Antes de continuar, revisa estos tropiezos frecuentes y resuelve un caso sin copiar los ejemplos.
Tratar el hash como identificador único.
Marcar como vacía una casilla eliminada en direccionamiento abierto.
Ahora hazlo sin guía
Completa un diccionario con sondeo lineal, tres estados, redimensionamiento y claves genéricas.
Mostrar pauta de corrección ＋
Una respuesta sólida:
- equals y hashCode se usan coherentemente.
- Busca después de una eliminación con colisión.
- Mantiene el factor de carga bajo el umbral elegido.