Estructuras de Datos

0x0042 INICIALIZANDO...
0x7ffe-stack
*p = malloc(sizeof(Node))
0x3b2a - heap
ptr -> next = NULL
Unidad 11

Tablas Hash

Imagina una biblioteca donde no tienes que buscar el libro por orden alfabético. Simplemente tienes una fórmula matemática que te dice exactamente en qué estante y posición está. Eso es el Hashing: transformar una clave de búsqueda en una dirección de memoria directa para obtener acceso en tiempo constante O(1).

Imagen 43. Funcionamiento conceptual de una Tabla Hash

Imagen 43. Funcionamiento conceptual de una Tabla Hash

Diagrama de flujo básico: Muestra entradas (strings/nombres) pasando por una "Caja Negra" (Función Hash) que escupe números (índices) correspondientes a casillas en un arreglo.

11.1 La Magia del O(1): Hashing
Mirar en YouTube

Una función hash debe ser determinista: para la misma entrada, siempre debe dar el mismo índice. Además, debe ser rápida de calcular y distribuir los datos uniformemente. La operación matemática estrella aquí es el Módulo (%).

Imagen 44. Uso del operador Módulo para índices

Imagen 44. Uso del operador Módulo para índices

Visualización del ajuste: Si el hash crudo es 1,000,500 pero mi array es de tamaño 10, la operación 1,000,500 % 10 ubica el dato en la posición 0. El módulo garantiza que nunca nos salgamos del array.

main.cpp
// Función simple para sumar valores ASCII
unsigned int hash(char *key, int table_size) {
    unsigned int sum = 0;
    for (int i = 0; key[i] != '\0'; i++) {
        sum += key[i];
    }
    return sum % table_size; // El módulo es vital
}
// Función simple para sumar valores ASCII
unsigned int hash(char *key, int table_size) {
    unsigned int sum = 0;
    for (int i = 0; key[i] != '\0'; i++) {
        sum += key[i];
    }
    return sum % table_size; // El módulo es vital
}
11.2 Funciones Hash y el Módulo
Mirar en YouTube

Es matemáticamente imposible evitar que dos llaves diferentes generen el mismo índice (ej: "roma" y "amor" podrían sumar lo mismo). Esto se llama colisión. Para resolverlo, la técnica más común y robusta es el "Encadenamiento" (Chaining).

Imagen 45. Resolución de colisiones mediante Listas Enlazadas

Imagen 45. Resolución de colisiones mediante Listas Enlazadas

Diagrama de Encadenamiento: Muestra el Array principal, pero en lugar de guardar el dato directamente, cada casilla guarda un puntero a una Lista Enlazada donde se acumulan las colisiones.

11.3 Manejo de Colisiones
Mirar en YouTube

Para implementar una Tabla Hash con encadenamiento en C, necesitamos un Array de Punteros. Cada puntero será la "cabeza" de una lista enlazada. Inicialmente, todos apuntan a NULL.

main.cpp
#define TABLE_SIZE 10

struct Nodo {
    char clave[50];
    int valor;
    struct Nodo* siguiente;
};

// La tabla es un array de punteros a Nodo
struct Nodo* tablaHash[TABLE_SIZE];

void init() {
    for(int i=0; i<TABLE_SIZE; i++)
        tablaHash[i] = NULL;
}
#define TABLE_SIZE 10

struct Nodo {
    char clave[50];
    int valor;
    struct Nodo* siguiente;
};

// La tabla es un array de punteros a Nodo
struct Nodo* tablaHash[TABLE_SIZE];

void init() {
    for(int i=0; i<TABLE_SIZE; i++)
        tablaHash[i] = NULL;
}
Imagen 46. Estructura en memoria: Array de Punteros

Imagen 46. Estructura en memoria: Array de Punteros

Arquitectura en RAM: Visualización del "Array de cabezas". Muestra cómo la tabla principal reside en memoria estática o dinámica, apuntando a nodos dispersos en el Heap.

11.4 Codificando una Tabla Hash en C
Mirar en YouTube
Volver al nivel