C Academy · Lección

Funciones hash

Asigne claves a buckets

Funciones hash es una lección gratuita de C Academy en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de C Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de C Academy incluye 4 lecciones en total.

Qué es una función hash

Una función hash toma una clave y produce un índice entero en un array de cubetas. Es el núcleo de una tabla hash: convierte claves arbitrarias, como cadenas, en posiciones de array de acceso rápido.

Entrada: una clave (cadena, entero, etc.)
Salida: un índice de cubeta en [0, capacity)

Propiedades de una buena función hash

Una buena función hash es determinista, rápida y distribuye las claves de forma uniforme entre las cubetas.

La misma clave siempre produce el mismo índice
Pequeños cambios en la clave provocan grandes cambios en el índice (efecto avalancha)
Pocas colisiones con datos habituales

Asignar a una cubeta

Una vez calculado el valor hash sin procesar, asígnelo a una posición de la tabla mediante el operador módulo: index = hash % capacity.

Utilice un tipo unsigned para que el módulo nunca produzca un índice negativo.

#include <stdio.h>

int main(void) {
    unsigned long hash = 123456789UL;
    unsigned capacity = 16;
    unsigned index = (unsigned)(hash % capacity);
    printf("bucket = %u\n", index);
    return 0;
}

Una función hash de suma sencilla

La función hash de cadenas más sencilla suma los valores de sus caracteres. Es fácil de implementar, pero distribuye mal las claves porque las palabras con las mismas letras producen colisiones.

Ejecútela para observar cómo dos cadenas distintas producen valores hash cercanos.

#include <stdio.h>

unsigned long sum_hash(const char *s) {
    unsigned long h = 0;
    while (*s) h += (unsigned char)*s++;
    return h;
}

int main(void) {
    printf("%lu\n", sum_hash("abc"));
    printf("%lu\n", sum_hash("cba"));
    return 0;
}

La función hash DJB2

DJB2 es una función hash de cadenas clásica y bien distribuida, creada por Daniel J. Bernstein. Comienza en 5381 y utiliza hash * 33 + c.

La combinación de multiplicación y suma mezcla los bits mucho mejor que una suma simple.

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*s++))
        h = ((h << 5) + h) + c; /* h * 33 + c */
    return h;
}

int main(void) {
    printf("%lu\n", djb2("hello"));
    printf("%lu\n", djb2("world"));
    return 0;
}

La función hash FNV-1a

FNV-1a aplica XOR a cada byte y, después, multiplica por un número primo. Es sencilla, rápida y se utiliza ampliamente.

Orden: primero XOR y después multiplicación (esa es la variante 1a).

#include <stdio.h>

unsigned long fnv1a(const char *s) {
    unsigned long h = 1469598103934665603UL;
    while (*s) {
        h ^= (unsigned char)*s++;
        h *= 1099511628211UL;
    }
    return h;
}

int main(void) {
    printf("%lu\n", fnv1a("key1"));
    printf("%lu\n", fnv1a("key2"));
    return 0;
}

Aplicar hash a enteros

Las claves enteras también necesitan una mezcla, porque usar solo x % capacity agrupa las claves cuando comparten patrones. Una mezcla multiplicativa (Knuth) distribuye los bits.

#include <stdio.h>

unsigned hash_int(unsigned x, unsigned cap) {
    x *= 2654435761u; /* Knuth multiplicative */
    return x % cap;
}

int main(void) {
    for (unsigned i = 0; i < 5; i++)
        printf("%u -> %u\n", i, hash_int(i, 8));
    return 0;
}

Capacidades potencia de dos

Cuando la capacidad es una potencia de dos, puede sustituir % capacity por una operación AND bit a bit rápida: hash & (capacity - 1).

Esto funciona únicamente porque los bits bajos de una potencia de dos menos uno forman una máscara completa.

#include <stdio.h>

int main(void) {
    unsigned long hash = 123456789UL;
    unsigned capacity = 16; /* power of two */
    unsigned index = (unsigned)(hash & (capacity - 1));
    printf("bucket = %u\n", index);
    return 0;
}

Por qué el módulo puede ser lento

El operador % se compila como una instrucción de división, que es más lenta que AND. Esto importa en bucles estrechos.

Tabla con tamaño potencia de dos: utilice una máscara AND
Tabla con tamaño primo: utilice el módulo (ofrece una mejor distribución con funciones hash débiles)

Las colisiones son inevitables

Según el principio del palomar, asignar muchas claves a un número menor de cubetas garantiza que haya colisiones. Una buena función hash las minimiza, pero no puede eliminarlas.

En la siguiente lección se explica cómo resolver las colisiones.

Demostración de distribución

Contemos cómo DJB2 distribuye varias claves entre 8 cubetas. Las buenas funciones hash las distribuyen de manera bastante uniforme.

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
    return h;
}

int main(void) {
    const char *keys[] = {"apple", "banana", "cherry", "date"};
    int counts[8] = {0};
    for (int i = 0; i < 4; i++)
        counts[djb2(keys[i]) % 8]++;
    for (int i = 0; i < 8; i++)
        printf("bucket %d: %d\n", i, counts[i]);
    return 0;
}

Comprobación rápida

Compruebe su comprensión de los conceptos básicos de las funciones hash.

Resumen

Ha aprendido qué hace una función hash y cómo asignar claves a cubetas.

Las buenas funciones hash son deterministas, rápidas y uniformes
DJB2 y FNV-1a son funciones hash de cadenas sólidas
Asigne mediante % capacity o mediante & (capacity-1) con potencias de dos
Utilice tipos unsigned; las colisiones son inevitables

Preguntas frecuentes

¿La lección «Funciones hash» es gratis?

Sí — el texto completo de «Funciones hash» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de C Academy, actualiza a CoddyKit PRO. El curso de C Academy incluye 4 lecciones en total.

¿Qué aprenderé en «Funciones hash»?

Asigne claves a buckets Practicas C Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar C Academy?

No se requiere experiencia previa. C Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.

¿Cuánto tiempo toma la lección «Funciones hash»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de C Academy?

Sí. Cada lección de C Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

← Volver a C Academy