Una tabla hash de tamaño M = 7 usa la función h(k) = k mod 7. Inserta en este orden las claves 19, 26, 12, 5, 33. Muestra el contenido de la tabla resolviendo las colisiones por sondeo lineal y, alternativamente, por encadenamiento separado. Indica qué claves colisionan y por qué el factor de carga influye en el rendimiento de las operaciones.
Este supuesto evalúa tu dominio de las tablas hash, una estructura clave del tema de TADs y algoritmos. No te limites a "rellenar la tabla": el tribunal valora que justifiques cada paso.
Cuestión de la inserción. Recuerda que la función h(k) = k mod M reparte las claves en M cubetas. Calcula primero, para cada clave, su posición teórica (el resto de dividir entre 7). Hazlo de forma ordenada en una pequeña tabla auxiliar antes de insertar nada: así detectarás de un vistazo qué claves caen en la misma cubeta. El error típico aquí es equivocarse en una operación módulo (revisa con cuidado las claves mayores que M).
Sondeo lineal (open addressing). El concepto a recordar es que todas las claves viven dentro del propio array; ante colisión se busca la siguiente posición libre con (h(k) + i) mod M, i = 1, 2, 3... Da los pasos respetando el orden de inserción del enunciado (es vinculante). Evita dos errores clásicos: olvidar el módulo al desbordar el final del array (debe ser circular) y confundir clustering primario con la simple ocupación.
Encadenamiento separado (chaining). Aquí cada cubeta es una lista enlazada; las claves colisionantes no se desplazan, se añaden a la lista de su cubeta. Decide y menciona el criterio de inserción (al inicio o al final de la lista) porque condiciona el resultado mostrado.
Factor de carga (λ = n/M). Define la fórmula y explica su efecto en el coste medio de búsqueda: relaciónalo con el rehashing y con la diferencia de comportamiento entre ambas estrategias cuando λ crece (en sondeo lineal el coste se dispara al acercarse a 1; en encadenamiento degrada de forma más suave). Cierra calculando el λ resultante.
No olvides comparar ventajas e inconvenientes de las dos técnicas: es lo que distingue una respuesta de máxima nota.
Datos del enunciado: tabla de tamaño M = 7, función hash h(k) = k mod 7, claves a insertar en orden: 19, 26, 12, 5, 33.
Calculamos el valor hash de cada clave antes de resolver colisiones:
\begin{aligned} h(19) &= 19 \bmod 7 = 5 \quad (19 = 2\cdot 7 + 5) \\ h(26) &= 26 \bmod 7 = 5 \quad (26 = 3\cdot 7 + 5) \;\;\leftarrow\; \text{colisiona con } 19 \\ h(12) &= 12 \bmod 7 = 5 \quad (12 = 1\cdot 7 + 5) \;\;\leftarrow\; \text{colisiona con } 19 \text{ y } 26 \\ h(5) &= \phantom{0}5 \bmod 7 = 5 \quad (\phantom{0}5 = 0\cdot 7 + 5) \;\;\leftarrow\; \text{colisiona con } 19,\, 26 \text{ y } 12 \\ h(33) &= 33 \bmod 7 = 5 \quad (33 = 4\cdot 7 + 5) \;\;\leftarrow\; \text{colisiona con todas} \end{aligned}| Clave | k mod 7 | Cubeta destino |
|---|---|---|
| 19 | 5 | 5 |
| 26 | 5 | 5 |
| 12 | 5 | 5 |
| 5 | 5 | 5 |
| 33 | 5 | 5 |
Resultado clave: todas las claves del conjunto son congruentes con 5 módulo 7, es decir, todas son de la forma 7q + 5. Por tanto las cinco claves colisionan en la misma cubeta (índice 5). Es el caso peor posible para una función hash: un reparto totalmente degenerado en el que la función no dispersa nada. Esto se debe a que el conjunto elegido pertenece a una única clase de equivalencia módulo 7 (todas dejan resto 5). Una función hash de calidad debería repartir uniformemente; aquí el supuesto lo provoca a propósito para forzar la gestión de colisiones.
En sondeo lineal, ante colisión se prueba la secuencia de posiciones (h(k) + i) mod 7, con i = 0, 1, 2, ..., hasta encontrar un hueco libre. Insertamos respetando el orden dado.
Paso a paso:
Insertar 19: h=5. Posición 5 libre → 19 va a [5]
Insertar 26: h=5. [5] ocupada (19) → i=1: (5+1) mod 7 = 6 libre → 26 va a [6]
Insertar 12: h=5. [5] ocupada (19) → i=1: 6 ocupada (26)
→ i=2: (5+2) mod 7 = 0 libre → 12 va a [0]
Insertar 5: h=5. [5] ocupada → i=1: 6 ocupada
→ i=2: 0 ocupada (12)
→ i=3: (5+3) mod 7 = 1 libre → 5 va a [1]
Insertar 33: h=5. [5] ocupada → i=1: 6 ocupada
→ i=2: 0 ocupada
→ i=3: 1 ocupada (5)
→ i=4: (5+4) mod 7 = 2 libre → 33 va a [2]
Contenido final de la tabla (sondeo lineal):
Justificación: se observa el fenómeno de clustering primario (agrupamiento primario): como todas las claves caen en el mismo punto de arranque (5) y el sondeo es lineal, se forma un único bloque contiguo de posiciones ocupadas que se va alargando. Cada nueva inserción debe recorrer todo el racimo antes de encontrar hueco, por lo que el número de sondeos crece linealmente con cada inserción (1, 2, 3, 4, 5 sondeos respectivamente). Este es precisamente el inconveniente teórico del sondeo lineal frente a otras estrategias de direccionamiento abierto (sondeo cuadrático o doble hashing), que rompen ese agrupamiento.
En encadenamiento separado, cada cubeta [i] es la cabeza de una lista enlazada; toda clave con h(k) = i se añade a esa lista, sin desplazarse a otras cubetas. Adoptamos el criterio de insertar al final de la lista (preserva el orden de inserción del enunciado y facilita la lectura; insertar al inicio sería igualmente válido si se justifica, pero invertiría el orden).
Resultado:
(Si se hubiera elegido inserción al inicio de la lista, la cubeta 5 quedaría 33 → 5 → 12 → 26 → 19.)
Justificación: todas las claves comparten cubeta, por lo que la tabla degenera en una única lista enlazada de 5 nodos colgando del índice 5, mientras las otras seis cubetas quedan vacías. La estructura se comporta entonces como una lista lineal: la búsqueda de la última clave insertada exige recorrer los 5 elementos, de modo que el coste de búsqueda en el peor caso es O(n). A diferencia del sondeo lineal, el encadenamiento no sufre clustering primario ni puede "llenarse" (admite más de M claves), pero a cambio consume memoria extra en punteros y pierde localidad de caché.
El factor de carga se define como:
\lambda = \frac{n}{M}donde n es el número de claves almacenadas y M el número de cubetas. En este supuesto:
Influencia en el rendimiento (caso ideal de dispersión uniforme):
Direccionamiento abierto / sondeo lineal: el coste medio de una búsqueda con éxito se aproxima a \frac{1}{2}\left(1 + \frac{1}{1-\lambda}\right) y la sin éxito a \frac{1}{2}\left(1 + \frac{1}{(1-\lambda)^2}\right). Como \frac{1}{1-\lambda} crece de forma explosiva cuando \lambda \to 1, el rendimiento se degrada bruscamente al llenarse la tabla. Por eso en sondeo lineal se recomienda mantener \lambda \le 0{,}7\text{–}0{,}75 y aplicar rehashing (reconstruir la tabla con un M mayor, normalmente primo) al superar ese umbral. Además, λ nunca puede exceder 1 (no caben más de M claves).
Encadenamiento separado: el coste medio de búsqueda es del orden de 1 + \frac{\lambda}{2} (con éxito) o 1 + \lambda (sin éxito), es decir, crece linealmente y de forma suave con λ, ya que λ es simplemente la longitud media de las listas. Admite \lambda > 1 sin colapsar, aunque conviene también rehashear para que las listas no se alarguen en exceso.
Conclusión y comparativa:
| Aspecto | Sondeo lineal | Encadenamiento separado |
|---|---|---|
| Almacenamiento | Dentro del propio array | Listas enlazadas externas |
| λ máximo | < 1 (se llena) | sin límite (>1 posible) |
| Degradación con λ alto | Brusca (clustering) | Suave (listas más largas) |
| Memoria | Solo el array | Array + punteros |
| Localidad de caché | Buena | Peor (saltos de punteros) |
El caso de este supuesto es deliberadamente patológico: una función hash que envía todas las claves a la misma cubeta hace que ambas técnicas degeneren en una búsqueda lineal O(n), evidenciando que el rendimiento de una tabla hash depende tanto de una buena función de dispersión como de mantener controlado el factor de carga mediante rehashing. Lo idóneo es elegir M primo, una función hash que distribuya uniformemente y conservar λ por debajo de un umbral razonable.
Genera supuestos de tu especialidad y comunidad en cualquiera de los cuatro formatos, resuélvelos y recibe corrección con nota al instante.