El hashing permite mapear claves de longitud variable a posiciones fijas dentro de una estructura, usualmente un array. El objetivo es obtener accesos promedio O(1) para insertar, buscar o eliminar, siempre y cuando la funcion hash disperse las claves de manera uniforme y la carga de la tabla se mantenga controlada.
Antes de codificar una tabla hash en C necesitamos comprender los conceptos base: que hace la funcion hash, que problema resuelve frente al acceso directo, en que estructuras se aplica y donde aparecen sus limitaciones.
Hashing es el proceso de transformar una clave en un valor entero reducido (el hash o indice) mediante una funcion determinista. Ese valor indica la posicion donde almacenar o buscar el elemento en una tabla.
#define TAM_TABLA 1024
static unsigned long hash_cadena(const char *clave) {
unsigned long hash = 5381;
int c;
while ((c = *clave++) != 0) {
hash = ((hash << 5) + hash) + (unsigned long)c; /* hash * 33 + c */
}
return hash % TAM_TABLA; /* asegura indice dentro del array */
}La funcion anterior usa la variante djb2 propuesta por Daniel J. Bernstein, popular por su sencillez y buen comportamiento generalista en cadenas cortas. Devuelve un indice entre 0 y TAM_TABLA - 1. Aun sin almacenar nada, ilustra la idea central: reducir la clave a un espacio finito y utilizable.
Detalle de cada linea:
hash = 5381; inicializa el acumulador con una constante no nula que reduce patrones repetitivos.while ((c = *clave++) != 0) recorre la cadena hasta encontrar el terminador \0, avanzando el puntero.hash = ((hash << 5) + hash) + (unsigned long)c; equivale a hash * 33 + c: desplaza 5 bits para multiplicar por 32, suma el valor anterior (32 + 1 = 33) y agrega el byte de la letra, acumulando influencia de cada caracter.return hash % TAM_TABLA; ajusta el valor para que siempre sea un indice valido entre 0 y TAM_TABLA - 1.Sin hashing, buscar un elemento por su clave en una coleccion desordenada requiere recorrerla completa (O(n)) o mantenerla ordenada para aplicar búsqueda binaria (O(log n)). El hashing evita ambos escenarios al llevar la clave directamente a un bucket (un contenedor donde se almacenan los elementos asignados a una misma posicion del hash), eliminando recorridos y manteniendo un costo promedio constante.
Aunque cada estructura define operaciones propias, todas comparten la misma necesidad: localizar rápido una clave sin recorrer toda la coleccion.
El acceso directo supone que la clave ya es un indice valido (por ejemplo, un DNI que coincide con la posicion de un array gigante). Esto consume mucha memoria si el dominio de claves es amplio o disperso. El hashing, en cambio, aplica una funcion que comprime el dominio a un tamaño razonable de tabla y acepta cierto riesgo de colision.
En la practica se decide entre ambos segun el rango de claves, la memoria disponible y la necesidad de crecer o decrecer la estructura.
Comprender estas limitaciones desde el inicio permite diseñar pruebas y ajustes que mantengan la tabla sana a medida que crece.