Funções de hash
Mapeando chaves para buckets.
Funções de hash é uma aula grátis de C Academy no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de C Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de C Academy inclui 4 aulas no total.
O que é uma função de dispersão
Uma função de dispersão recebe uma chave e produz um índice inteiro para um vetor de compartimentos. Ela é o núcleo de uma tabela de dispersão, transformando chaves arbitrárias, como strings, em posições rápidas no vetor.
- Entrada: uma chave (string, inteiro etc.)
- Saída: um índice de compartimento em
[0, capacity)
Propriedades de uma boa dispersão
Uma boa função de dispersão é determinística, rápida e distribui as chaves de maneira uniforme entre os compartimentos.
- A mesma chave sempre produz o mesmo índice
- Pequenas mudanças na chave causam grandes mudanças no índice (efeito avalanche)
- Poucas colisões para dados comuns
Mapeando para um compartimento
Depois de calcular um valor bruto de dispersão, mapeie-o para a tabela usando o operador módulo: index = hash % capacity.
Use um tipo unsigned para garantir que o módulo nunca produza um í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;
}Uma função de dispersão por soma simples
A função de dispersão mais simples para strings soma os valores dos caracteres. Ela é fácil de implementar, mas distribui mal, pois anagramas colidem.
Execute-a para ver duas strings diferentes produzindo valores de dispersão próximos.
#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;
}A função de dispersão DJB2
DJB2 é uma função clássica de dispersão de strings, bem distribuída, criada por Daniel J. Bernstein. Ela começa em 5381 e usa hash * 33 + c.
A combinação de multiplicação e soma mistura os bits muito melhor do que uma soma simples.
#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;
}A função de dispersão FNV-1a
FNV-1a aplica XOR a cada byte e depois multiplica por um número primo. É simples, rápida e amplamente utilizada.
Ordem: XOR primeiro e depois a multiplicação (essa é a 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;
}Aplicando dispersão a inteiros
Chaves inteiras ainda precisam de mistura, pois usar apenas x % capacity cria agrupamentos quando as chaves compartilham padrões. Uma mistura multiplicativa (Knuth) distribui os 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 que são potências de dois
Quando a capacidade é uma potência de dois, você pode substituir % capacity por uma operação AND bit a bit rápida: hash & (capacity - 1).
Isso funciona somente porque os bits baixos de uma potência de dois menos um formam uma 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 que o módulo pode ser lento
O operador % é compilado como uma instrução de divisão, que é mais lenta do que AND. Em laços apertados, isso faz diferença.
- Tabela com tamanho potência de dois: use uma máscara AND
- Tabela com tamanho primo: use módulo (melhor distribuição para funções de dispersão fracas)
Colisões são inevitáveis
De acordo com o princípio da casa dos pombos, mapear muitas chaves para menos compartimentos garante a ocorrência de colisões. Uma boa função de dispersão as minimiza, mas não pode eliminá-las.
A próxima lição aborda como resolver colisões.
Demonstração da distribuição
Vamos contar como DJB2 distribui algumas chaves entre 8 compartimentos. Boas funções de dispersão distribuem as chaves de maneira relativamente 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;
}Verificação rápida
Teste sua compreensão dos conceitos básicos das funções de dispersão.
Recapitulação
Você aprendeu o que uma função de dispersão faz e como mapear chaves para compartimentos.
- Boas funções de dispersão são determinísticas, rápidas e uniformes
- DJB2 e FNV-1a são funções sólidas de dispersão para strings
- Mapeie com
% capacityou com& (capacity-1)para potências de dois - Use tipos unsigned; colisões são inevitáveis
Perguntas Frequentes
A aula “Funções de hash” é grátis?
Sim — o texto completo de “Funções de hash” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de C Academy, atualize para CoddyKit PRO. O curso de C Academy inclui 4 aulas no total.
O que vou aprender em “Funções de hash”?
Mapeando chaves para buckets. Você pratica C Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar C Academy?
Nenhuma experiência prévia é necessária. C Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “Funções de hash”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de C Academy?
Sim. Cada aula de C Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.