2 - Concepto de funcion hash

Vision general

Una funcion hash convierte una clave de longitud variable en un entero reducido que actua como indice dentro de una tabla. Su calidad determina la velocidad y estabilidad de estructuras como diccionarios o sets. En esta seccion repasamos sus propiedades y mostramos implementaciones sencillas en C.

2.1 ¿Que es una funcion hash?

Es una funcion determinista que toma una clave (entero, cadena o estructura) y devuelve un valor numerico de rango acotado. Ese valor se usa para ubicar el elemento en una tabla hash.

2.2 Propiedades deseables de una buena funcion hash

  • Uniforme: reparte claves distintas de forma pareja entre los buckets.
  • Determinista: la misma clave siempre produce el mismo hash.
  • Rapida: 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 Distribucion 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 numero de elementos por bucket.

2.4 Determinismo y reproducibilidad

Para que la tabla hash funcione, la funcion 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 formula 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:

#define TAM_TABLA 1024

static unsigned long hash_entero(int clave) {
  const unsigned long constante = 2654435761u; /* fraccion dorada en 32 bits */
  unsigned long mezcla = (unsigned long)clave * constante;
  return mezcla % TAM_TABLA;
}

La multiplicacion por la constante (derivada de la fraccion dorada, 232/φ ≈ 2654435761) distribuye los valores de manera casi uniforme antes del modulo.

2.6 Funciones hash para cadenas en C

Las cadenas requieren recorrer cada caracter y mezclarlo con el acumulador. Una variante ligera es FNV-1a, que combina XOR y multiplicacion:

#define OFFSET_BASIS 2166136261u
#define FNV_PRIME 16777619u

static unsigned long hash_cadena_fnv(const char *clave, unsigned long tam_tabla) {
  unsigned long hash = OFFSET_BASIS;
  int c;
  while ((c = *clave++) != 0) {
    hash ^= (unsigned long)c;
    hash *= FNV_PRIME;
  }
  return hash % tam_tabla;
}

FNV-1a es rapido, 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 busqueda.
  • Sesgo por prefijos o sufijos: si solo mezcla al inicio o al final, cadenas similares terminan juntas.
  • Costos altos: usar divisiones, operaciones criptograficas o ciclos extensos puede hacer lento cada acceso.
  • Dependencia del conjunto: funciones que parecen buenas pueden fallar con dominios concretos (por ejemplo, numeros consecutivos), por eso conviene probar con datos reales.

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

Retornar