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
¡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
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étodo | Principio | Ventajas | Desventajas |
|---|---|---|---|
| Encadenamiento separado | Cada ranura almacena una lista enlazada; las claves en conflicto se agregan a la lista | Implementación simple, eliminación conveniente, el factor de carga puede ser mayor que 1 | Sobrecarga adicional de punteros, no es amigable con la caché |
| Direccionamiento abierto | Ante una colisión, se busca la siguiente posición vacía en el array según las reglas de sondeo | Sin 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 <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
| Escenario | Descripción |
|---|---|
| Diccionario/Mapa | Almacenamiento 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 datos | Los índices hash permiten búsquedas O(1) en consultas de igualdad |
| Tabla de símbolos del compilador | Registra el mapeo de nombres de variables, nombres de funciones y sus tipos |