Estructura de datos - Tabla hash

Una tabla hash es una estructura de datos que, mediante una función hash, mapea claves a posiciones específicas en un array, logrando así operaciones de búsqueda, inserción y eliminación con una complejidad temporal promedio de O(1).


Función hash y colisiones hash

Principio de la tabla hash — Mapeo de la función hash
key=1 key=2 key=11 → hash(key) = key % 10 →
[0]
[1] 1,11
[2] 2
[3]
[4]
[5]
[6]
[7]
[8]
[9]

¡Ranura roja = colisión! key=1 y key=11 se mapean a la misma posición

Función hashEl objetivo de diseño de la función hash es convertir cualquier entrada (clave) en un entero dentro de un rango fijo (índice del array).

Una buena función hash debe caracterizarse por una velocidad de cálculo rápida y una distribución uniforme de los resultados.

Sin embargo, debido a que la capacidad de la tabla hash siempre es limitada,la colisión hash—que dos claves diferentes se mapeen a la misma posición— es un fenómeno inevitable.


Métodos de resolución de colisiones

Resolución de colisiones hash — Encadenamiento separado vs. Direccionamiento abierto

Encadenamiento separado

Cada ranura almacena una lista enlazada; las claves en conflicto se agregan al final

Ventajas: implementación simple, eliminación conveniente

Desventajas: sobrecarga de punteros, no es amigable con la caché

El factor de carga puede superar 1.0

Direccionamiento abierto

Ante una colisión, se sondea la siguiente posición vacía

Ventajas: sin punteros, amigable con la caché

Desventajas: la eliminación requiere marcado diferido

El factor de carga debe ser ≤ 0.7

MétodoPrincipioVentajasDesventajas
Encadenamiento separadoCada ranura almacena una lista enlazada; las claves en conflicto se agregan a la listaImplementación simple, eliminación conveniente, el factor de carga puede ser mayor que 1Sobrecarga adicional de punteros, no es amigable con la caché
Direccionamiento abiertoAnte una colisión, se busca la siguiente posición vacía en el array según las reglas de sondeoSin necesidad de punteros, amigable con la cachéEliminación compleja (requiere eliminación diferida), el factor de carga debe controlarse

En el direccionamiento abierto, al eliminar un elemento no se puede simplemente vaciar la ranura, de lo contrario se rompería la cadena de búsqueda de los elementos posteriores. La práctica habitual es utilizar la "eliminación diferida": marcar la posición como "eliminada" en lugar de "vacía".


Implementación del método de encadenamiento separado

Ejemplo

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10 /* Capacidad de la tabla hash */

/* Nodo de la tabla hash */
struct HashNode {
    int key;
    int value;
    struct HashNode* next;  /* Apunta al siguiente nodo de la misma ranura */
};

/* Función hash: método simple de módulo */
int hashFunc(int key) {
    return key % TABLE_SIZE;
}

/* Insertar par clave-valor (encadenamiento separado)
Complejidad temporal: O(1) promedio, O(n) en el peor caso (todas las claves mapeadas a la misma ranura) */

void insert(struct HashNode* table[], int key, int value) {
    int index = hashFunc(key);
    struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = table[index];  /* Inserción por cabeza */
    table[index] = newNode;
}

/* Búsqueda: obtener el valor según la clave
Primero se calcula el valor hash para localizar la ranura, luego se recorre la lista enlazada para encontrar la clave coincidente */

int search(struct HashNode* table[], int key) {
    int index = hashFunc(key);
    struct HashNode* cur = table[index];
    while (cur != NULL) {
        if (cur->key == key) {
            return cur->value;  /* Encontrado */
        }
        cur = cur->next;
    }
    return -1;  /* No encontrado */
}

int main() {
    struct HashNode* table[TABLE_SIZE] = {NULL};  /* Inicializar todas las ranuras como vacías */

    insert(table, 1, 100);   /* key=1, value=100, index=1 */
    insert(table, 2, 200);   /* key=2, value=200, index=2 */
    insert(table, 11, 300);  /* key=11, value=300, index=1 — ¡colisión con key=1! */

    printf("key=1 → %d\n", search(table, 1));   /* Salida: 100 */
    printf("key=2 → %d\n", search(table, 2));   /* Salida: 200 */
    printf("key=11 → %d\n", search(table, 11)); /* Salida: 300 (el encadenamiento separado manejó correctamente la colisión) */
    printf("key=99 → %d\n", search(table, 99)); /* Salida: -1 (no encontrado) */
    return 0;
}

Escenarios de aplicación

EscenarioDescripción
Diccionario/MapaAlmacenamiento y búsqueda rápida de pares clave-valor, como dict de Python, HashMap de Java
Sistema de cachéImplementación subyacente de sistemas de caché como LRU Cache
Índice de base de datosLos índices hash permiten búsquedas O(1) en consultas de igualdad
Tabla de símbolos del compiladorRegistra el mapeo de nombres de variables, nombres de funciones y sus tipos
Otras extensiones