Una tabla hash cambia un poco de memoria y un diseño cuidadoso por una de las promesas más útiles de la informática: encontrar un valor a partir de su clave en tiempo constante esperado.
La idea central
Una función hash convierte una clave en un número. Ese número, ajustado al tamaño de la tabla, elige una casilla de un arreglo. Para buscar «Maria», el programa calcula el hash, salta directamente a la casilla y revisa lo que hay allí. No hace falta recorrer nada desde el principio.
Las colisiones son normales
Dos claves distintas pueden caer en la misma casilla. Una buena tabla lo prevé. El encadenamiento guarda una lista pequeña en cada casilla. El direccionamiento abierto busca la siguiente casilla libre. Ambos enfoques funcionan bien mientras la tabla no esté demasiado llena.
Factor de carga y cambio de tamaño
El factor de carga es el número de elementos dividido entre el número de casillas. A medida que crece, las colisiones se vuelven más frecuentes y las operaciones se hacen más lentas. La mayoría de las implementaciones amplían el arreglo, a menudo duplicándolo, cuando el factor de carga supera un umbral, y reinsertan todos los elementos. Esa reconstrucción es costosa pero poco frecuente, de modo que el costo medio por inserción sigue siendo bajo.
Qué recordar
- Buscar, insertar y eliminar son O(1) en promedio, pero pueden degradarse a O(n) cuando muchas claves colisionan.
- Las tablas hash no mantienen las claves ordenadas. Para recorridos ordenados o consultas por rango, un árbol balanceado es más adecuado.
- Las claves deben poder calcularse con hash y no deben cambiar mientras están almacenadas.
Cuándo usarlas
Recurre a una tabla hash cuando la pregunta sea «¿ya vi esto?», «¿cuántas veces?» o «¿cuál es el valor de esta clave?». Contar palabras, guardar resultados en caché y detectar duplicados son usos naturales.
Continúa con el libro
Consulta el tratamiento completo, los ejemplos y los ejercicios en Algoritmos explicados con claridad.
Adaptado de Algoritmos explicados con claridad, publicado por Choral Software. Texto del artículo y ejemplos originales © 2026 Choral Software. Todos los derechos reservados.