2 - Concepto de función hash

Visión general

Una función hash convierte una clave de longitud variable en un entero reducido que actúa como índice dentro de una tabla. Su calidad determina la velocidad y estabilidad de estructuras como diccionarios o sets. En esta sección repasamos sus propiedades y mostramos implementaciones sencillas en Python.

2.1 ¿Qué es una función hash?

Es una función determinista que toma una clave (entero, cadena o estructura) y devuelve un valor numérico de rango acotado. Ese valor se usa para ubicar el elemento en una tabla hash.

2.2 Propiedades deseables de una buena función hash

• Uniforme: reparte claves distintas de forma pareja entre los buckets.
• Determinista: la misma clave siempre produce el mismo hash.
• Rápida: evita operaciones costosas (no usa divisiones repetidas ni ciclos largos).
• Mezcla suficiente: pequeños cambios en la clave alteran varios bits del resultado.
• Simple de implementar: favorece el mantenimiento y las pruebas.

2.3 Distribución uniforme

Se busca que todas las posiciones de la tabla reciban cantidades similares de claves. Si algunas posiciones concentran demasiados elementos, las colisiones aumentan y el tiempo promedio deja de ser O(1). Evaluar la uniformidad implica medir el factor de carga y el número de elementos por bucket.

2.4 Determinismo y reproducibilidad

Para que la tabla hash funcione, la función debe producir siempre el mismo valor para la misma clave en todas las ejecuciones. Esto permite guardar, buscar y eliminar de forma coherente y reproducible. Variar la semilla o la fórmula solo se hace de manera controlada (por ejemplo al rehashing).

2.5 Funciones hash para enteros

Para enteros suele bastar con una mezcla multiplicativa que preserve bits significativos y reduzca patrones. Ejemplo:

TAM_TABLA = 1024

def hash_entero(clave):
  constante = 2654435761  # fracción dorada en 32 bits
  mezcla = clave * constante
  return mezcla % TAM_TABLA

La multiplicación por la constante (derivada de la fracción dorada, 2³²/φ ≈ 2654435761) distribuye los valores de manera casi uniforme antes del módulo.

2.6 Funciones hash para cadenas en Python

Las cadenas requieren recorrer cada carácter y mezclarlo con el acumulador. Una variante ligera es FNV-1a, que combina XOR y multiplicación:

OFFSET_BASIS = 2166136261
FNV_PRIME = 16777619

def hash_cadena_fnv(clave, tam_tabla):
  hash_valor = OFFSET_BASIS
  for caracter in clave:
    hash_valor ^= ord(caracter)
    hash_valor *= FNV_PRIME
  return hash_valor % tam_tabla

FNV-1a es rápido, determinista y mezcla bien caracteres secuenciales, lo que reduce agrupamientos al usar tablas moderadas.

2.7 Problemas con funciones hash malas

• Clustering: demasiadas claves caen en pocos buckets, elevando el tiempo de búsqueda.
• Sesgo por prefijos o sufijos: si solo mezcla al inicio o al final, cadenas similares terminan juntas.
• Costos altos: usar divisiones, operaciones criptográficas o ciclos extensos puede hacer lento cada acceso.
• Dependencia del conjunto: funciones que parecen buenas pueden fallar con dominios concretos (por ejemplo, números consecutivos), por eso conviene probar con datos reales.

Elegir o ajustar la función hash es un paso central para mantener el rendimiento de la tabla sin aumentar su tamaño de forma innecesaria.