Ayuda | Tabla Hash

Tabla Hash

Descripcion del TAD

Tabla hash de capacidad fija con claves y valores enteros, usando encadenamiento separado. La animacion sigue el indice hash, la normalizacion de negativos, las colisiones y la memoria. La Tabla Hash mapea claves a buckets mediante una funcion hash. La simulacion muestra colisiones, encadenamiento y eventos de rehash al crecer la carga.

Controles de ejecucion paso a paso

Checkbox Interpretar codigo paso a paso: activado muestra toda la traza; desactivado aplica solo el resultado final.
Botones de ejecucion: Reproducir y Reiniciar.
Navegacion por traza: Anterior paso y Siguiente paso.
Velocidad de simulacion: slider de -2x a +2x (0.00x = 1.00x real).
En modo rapido (checkbox desactivado), el resultado visual final debe coincidir con el ultimo estado de la traza interpretada.
Al llegar al ultimo paso, Siguiente paso se bloquea hasta cambiar entradas/operacion; Anterior paso se habilita solo cuando ya avanzaste.

Operaciones soportadas

Guía de aprendizaje

Objetivo: Explicar cómo el residuo C selecciona un bucket y cómo la cadena de punteros resuelve una colisión.

Estrategia: Calcular índice, normalizar negativos, recorrer actual/anterior y enlazar o liberar solo en la rama ejecutada.

Memoria C: Insertar una clave nueva reserva un THNodo con malloc; actualizar no reserva. Eliminar, vaciar y destruir liberan memoria con free.

Invariantes

Cada clave está en el bucket normalizado por clave % capacidad.
Las claves son únicas.
cantidad coincide con los nodos alcanzables.
Toda cadena termina en NULL y no tiene ciclos.

Complejidad

mejor: Θ(1)
promedio: Θ(1 + α) con distribución aproximadamente uniforme
peor: Θ(n) si todas las claves colisionan

Aplicaciones

Índices por identificador
tablas de símbolos
cachés con clave entera
conteo y asociación de datos

Errores frecuentes

Confundir el módulo de Python con el residuo negativo de C.
Suponer que la tabla se redimensiona automáticamente.
Olvidar actualizar anterior al eliminar un nodo intermedio.
Usar un nodo después de free.

Glosario

Bucket: Celda del arreglo que apunta a una cadena.
Colisión: Dos claves diferentes seleccionan el mismo bucket.
Factor de carga α: cantidad / capacidad.
Encadenamiento separado: Estrategia que conserva las colisiones en listas enlazadas.
Residuo C: Resultado de %, que puede ser negativo y se normaliza antes de indexar.
NULL: Puntero nulo que marca el final de una cadena.
Capacidad fija: Número de buckets que no cambia durante la vida de esta implementación.

Guía docente

Pida predecir el bucket antes de mostrar la traza.
Use capacidad 1 como contraejemplo de distribución.
Compare las mismas claves en 3, 7 y 17 sin cambiar la entrada.
Solicite explicar anterior->siguiente antes de eliminar un nodo intermedio.
Evalúe la justificación mediante la línea C y el invariante, no solo el resultado.

Teclado

Alt+→: siguiente paso.
Alt+←: paso anterior.
Alt+Inicio: inicio.
Alt+Fin: final.
Alt+P: pausar.

th_inicializar
th_insertar
th_buscar
th_contiene
th_eliminar
th_formatear
th_formatear
th_formatear
th_estadisticas
th_vaciar

Operaciones pendientes / restricciones

El TAD no expone tecnicas alternativas de hashing (lineal/cuadratico/doble hash).
La capacidad es fija: no hay resize ni rehash automático en el C interpretado.

Estructura del TAD en C

typedef struct th_nodo {
    int clave;                 
    int valor;                 
    struct th_nodo *siguiente; 
} THNodo;

typedef struct {
    THNodo **buckets; 
    int capacidad;    
    int cantidad;     
} TablaHash;

typedef struct {
    int capacidad;        
    int cantidad;         
    int buckets_ocupados; 
    int colisiones;       
    float factor_carga;  
} THEstadisticas;

Metodos del TAD en C

Codigo C: create_table

Inicializa la tabla hash con su capacidad y parametros de control de carga.

/**
 * @brief Inicializa la tabla hash.
 * @param[out] tabla Puntero a la tabla hash.
 * @param[in] capacidad Capacidad (número de buckets) de la tabla.
 */
void th_inicializar(TablaHash *tabla, int capacidad) {
    if (!tabla || capacidad <= 0) return;
    
    tabla->capacidad = capacidad;
    tabla->cantidad = 0;
    tabla->buckets = (THNodo **)malloc(capacidad * sizeof(THNodo *));
    
    if (tabla->buckets) {
        for (int i = 0; i < capacidad; i++) {
            tabla->buckets[i] = NULL;
        }
    } else {
        tabla->capacidad = 0; // Error de memoria
    }
}

Codigo C: insert

Calcula bucket hash e inserta/actualiza clave-valor, gestionando colisiones por encadenamiento.

/**
 * @brief Inserta un par clave-valor, actualizando el valor si la clave existe.
 * @param[in,out] tabla Puntero a la tabla hash.
 * @param[in] clave Clave a insertar.
 * @param[in] valor Valor asociado a la clave.
 * @return true si se insertó o actualizó correctamente, false en error.
 */
bool th_insertar(TablaHash *tabla, int clave, int valor) {
    if (!tabla || !tabla->buckets || tabla->capacidad <= 0) return false;
    
    int indice = th_indice(tabla, clave);
    THNodo *actual = tabla->buckets[indice];
    
    // Buscar si ya existe para actualizar
    while (actual != NULL) {
        if (actual->clave == clave) {
            actual->valor = valor;
            return true;
        }
        actual = actual->siguiente;
    }
    
    // No existe, insertar al principio del bucket
    THNodo *nuevo = (THNodo *)malloc(sizeof(THNodo));
    if (!nuevo) return false;
    
    nuevo->clave = clave;
    nuevo->valor = valor;
    nuevo->siguiente = tabla->buckets[indice];
    tabla->buckets[indice] = nuevo;
    tabla->cantidad++;
    
    return true;
}

int th_indice(const TablaHash *tabla, int clave) {
    if (!tabla || tabla->capacidad <= 0) return -1;
    int indice = clave % tabla->capacidad;
    if (indice < 0) {
        indice += tabla->capacidad;
    }
    return indice;
}

Codigo C: get

Busca una clave y retorna su valor asociado si existe en la tabla.

/**
 * @brief Busca el valor asociado a una clave.
 * @param[in] tabla Puntero a la tabla hash constante.
 * @param[in] clave Clave a buscar.
 * @param[out] valor Puntero donde se almacenará el valor si se encuentra.
 * @return true si se encontró la clave, false si no.
 */
bool th_buscar(const TablaHash *tabla, int clave, int *valor) {
    if (!tabla || !tabla->buckets || tabla->capacidad <= 0 || !valor) return false;
    
    int indice = th_indice(tabla, clave);
    THNodo *actual = tabla->buckets[indice];
    
    while (actual != NULL) {
        if (actual->clave == clave) {
            *valor = actual->valor;
            return true;
        }
        actual = actual->siguiente;
    }
    
    return false;
}

int th_indice(const TablaHash *tabla, int clave) {
    if (!tabla || tabla->capacidad <= 0) return -1;
    int indice = clave % tabla->capacidad;
    if (indice < 0) {
        indice += tabla->capacidad;
    }
    return indice;
}

Codigo C: contains

Verifica existencia de una clave sin extraer ni modificar su valor.

/**
 * @brief Verifica si una clave existe en la tabla.
 * @param[in] tabla Puntero a la tabla hash.
 * @param[in] clave Clave a verificar.
 * @return true si la clave existe, false si no.
 */
bool th_contiene(const TablaHash *tabla, int clave) {
    int dummy_valor;
    return th_buscar(tabla, clave, &dummy_valor);
}

int th_indice(const TablaHash *tabla, int clave) {
    if (!tabla || tabla->capacidad <= 0) return -1;
    int indice = clave % tabla->capacidad;
    if (indice < 0) {
        indice += tabla->capacidad;
    }
    return indice;
}

/**
 * @brief Busca el valor asociado a una clave.
 * @param[in] tabla Puntero a la tabla hash constante.
 * @param[in] clave Clave a buscar.
 * @param[out] valor Puntero donde se almacenará el valor si se encuentra.
 * @return true si se encontró la clave, false si no.
 */
bool th_buscar(const TablaHash *tabla, int clave, int *valor) {
    if (!tabla || !tabla->buckets || tabla->capacidad <= 0 || !valor) return false;
    
    int indice = th_indice(tabla, clave);
    THNodo *actual = tabla->buckets[indice];
    
    while (actual != NULL) {
        if (actual->clave == clave) {
            *valor = actual->valor;
            return true;
        }
        actual = actual->siguiente;
    }
    
    return false;
}

Codigo C: remove

Elimina una clave del bucket correspondiente y ajusta enlaces de la cadena.

/**
 * @brief Elimina una clave de la tabla hash.
 * @param[in,out] tabla Puntero a la tabla hash.
 * @param[in] clave Clave a eliminar.
 * @return true si fue eliminada, false si no existía o error.
 */
bool th_eliminar(TablaHash *tabla, int clave) {
    if (!tabla || !tabla->buckets || tabla->capacidad <= 0) return false;
    
    int indice = th_indice(tabla, clave);
    THNodo *actual = tabla->buckets[indice];
    THNodo *anterior = NULL;
    
    while (actual != NULL) {
        if (actual->clave == clave) {
            if (anterior == NULL) {
                tabla->buckets[indice] = actual->siguiente;
            } else {
                anterior->siguiente = actual->siguiente;
            }
            free(actual);
            tabla->cantidad--;
            return true;
        }
        anterior = actual;
        actual = actual->siguiente;
    }
    
    return false;
}

int th_indice(const TablaHash *tabla, int clave) {
    if (!tabla || tabla->capacidad <= 0) return -1;
    int indice = clave % tabla->capacidad;
    if (indice < 0) {
        indice += tabla->capacidad;
    }
    return indice;
}

Codigo C: keys

Devuelve todas las claves activas de la tabla.

/* Este TAD en C no expone un metodo que retorne solo claves como arreglo. */
/* Se puede recorrer la tabla completa usando th_formatear. */
char buffer[2048];
th_formatear(&tabla, buffer, sizeof(buffer));

Codigo C: values

Devuelve todos los valores almacenados actualmente.

/* Este TAD en C no expone un metodo que retorne solo valores como arreglo. */
/* Se puede recorrer la tabla completa usando th_formatear. */
char buffer[2048];
th_formatear(&tabla, buffer, sizeof(buffer));

Codigo C: items

Devuelve pares clave-valor para inspeccion completa del contenido.

/* Consulta didactica de pares clave:valor por bucket. */
char buffer[2048];
th_formatear(&tabla, buffer, sizeof(buffer));

Codigo C: stats

Calcula metricas de carga, buckets usados y colisiones para diagnostico.

/* Estadisticas del TAD tabla hash. */
THEstadisticas stats = th_estadisticas(&tabla);
char texto[512];
th_formatear_estadisticas(&tabla, texto, sizeof(texto));

Codigo C: clear

Limpia la tabla completa y reinicia su estado interno.

/**
 * @brief Elimina todos los elementos manteniendo la capacidad de la tabla.
 * @param[in,out] tabla Puntero a la tabla hash.
 */
void th_vaciar(TablaHash *tabla) {
    if (!tabla || !tabla->buckets) return;
    
    for (int i = 0; i < tabla->capacidad; i++) {
        THNodo *actual = tabla->buckets[i];
        while (actual != NULL) {
            THNodo *siguiente = actual->siguiente;
            free(actual);
            actual = siguiente;
        }
        tabla->buckets[i] = NULL;
    }
    tabla->cantidad = 0;
}

Codigo C: destroy_table

Este metodo del TAD Tabla Hash debe interpretarse respetando condicionales, ciclos, returns y actualizacion del estado visual segun el flujo real del codigo C.

/**
 * @brief Destruye la tabla hash liberando toda su memoria.
 * @param[in,out] tabla Puntero a la tabla hash.
 */
void th_destruir(TablaHash *tabla) {
    if (!tabla || !tabla->buckets) return;
    
    th_vaciar(tabla);
    free(tabla->buckets);
    tabla->buckets = NULL;
    tabla->capacidad = 0;
    tabla->cantidad = 0;
}

/**
 * @brief Elimina todos los elementos manteniendo la capacidad de la tabla.
 * @param[in,out] tabla Puntero a la tabla hash.
 */
void th_vaciar(TablaHash *tabla) {
    if (!tabla || !tabla->buckets) return;
    
    for (int i = 0; i < tabla->capacidad; i++) {
        THNodo *actual = tabla->buckets[i];
        while (actual != NULL) {
            THNodo *siguiente = actual->siguiente;
            free(actual);
            actual = siguiente;
        }
        tabla->buckets[i] = NULL;
    }
    tabla->cantidad = 0;
}

Codigo C: clear_and_reinit

Este metodo del TAD Tabla Hash debe interpretarse respetando condicionales, ciclos, returns y actualizacion del estado visual segun el flujo real del codigo C.

/**
 * @brief Destruye la tabla hash liberando toda su memoria.
 * @param[in,out] tabla Puntero a la tabla hash.
 */
void th_destruir(TablaHash *tabla) {
    if (!tabla || !tabla->buckets) return;
    
    th_vaciar(tabla);
    free(tabla->buckets);
    tabla->buckets = NULL;
    tabla->capacidad = 0;
    tabla->cantidad = 0;
}

/* Reinicio recomendado del TAD conservando una capacidad valida. */
/**
 * @brief Inicializa la tabla hash.
 * @param[out] tabla Puntero a la tabla hash.
 * @param[in] capacidad Capacidad (número de buckets) de la tabla.
 */
void th_inicializar(TablaHash *tabla, int capacidad) {
    if (!tabla || capacidad <= 0) return;
    
    tabla->capacidad = capacidad;
    tabla->cantidad = 0;
    tabla->buckets = (THNodo **)malloc(capacidad * sizeof(THNodo *));
    
    if (tabla->buckets) {
        for (int i = 0; i < capacidad; i++) {
            tabla->buckets[i] = NULL;
        }
    } else {
        tabla->capacidad = 0; // Error de memoria
    }
}

Ir a la visualizacion