Tamaño m (primo)
Función hash
Resolución de colisiones
Tabla hash — m = 11
0
1
2
3
4
5
6
7
8
9
10
Elementos (n)0
Tamaño (m)11
Colisiones0
Factor de carga α0.00
Factor de carga α = n/mα = 0.00
Vacía Ocupada Colisión Insertando
Visualiza tablas hash, funciones hash y estrategias de resolución de colisiones
Funciones hash, resolución de colisiones y factor de carga
Una tabla hash almacena pares clave-valor en posiciones calculadas por una función hash h(k). Cuando dos claves producen el mismo índice ocurre una colisión, que se resuelve con encadenamiento (listas enlazadas en cada celda) o sondeo lineal (buscar el siguiente hueco disponible). Un buen factor de carga α < 0,75 garantiza O(1) promedio en búsquedas e inserciones.
| Resolución | Ventaja | Desventaja | Rendimiento promedio | Sensible a α | Uso real |
|---|---|---|---|---|---|
| Encadenamiento separado | Sin límite de carga | Memoria extra por punteros | O(1 + α) | Moderado | Java HashMap, Python dict |
| Sondeo lineal | Caché-friendly | Clustering primario | O(1/(1-α)) | Alto | Redis, TablaHash C++ |
| Sondeo cuadrático | Menos clustering | Clustering secundario | O(1/(1-α)) | Alto | PostgreSQL |
| Doble hashing | Distribución uniforme | Más costoso de calcular | O(1/(1-α)) | Muy alto | Cuckoo hashing |
| Cuckoo hashing | Worst-case O(1) | Rehash frecuente | O(1) garantizado | Extremo | Redes (packet lookup) |
| Árbol rojo-negro (alternativa) | O(log n) garantizado | Más lento en promedio | O(log n) | No | Java TreeMap, std::map |
m = 17, 8 palabras cortas, función djb2 → distribución casi perfecta, 0 colisiones. El factor de carga α ≈ 0,47 mantiene O(1) garantizado.
m = 7, insertar 8 palabras → α ≈ 1,14 con sondeo lineal o cadenas largas. Las colisiones crecen exponencialmente y el tiempo de búsqueda se degrada.
m = 11, palabras con hashes consecutivos → sondeo lineal agrupa elementos en bloques («clustering primario»), degradando búsquedas en esa zona.
m = 7, insertar 10 palabras → con encadenamiento la tabla funciona aunque α > 1; con sondeo lineal se llena y necesitaría rehash para continuar.
Los tamaños primos reducen la periodicidad de las colisiones al aplicar mod. Si m tiene divisores comunes con los hashes generados, ciertos índices nunca se usan y otros se sobrecargan. Con m primo, la función mod distribuye los valores más uniformemente.
La tabla está completamente llena: cualquier nueva inserción entraría en bucle infinito buscando un hueco que no existe. Por eso, las implementaciones reales hacen rehashing automático cuando α supera un umbral (típicamente 0,75), creando una tabla mayor y reinsertando todos los elementos.
Sí. dict y set en Python son tablas hash con open addressing y sondeo cuadrático modificado. Desde Python 3.6, los dicts también preservan el orden de inserción gracias a una estructura auxiliar compacta.
Una función hash pobre (como suma de caracteres para cadenas cortas) agrupa muchas claves en pocos índices. djb2 aplica multiplicaciones que dispersan mejor los valores. Una buena función hash hace que la distribución de índices sea aproximadamente uniforme.
Cuando α supera un umbral (0,75 típico), se crea una tabla nueva de tamaño mayor (generalmente el siguiente primo después de 2×m) y se reinsertan todos los elementos usando la misma función hash con el nuevo m. Esta operación es O(n) pero amortizada resulta O(1) por inserción.
Empieza con m = 11 y djb2: es el tamaño y función más equilibrados para ver la distribución.
El conjunto «nombres» o «programación» dan buen contraste de colisiones según la función elegida.
Cada inserción muestra el cálculo paso a paso del índice hash debajo de la tabla. Las celdas se colorean según el estado.
Limpiar la tabla, cambiar a sondeo lineal e insertar el mismo conjunto revela diferencias de distribución.
Usa m = 7 e inserta todas las palabras para ver cómo crecen las colisiones y se degrada el rendimiento.
Un tamaño primo reduce colisiones porque ningún divisor común «agrupa» los hashes.
Función hash simple y veloz usada en compiladores y shells UNIX. Buen equilibrio distribución/coste.
El factor de carga α = n/m es el mejor indicador del rendimiento. Mantén α < 0,75.
Las implementaciones reales hacen rehash automático al superar α = 0,75 para mantener O(1).