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 Python 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.
TAM_TABLA = 1024
def hash_cadena(clave):
hash_valor = 5381
for caracter in clave:
hash_valor = ((hash_valor << 5) + hash_valor) + ord(caracter) # hash * 33 + caracter
return hash_valor % TAM_TABLA # asegura indice dentro del arrayLa 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_valor = 5381 inicializa el acumulador con una constante no nula que reduce patrones repetitivos.for caracter in clave recorre la cadena caracter por caracter.hash_valor = ((hash_valor << 5) + hash_valor) + ord(caracter) equivale a hash_valor * 33 + ord(caracter): desplaza 5 bits para multiplicar por 32, suma el valor anterior (32 + 1 = 33) y agrega el codigo Unicode del caracter, acumulando influencia de cada simbolo.return hash_valor % 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.