Visualizador de tabla hash

Introduce claves y observa cómo se asignan a las ranuras. Descubre qué sucede cuando ocurren colisiones.

Ejemplo resuelto — Visualizador de tabla hash

Factor de carga alfa	0.75
Comportamiento actual	5 colisión(es)
Sondeos adicionales	15
Sondeos promedio	3.5
Probabilidad de colisión	85%

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

La preselección de colisión total no tiene un hash roto: tiene el tamaño de tabla equivocado 🖖

Sus claves son 0, 8, 16, 24, 32 y 40, y la tabla tiene 8 huecos. Todas esas claves son múltiplos de 8, así que key mod 8 manda las seis al hueco 0 y la tabla degenera en una sola lista. La función de hash no tiene nada de malo: hace exactamente lo que promete. El fallo es que el tamaño de la tabla comparte un factor con el patrón de las claves. En eso consiste todo el argumento a favor de tamaños primos — un tamaño de 8 está indefenso ante claves que avanzan de 8 en 8, mientras que un tamaño primo no ofrece ningún factor sobre el que caer. Cambia a las preselecciones de sondeo y observa la misma colisión resuelta de dos maneras.

Salta directo a la casilla 🖖

Una tabla de dispersión no es más que un array asociado a una regla, la función de dispersión, que convierte cualquier clave en el número de una casilla. En vez de recorrer las entradas una por una, calculas dónde corresponde cada elemento y vas directamente allí. Por eso las búsquedas siguen siendo rápidas incluso con millones de claves. La velocidad depende de que las claves se distribuyan de manera uniforme. Inserta unas cuantas y observa lo pronto que dos claves intentan ocupar la misma casilla.

Cuando las colisiones se vuelven un arma 🖖

Como una tabla hash degenera en una lenta búsqueda lineal cuando demasiadas claves caen en la misma casilla — justo el peor caso que puedes provocar arriba —, un atacante que conozca tu función hash puede fabricar miles de claves que colisionan a propósito. En 2011 este truco de 'hash-flooding' bloqueó servidores web en PHP, Java, Python y Ruby con una sola petición manipulada. La solución fueron funciones hash con semilla aleatoria como SipHash, hoy estándar en muchos lenguajes.

TABLAS HASH — DÓNDE CAE UNA CLAVE Y QUÉ PASA CUANDO CAEN DOS JUNTAS

¿Qué caso de colisión estás manejando?

Una tabla hash es O(1) solo mientras las claves se reparten. Dos preguntas lo deciden todo: ¿dispersa la función hash tus claves? y, cuando dos chocan, ¿cuelgas la segunda del mismo hueco o sales a buscar otro? El factor de carga α = n/m decide con qué frecuencia hay colisiones; la estrategia decide cuánto cuesta cada una.

Sin colisiones — el caso que supone la promesa O(1) h(k) = k mod m, α = n/m

Todas las claves en un hueco — el encadenamiento degenera en lista O(n)

Sondeo lineal — direccionamiento abierto con agrupamiento primario (h + i) mod m

Sondeo cuadrático — sin agrupamiento, pero puede negarse a insertar (h + i²) mod m

Sin colisiones — el caso que supone la promesa O(1)

Qué sabes: Cada clave cae en un hueco distinto. El factor de carga α = n/m está por debajo de 1 y el hash reparte las claves uniformemente por la tabla.

Regla de sondeo: h(k) = k mod m, α = n/m

Ejemplo resuelto: claves 0–5 en m = 8 con h(k) = k mod 8 → huecos 0–5, un sondeo cada una: α = 0,75 y una media de exactamente 1,00 sondeos

Abrir este caso: Sin colisión

Sin colisiones — el caso que supone la promesa O(1). Seis claves, seis huecos distintos, un sondeo cada una: solo hay que mirar el factor de carga. Cada clave cae en un hueco distinto. El factor de carga α = n/m está por debajo de 1 y el hash reparte las claves uniformemente por la tabla. — Seis claves, seis huecos distintos, un sondeo cada una: solo hay que mirar el factor de carga.

Todas las claves en un hueco — el encadenamiento degenera en lista

Qué sabes: Todas las claves son múltiplos del tamaño de la tabla, así que k mod m da el mismo hueco para todas. El encadenamiento las guarda igual, pero en una única cadena.

Regla de sondeo: O(n)

Ejemplo resuelto: claves 0, 8, 16, 24, 32, 40 en m = 8 → todas caen en el hueco 0; insertarlas cuesta 1+2+3+4+5+6 = 21 sondeos, una media de 3,50

Abrir este caso: Todas colisionan

Todas las claves en un hueco — el encadenamiento degenera en lista. Las seis claves en el hueco 0: una tabla hash convertida en lista enlazada. Todas las claves son múltiplos del tamaño de la tabla, así que k mod m da el mismo hueco para todas. El encadenamiento las guarda igual, pero en una única cadena. — Las seis claves en el hueco 0: una tabla hash convertida en lista enlazada.

Sondeo lineal — direccionamiento abierto con agrupamiento primario

Qué sabes: Sin cadenas: ante una colisión se avanza hueco a hueco hasta encontrar uno libre. Cada entrada vive dentro de la propia tabla.

Regla de sondeo: (h + i) mod m

Ejemplo resuelto: claves 3, 11, 19, 6, 14, 22 en m = 8 → huecos 3, 4, 5, 6, 7, 0 con 1, 2, 3, 1, 2, 3 sondeos: media 2,00, y las seis entradas forman un bloque continuo

Abrir este caso: Sondeo lineal

Sondeo lineal — direccionamiento abierto con agrupamiento primario. Los huecos ocupados se funden en un bloque; una clave que caiga dentro debe recorrerlo entero. Sin cadenas: ante una colisión se avanza hueco a hueco hasta encontrar uno libre. Cada entrada vive dentro de la propia tabla. — Los huecos ocupados se funden en un bloque; una clave que caiga dentro debe recorrerlo entero.

Sondeo cuadrático — sin agrupamiento, pero puede negarse a insertar

Qué sabes: Ante una colisión se salta i² huecos en vez de i. Eso rompe los bloques, pero la secuencia de sondeo deja de visitar todos los huecos.

Regla de sondeo: (h + i²) mod m

Ejemplo resuelto: las mismas claves en m = 8 → 3, 4, 7, 6, 2 y entonces 22 falla del todo: con m potencia de dos, i² mod 8 solo vale 0, 1 o 4, así que tres huecos es todo lo que alcanza

Abrir este caso: Sondeo cuadrático

Sondeo cuadrático — sin agrupamiento, pero puede negarse a insertar. La secuencia salta y luego se repite: quedan huecos libres y la última clave no tiene dónde ir. Ante una colisión se salta i² huecos en vez de i. Eso rompe los bloques, pero la secuencia de sondeo deja de visitar todos los huecos. — La secuencia salta y luego se repite: quedan huecos libres y la última clave no tiene dónde ir.

Problemas resueltos al detalle

Una tabla llena al 75% con una media de 3,5 sondeos por búsqueda 5 pasos
La tabla está llena al 75% y promedia 3,5 sondeos por búsqueda. La fórmula estándar para el sondeo lineal predice 2,5 con esa carga. Averigua cuál de los dos datos es erróneo.
1. Ninguno de los dos es incorrecto, y la razón está en las claves. Si aplicas la propia función hash de la tabla a cada una de las seis, todas devuelven 3: forman una progresión aritmética con una diferencia común de 8, y la tabla tiene exactamente 8 posiciones.
  
  $h (k) = k mod 8 : 3, 11, 19, 27, 35, 43 ⟼ 3, 3, 3, 3, 3, 3$
2. El factor de carga sigue siendo un auténtico 0,75: seis claves en ocho posiciones. Sencillamente, no dice nada sobre dónde fueron a parar.
  
  $α = \frac{n}{m} = \frac{6}{8} = 0.75$
3. Por tanto, la secuencia de sondeo es la peor posible. La primera clave ocupa un lugar libre; la segunda se desplaza una posición; la tercera se desplaza dos. Seis claves cuestan 1 + 2 + … + 6 = 21 sondeos, de los cuales 15 corresponden al trabajo extra que indica el panel.
  
  $probes = 1, 2, 3, 4, 5, 6 ⟹ \sum = 21, extra = 21 - 6 = 15$
4. Eso supone una media de 3,5 sondeos por búsqueda.
  
  $\overset{p}{ˉ} = \frac{21}{6} = 3.5$
5. La estimación de los libros de texto asume que las claves se dispersan de manera uniforme, y para α = 0,75 da 2,5. La diferencia entre 2,5 y 3,5 no es un error: es el coste de usar una función hash que comparte un factor con el tamaño de la tabla, aplicada a claves que también lo comparten.
  
  $\frac{1}{2} (1 + \frac{1}{1 - α}) = \frac{1}{2} (1 + 4) = 2.5 (random keys) < 3.5$
Respuesta

La herramienta muestra α = 0,75, 15 sondeos de trabajo extra y una media de 3,5. La lección es que el factor de carga es la cifra famosa, pero la equivocada si se observa sola: aquí es idéntico al de una tabla con seis claves bien dispersas, que costaría 2,5. Lo que ha cambiado es la interacción entre el conjunto de claves y el módulo. Por este motivo los tamaños de tabla se eligen primos, y por eso aplicar hash a un struct mediante un campo que resulta ser múltiplo de la capacidad transforma O(1) en O(n) manteniendo todas las métricas con un aspecto saludable. Cambia el tamaño de 8 a 7 y observa cómo se desploma la media.

$\overset{p}{ˉ} = 3.5 observed vs 2.5 predicted : α is not the whole story$
Un mapa hash real redimensionándose con un factor de carga de 0,75 6 pasos
El panel mete 6 claves en 8 casillas, factor de carga 0,75, y reporta 3,5 sondeos. Una búsqueda con éxito a esa carga cuesta unos 2,5 — cómodo. ¿Por qué entonces toda tabla hash real se redimensiona justo en 0,75 en lugar de llenarse?
1. Empieza donde está el panel. Tres cuartos llena, lo que suena a un uso sensato de la memoria.
  
  $α = \frac{n}{m} = \frac{6}{8} = 0.75$
2. La búsqueda con éxito es la cifra tranquilizadora: de media compruebas unas dos casillas y media antes de encontrar la clave que buscabas.
  
  $S (α) \approx \frac{1}{2} (1 + \frac{1}{1 - α}) = \frac{1}{2} (1 + 4) = 2.5$
3. La búsqueda fallida sigue otra fórmula, y en esa diferencia está toda la respuesta. Un fallo tiene que recorrer hasta el final una racha de casillas ocupadas para demostrar la ausencia, así que el término del hueco entra al cuadrado, no linealmente.
  
  $U (α) \approx \frac{1}{2} (1 + \frac{1}{( 1 - α ) ^{2}}) = \frac{1}{2} (1 + 16) = 8.5$
4. Sube un poco la carga y lee lo que hace el cuadrado. De 0,75 a 0,90 suena a un cambio modesto de ocupación.
  
  $U (0.90) = \frac{1}{2} (1 + 100) = 50.5, U (0.95) = \frac{1}{2} (1 + 400) = 200.5$
5. Compara las dos tasas de crecimiento en ese mismo paso. El coste del acierto poco más que se duplica; el del fallo se multiplica por seis.
  
  $α : 0.75 \to 0.90 ⟹ S : 2.5 \to 5.5 (\times 2.2), U : 8.5 \to 50.5 (\times 5.9)$
6. Así que la tabla se duplica en su lugar. Todas las claves se rehashean, lo que cuesta m operaciones, pero compra m inserciones más antes de que vuelva a ocurrir.
  
  $m \to 2 m ⟹ α \to \frac{α}{2}, \frac{m}{m} = O (1)$
Respuesta

Un fallo a 0,75 cuesta 8,5 sondeos; a 0,90 cuesta 50,5, y a 0,95 cuesta 200,5. Por eso 0,75 es el umbral de redimensionado en una biblioteca estándar tras otra: menos un compromiso entre memoria y velocidad que el último punto antes del precipicio. Y lo que manda es el fallo, porque con un fallo empieza toda inserción y de un fallo consiste entera toda búsqueda infructuosa. El tranquilizador 2,5 describe el caso que no te preocupaba.

$U (α) = \frac{1}{2} (1 + \frac{1}{( 1 - α ) ^{2}}) : 2.5 (0.50), 8.5 (0.75), 50.5 (0.90), 200.5 (0.95)$

Ruta de aprendizaje

Cuando dos cosas coinciden en el mismo valor

Referencias (1)

Hashing, collision resolution and why table size matters, at length: Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, §6.4. Addison-Wesley, 1998. ISBN 978-0-201-89685-5.

Por el equipo de 42Math · Actualizado 2026-07-27

Contrastado con fuentes publicadas. Se agradecen correcciones. Política editorial · Correcciones

Todas las lecciones de Informática →

Problemas de ejemplo

Sin colisión - Claves del 0 al 5 en una tabla de 8 casillas: seis casillas distintas, un sondeo por clave y ninguna colisión. El factor de carga ya es 0,75.
Todas colisionan - Todas las claves son múltiplos de 8, así que las seis se dispersan a la casilla 0 y la cadena alcanza una longitud de seis. La media es de 3,5 sondeos, el valor del que parte el problema resuelto.
Sondeo lineal - 3, 11 y 19 intentan ocupar la casilla 3; 6, 14 y 22, la casilla 6. El sondeo lineal coloca las seis claves con 1, 2, 3, 1, 2 y 3 sondeos, respectivamente: una media de 2.
Sondeo cuadrático - Con las mismas seis claves, el sondeo cuadrático no logra colocar la última. Los cuadrados módulo 8 solo pueden ser 0, 1 y 4, así que, desde la casilla 6, la secuencia pasa por 6, 7 y 2, y no llega a ninguna otra; mientras tanto, las casillas 0, 1 y 5 quedan vacías.