Skip to main content

Abrir el simulador

Inserta, busca y borra en una tabla hash cerrada o abierta y mira cada sondeo.
Buscar un elemento en una lista obliga a recorrerla. En un árbol equilibrado, unos log⁡2n\log_2 n pasos. Una tabla hash lo hace, de media, en tiempo constante: calcula directamente en qué casilla debería estar. Es lo que hay detrás de HashMap y HashSet en Java, de los diccionarios de Python y de los índices de las bases de datos.

​
Lo que vas a aprender

  • Qué es una función hash y por qué hay colisiones.
  • La tabla cerrada con sondeo lineal y cuadrático.
  • La tabla abierta con listas (encadenamiento).
  • Por qué no se puede vaciar una casilla al borrar en una tabla cerrada.
  • El factor de carga y el redimensionado.

​
Cómo se usa el simulador

  • Elige Cerrada (sondeo) o Abierta (listas) y, en la cerrada, sondeo lineal o cuadrático.
  • Inserta, busca y borra valores. El simulador marca cada casilla que se sondea, cuáles están ocupadas y cuáles borradas, y resalta la línea del código Java.
  • Prueba a borrar un elemento y buscar otro que chocó con él.

​
Fundamentos teóricos

​
Función hash

Convierte cada elemento en una posición de la tabla de tamaño BB: h(e)=e.hashCode() mod Bh(e) = e.\text{hashCode()} \bmod B Con enteros, en el simulador, h(e)=e mod Bh(e) = e \bmod B. Una buena función hash reparte los elementos de forma uniforme.

​
Colisiones

Dos elementos distintos pueden caer en la misma posición: es una colisión. Son inevitables, y hay dos formas de resolverlas.

​
Tabla cerrada (direccionamiento abierto)

Todo se guarda en el propio array. Si la casilla está ocupada, se sondea otra:
  • Lineal: h,h+1,h+2,…h, h + 1, h + 2, \dots (módulo BB). Sencillo, pero forma agrupamientos.
  • Cuadrático: h,h+1,h+4,h+9,…h, h + 1, h + 4, h + 9, \dots. Reduce los agrupamientos.
Cada casilla tiene un estado: VACÍA, OCUPADA o BORRADA.

​
Borrar en una tabla cerrada

Una búsqueda se detiene al llegar a una casilla vacía. Si al borrar se vaciara la casilla, los elementos que chocaron allí y se guardaron más adelante ya no se encontrarían. Por eso se marca como BORRADA: las búsquedas la saltan y las inserciones pueden reutilizarla.

​
Tabla abierta (encadenamiento)

Cada posición guarda una lista con todos los elementos que caen en ella. Borrar es quitar de la lista. Admite más elementos que casillas.

​
Factor de carga y redimensionado

α=nB\alpha = \frac{n}{B} Cuanto más llena, más colisiones y más lento. Cuando α\alpha supera un límite (por ejemplo 0,5 en la cerrada o 0,75 en HashMap), se crea una tabla mayor, normalmente de tamaño primo mayor que el doble, y se reinsertan todos los elementos.

​
¿Por qué primo?

Con un tamaño primo, los múltiplos de un mismo número se reparten por toda la tabla y el sondeo cuadrático recorre más casillas distintas.

​
Ejemplos resueltos

Ejemplo 1 · Colisiones y borrado

B=11B = 11, sondeo lineal. Se insertan 14, 25 y 36: los tres tienen h=3h = 3.14 → casilla 3. 25 → 3 ocupada, va a la 4. 36 → 3 y 4 ocupadas, va a la 5.Se borra 25: la casilla 4 queda BORRADA. Al buscar 36: 3 (14), 4 (borrada, se sigue), 5 (encontrado).
Con los mismos datos y encadenamiento, la posición 3 guarda la lista 14 → 25 → 36. Borrar 25 es quitarlo de la lista.
Si h=3h = 3 y está ocupada, se prueban 4, 7, 12 mod 11 = 1, 19 mod 11 = 8…

​
Experimenta con el simulador

1

Agrupamiento

Con sondeo lineal, inserta varios números con el mismo resto. Repite con sondeo cuadrático.
2

La marca de borrado

Reproduce el ejemplo 1 y busca 36 tras borrar 25.
3

Redimensionar

Inserta elementos hasta superar el factor de carga máximo. ¿Qué tamaño tiene la nueva tabla?

​
Errores frecuentes

  • Vaciar la casilla al borrar en una tabla cerrada.
  • Olvidar el módulo al sondear y salirse del array.
  • Implementar equals sin hashCode en Java: dos objetos iguales deben tener el mismo hash.

​
Herramientas relacionadas

ArrayList y lista enlazada

Listas en Java.

Estructuras de datos

Árbol binario de búsqueda.

Factores primos

Números primos.
Última modificación el 6 de octubre de 2026