Aqui no blog, já falei sobre algumas estruturas de dados fundamentais em C (listas encadeadas e seus primos: a pilha e a fila). Continuando essa série de estruturas de dados em C, hoje vou falar de uma estrutura um pouco diferente: tabelas de dispersão, também conhecidas como tabelas de espalhamento ou ainda tabelas hash, (do inglês, hash tables).
O que são tabelas de dispersão?
Resumidamente, tabelas de dispersão são estruturas de dados que armazenam valores identificados por chaves de busca, e que permitem a buscados dados a partir da chavede forma eficiente. Se não deu pra pegar o espírito da coisa a partir dessa definição, sem problemas! Depois de apresentar melhor o problema que as tabelas de dispersão procuram resolver, eu darei uma definição mais específica!
Hash tables são muito utilizadas para implementar o tipo abstrato de dados chamado dicionário. Dicionários são exatamente conjuntos de pares chave/valor. Eles são usados quando desejamos associar um identificador qualquer (a chave) a um dado qualquer (o valor). Por exemplo, podemos armazenar a nota da prova dos alunos de uma certa disciplina usando seus nomes como chave e as notas como valor:
notas = {
"João": 7,
"Pedro": 8,
"Maria":9,
...}(Aqueles que programam em Python devem ter percebido que nessa linguagem, dicionários são definidos exatamente assim).
Assim, se queremos a nota (valor) do aluno João, bastaria acessar a entrada do dicionário referente a esse nome (chave). Em Python, faríamos algo como nota_joao = notas[“João”].
Importante notar que embora no exemplo eu tenha utilizado strings como chaves, em tese, as chaves de um dicionário poderiam ser de outros tipos. A única restrição dos dicionários em Python, por exemplo, é que as chaves sejam tipos de dados imutáveis e “hasheáveis” (mas isso é papo pra outro post). Aqui, trabalharemos com os tipos básicos do C, com a restrição adicional de que todas as chaves da hash table serão do mesmo tipo.
Pois bem, hash tables proporcionam um modo de implementar dicionários, mas devo lembrar que a hash table é uma estrutura de dados, e um dicionário é um tipo abstrato de dados. Se você não sabe, ou não se recorda da diferença, eu escrevi sobre esse tópico nesse outro post. Dicionários, por serem tipos “ideais”, podem ser implementados de outras formas (como por exemplo, com árvores binárias de busca).
Por que usar tabelas de dispersão?
O que buscamos com hash tables não é apenas a possibilidade de criar registros do tipo chave / valor. Como eu mencionei anteriormente, uma característica fundamental das tabelas de dispersão é o tempo levado para buscar o valor de determinada chave na tabela.
Se você já é familiarizado com listas encadeadas (e se não for, pode ler o texto do blog sobre o assunto), deve se lembrar que inserir e deletar itens no início de uma lista encadeada é uma operação bastante simples. Por outro lado, inserir, remover ou consultar o valor de um item numa posição arbitrária leva um tempo proporcional à posição do item em questão na lista. Quanto mais longe o item estiver do início da lista, mais tempo vai demorar para acessá-lo porque precisaríamos percorrer a lista item por item, desde o início.
Valores armazenados em vetores (arrays), por outro lado, podem ser acessados em tempo constante a partir de seu índice. Mas eles tem algumas desvantagens, como, por exemplo, a necessidade de sabermos de antemão o tamanho máximo do vetor (ou ter que realocar memória para o vetor dinamicamente, o que é custoso em termos de gerenciamento de memória). Além disso, vetores com valores que podem ser removidos e inseridos dinamicamente causam bastante dor de cabeça.
Em resumo, seria interessante ter uma estrutura de dados que tornasse o processo de buscar um elemento algo mais eficiente, ao mesmo tempo em que não nos complicasse na hora de inserí-los, removê-los, etc. Seria interessante se a gente pudesse unir a versatilidade das listas encadeadas com a velocidade de acesso dos vetores. E a hash table é uma estrutura de dados que busca justamente esse meio termo.
Como implementar tabelas de dispersão
Para entender como podemos implementar hash tables, vamos adotar uma abordagem gradual. Comecemos com o problema mais simples, em que nossas chaves são valores inteiros e sabemos exatamente a quantidade de chaves e valores que eu preciso para minha aplicação, eu poderia implementar um dicionário pura e simplesmente com um vetor.
Por exemplo, se eu preciso de um dicionário em que as chaves são os números de 0 a 9 e os valores são os nomes dos respectivos números, eu poderia simplesmente criar um vetor, digamos:
char * num_dict[10]={“zero”, “um”, “dois”, “tres”, “quatro”, “cinco”, “seis”, “sete”, oito”, “nove”}
A gente poderia até utilizar designated initializers, pra tornar as chaves mais explícitas:
char * num_dict[] = {[0] = “zero”, [1] = “um”, [2] = “dois”, [3] = “tres”, [4] = “quatro”, [5] = “cinco”, [6] = “seis”, [7] = “sete”, [8] = “oito”, [9] = “nove”}
E isso resolveria o problema. Porém, o que fazer quando a gente não souber de antemão a quantidade de chaves de que precisamos em nossa aplicação?
Vamos supor agora, que eu queira armazenar chaves como 1, 200 e 503736, sem necessariamente utilizar todos os outros números entre eles. Seria um grande desperdício de memória reservar espaço para um vetor de tamanho 504000 apenas porque alguns poucos números chegam a essa magnitude, enquanto várias outras entradas do vetor ficam sem utilidade.
Uma solução possível é a seguinte: eu fixo um número N para o tamanho do vetor, e aí eu arrumo um jeito de encaixar o valor das chaves no intervalo de 0 a N-1 (lembre-se que o último índice de um vetor é igual ao tamanho dele menos 1).
Se decidirmos que o tamanho do vetor deve ser 1000, precisamos de uma maneira de transformar números de tamanho arbitrário em algum número entre 0 e 999 (que seriam os índices do meu vetor). E aí eu salvo o valor da chave nesse índice.
A maneira mais rasteira de fazer isso com números inteiros é utilizando a lógica do módulo (não confundir com valor absoluto). A operação módulo é basicamente o resto da divisão de um inteiro por determinado número, e em C consiste no operador %.
Assim, para obter o número do índice do vetor correspondente a uma chave qualquer, basta fazer a operação chave % TAMANHO_DO_VETOR. No nosso exemplo, teríamos chave % 1000. O resultado dessa expressão sempre será um número entre 0 e 999. Isso resolve parte do problema.
Uma implementação parcial desse dicionário, seria mais ou menos assim:
#define TAMANHO 1000
char * dict[TAMANHO];
void insere(int chave, char * valor){
dict[chave % TAMANHO] = valor;
}A operação que definimos para transformar uma chave qualquer em um outro valor que servirá de índice para o nosso vetor, é chamada de função de dispersão, ou de espalhamento (ou ainda função hash). O índice que produzimos como resultado dessa função, costuma ser chamado de hash da chave (esse termo é muito utilizado na área de criptografia, que também utiliza funções hash, mas com outros objetivos).
Então poderíamos reescrever o código acima isolando a função de dispersão da seguinte maneira:
#define TAMANHO 1000
char * dict[TAMANHO];
int hash(int chave){
return chave % tamanho;
}
void insere(int chave, char * valor){
dict[hash(chave)] = valor;
}Embora tenhamos resolvido provisoriamente o problema da função hash com a operação módulo, geralmente precisamos de uma função mais eficiente, por questões que ficarão claras mais a frente. Mas o princípio básico das tabelas de dispersão é esse. Todo o resto consiste em estudar a parte do “arrumar um jeito de converter o valor das chaves” e as dificuldades envolvidas nesse processo.
O leitor atento já deve ter percebido a primeira dessas dificuldades: independente de quão boa seja a minha estratégia para converter números de tamanhos arbitrários em índices de 0 a 999 (nesse exemplo), se eu tiver 1001 chaves, invariavelmente vai acontecer uma colisão de chaves. Porque eu não posso atribuir índices diferentes variando de 0 a 999 pra 1001 chaves (porque eu só disponho de 1000 índices diferentes). Só pra dar um exemplo, os números 0, 1000, 2000, 3000, 4000… etc. terão o mesmo hash, se apenas utilizarmos o módulo. Pois todos esses números divididos por mil têm resto 0.
Resolvendo colisões em hash tables com listas encadeadas
Se não temos ideia da quantidade de chaves que utilizaremos de antemão, colisões serão inevitáveis. Precisamos apenas arrumar um jeito de lidar com elas. Uma solução comumente utilizada, que é a que veremos nesse post, se chama encadeamento em separado (separate chaining).
Ao invés de criarmos um vetor de valores, onde cada índice corresponde a uma chave, criamos um vetor de listas encadeadas, onde cada índice corresponde a todas as chaves que “hasheiam” para o índice em questão. E os valores de cada nó da lista encadeada correspondem aos valores dessas chaves. Assim, cada entrada X do vetor armazenará os valores referentes a todas as chaves que depois de passar pela função de dispersão são convertidas no índice X.
Se ainda parece confuso, um exemplo pode ajudar a clarear as coisas. Vamos supor que eu tenho um uma tabela de dispersão chamada animais, de tamanho 5.000, contendo os nomes de 10.000 animais diferentes, e que dentre meus pares chave/ valor, eu tenha:
Se eu estiver usando como função hash a operação módulo pura e simples, então minha chave 35 e minha chave 2035 ambas vão “hashear” para o valor 35 (se transformam no valor 35 depois de passar pela função de dispersão), então o minha entrada animais[35], conterá uma lista encadeada em que um dos elementos conterá a entrada 35 → “cachorro” e o outro a entrada 2035 → “marmota”.
Quando eu quiser obter o valor correspondente à chave 2035 meu algoritmo irá primeiro aplicar a função hash para a chave 2035, para obter o valor de índice 35. Então ele percorrerá a lista encadeada contida em animais[35] até encontrar um elemento com a chave 2035. E então retornará o valor “marmota”.
Perceba que como precisamos executar uma função hash e percorrer uma lista encadeada a cada consulta, o processo fica naturalmente mais demorado do que se utilizássemos vetores pura e simplesmente.
Por outro lado, evitamos os transtornos de ter que redimensionar um vetor quando o número de elementos supera o tamanho dele, e o processo ainda é muito mais rápido do que atravessar uma lista encadeada até o 2035o elemento, para pegar o valor de “marmota”.
Tabelas de dispersão: uma definição mais precisa
O segredo do sucesso é desenvolver uma função de dispersão que funcione de tal modo que mantenha os hashs das chaves bem distribuídos entre todos os índices do vetor, o que manterá as listas encadeadas pequenas e de tamanho proporcional entre si, diminuindo o tempo de consulta. É por isso que essa estrutura se chama tabela de dispersão ou espalhamento: porque precisamos espalhar as chaves de forma razoavelmente equilibrada entre os índices do vetor.
Ou seja, podemos definir uma tabela de dispersãocomo um vetor de tamanho M para armazenagem de dados acompanhado de uma função hash que mapeia chaves para índices desse vetor, e de um mecanismo para tratar colisões.
Essa estrutura deve ser capaz de acomodar um número arbitrário de entradas, enquanto busca manter o tempo de consulta o mais próximo possível de um valor constante pequeno. Seu principal uso é para a implementação de dicionários, também chamados de vetores associativos, por associarem chaves a valores.
Funções hash para strings
Vamos pensar agora num problema que é o inverso do que o que estávamos analisando. E se nossas chaves fossem strings e os valores fossem inteiros? Como poderíamos transformar uma string em um inteiro de 0 a N? Esse é um dos usos mais comuns de hash tables, e por isso mesmo esse assunto é muito estudado na literatura sobre tabelas de dispersão.
Existem muitos algoritmos de dispersão para strings em C. A lógica por trás da maioria deles consiste em fazer operações em cada caractere da string em questão. Em C, especificamente, podemos trabalhar com caracteres como se fossem inteiros de 0 a 127, o que torna o processo bem mais simples.
Certamente uma das funções mais simples é essa aqui:
int hash(char * key){
int hash = 0;
while (* key){
hash = (hash + *key) % VEC_SIZE;
key++;
}
return hash;
}
Nesse algoritmo, iteramos sobre cada um dos caracteres, e em cada passo, acrescentamos à variável hash (que começa com o valor 0) o valor (hash + código do caractere) módulo VEC_SIZE. Ou seja, somamos hash com o código do caractere, e depois pegamos o resto da divisão desse valor por VEC_SIZE, que é o tamanho do vetor.
Existem vários truques pra melhorar a dispersão de uma hash table. Um deles consiste em escolher um tamanho de vetor primo. Porque a operação módulo quando usada com números primos tende a dar resultados mais bem distribuídos. Outra possibilidade é a de multiplicar o hash por um número primo dentro da função de hash, assim:
int hash(char * key){
int hash = 0;
while (* key){
hash = (127 * hash + *key) % VEC_SIZE;
key++;
}
return hash;
}Se você procurar pela internet, encontrará outras funções hash para strings bem mais complicadas, e provavelmente mais eficientes que essas. Mas para entender o funcionamento, as funções acima já são suficientes.
Implementação de uma hash table em C
Agora, vou apresentar pra vocês o código fonte de uma implementação básica de hash table em C para mapear strings para valores inteiros. Se você ficar confuso em relação às operações de inserção e consulta de valores e à destruição do dicionário, ou sobre o uso de ponteiros, vale a pena dar uma olhada no post sobre listas encadeadas aqui do blog.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_SIZE 101 //A funcao hash precisa fazer um
//modulo VEC_SIZE para encaixar a
//chave no vetor, e dizem por ai
//que numeros primos distribuem melhor
//as chaves, entao vamos confiar.
//Nossa querida lista encadeada, mas com um atributo a mais,
//para armazenar a chave relacionada a esse valor.
typedef struct _node{
char * key;
int val;
struct _node * next;
}node;
/*Essas sao funcoes da interface para o objeto dicionario*/
//inicializa um novo dicionario
void si_dict_init(node * dict[]);
//insere/modifica um par chave/valor no dicionario
void si_dict_insert(node * dict[], char * key, int val);
//pega o valor de um item, a partir da chave
int si_dict_get(node * dict[], char * key);
//apaga o dicionario
void si_dict_del(node * dict[]);
/**********************************************************/
//É praxe sinalizar as funcoes que nao fazem parte
//da interface de algum jeito. Aqui estou usando
//underline pra sinalizar que essa eh uma funcao
//de uso interno.
int _si_hash(char * key){
int hash = 0;
while (* key){
hash = (hash + *key) % VEC_SIZE;
key++;
}
return hash;
}
void si_dict_init(node * dict[]){
//Inicializa o vetor de entradas do dicionario
//com as 'cabecas' de cada lista encadeada.
for (int i = 0; i < VEC_SIZE; i++){
node * head = malloc(sizeof(node));
head -> key = NULL;
head -> val = 0;
head -> next = NULL;
//Lembre que podemos usar a sintaxe de vetores
//com ponteiros
dict[i] = head;
}
}
void si_dict_insert(node * dict[], char * key, int val){
//Pega o valor da chave 'hasheada'
int hash = _si_hash(key);
//current comeca apontando para o
//no cabeca da lista em dict[hash]
node * current = dict[hash];
//Se ja tiver um no na lista essa chave,
//altera o valor dela. Caso contrario,
//cria outro no no final.
while(current -> next){
//O primeiro no eh a cabeca, entao eh OK
//nao testa-la.
if (strcmp(current -> next -> key, key) == 0){
current -> next -> val = val;
return;
}
current = current -> next;
}
//Se o fluxo chegou aqui, entao current -> next == NULL
//Ou seja, current eh o ultimo no da lista, e ele tambem
//nao possui a chave que queremos inserir.
//Entao, agora eh soh adicionar um novo no no final da lista.
//Quando lidamos com strings (que são ponteiros para char)
//nao podemos simplesmente colocar o argumento 'key'
//em new_node -> key, porque o argumento 'key'
//eh um ponteiro para char, e nao sabemos se o endereco
//de memoria para o qual ele aponta vai continuar
//armazenando esse valor no longo prazo. Entao, o mais seguro
//eh criar uma copia dele!
//+1 porque precisamos contar o \0
char * new_key = malloc(strlen(key)+1);
strcpy(new_key, key);
node * new_node = malloc(sizeof(node));
new_node -> key = new_key;
new_node -> val = val;
new_node -> next = NULL;
current -> next = new_node;
}
int si_dict_get(node * dict[], char * key){
//Pega o valor da chave 'hasheada'
int hash = _si_hash(key);
node * current = dict[hash] -> next;
//Percorre a lista da entrada do vetor em questao
//
while (current){
if (strcmp(current -> key, key) == 0)
return current -> val;
current = current -> next;
}
//Retornamos -1 em caso de falha assumindo
//que os valores inseridos sao sempre positivos.
//Caso valores negativos possam ser inseridos
//no dicionario, precisamos de um outro protocolo!
return -1;
}
void _si_list_del(node * current){
while (current){
node * temp = current;
current = current -> next;
free(temp -> key);
free(temp);
}
}
void si_dict_del(node * dict[]){
for (int i = 0; i < VEC_SIZE; i++){
_si_list_del(dict[i]);
dict[i] = NULL;
}
}
int main(void){
//Um pequeno teste para verificar se tá tudo ok
node * dict[VEC_SIZE];
si_dict_init(dict);
si_dict_insert(dict, "caramba", 3);
si_dict_insert(dict, "nossinhora", 20);
si_dict_insert(dict, "eita", 1948);
si_dict_insert(dict, "creindeuspai", 57477);
si_dict_insert(dict, "jezuisss", 23);
si_dict_insert(dict, "eitapreula", 320);
si_dict_insert(dict, "misericordia", 1944238);
si_dict_insert(dict, "vixe", 57);
printf("%s:%d\n", "vixe", si_dict_get(dict, "vixe"));
printf("%s:%d\n", "jezuisss", si_dict_get(dict, "jezuisss"));
printf("%s:%d\n", "xablau", si_dict_get(dict, "xablau"));
printf("%s:%d\n", "caramba", si_dict_get(dict, "caramba"));
si_dict_del(dict);
}
Se você está se perguntando o que seria si_dict, eu inventei esse nome pra destacar o fato de que esse é um dicionário de String para Int. Como C não possui algo como o namespace de linguagens como Java e C++, é interessante criar prefixos para nossas funções, que funcionam como um “pseudo-namespace” para evitar colisão de nomes com funções de outras bibliotecas.
Esse código foi bastante simplificado, só pra ilustrar os princípios gerais do funcionamento das tabelas de dispersão. Num código de verdade, deveríamos sempre testar o resultado do malloc para saber se a memória foi efetivamente reservada, por exemplo. Então, ao invés de usar funções void (que não retornam nada), deveríamos retornar um código de erro ou sucesso ao inicializar a lista e inserir dados.
Outro ponto importante é que, no geral, devemos esconder detalhes de implementação do usuário de nossa biblioteca. Nesse caso, ao invés de deixar a cargo do usuário criar o vetor que servirá como dicionário, deveríamos criar um vetor dinamicamente dentro da função de inicialização e retornar um ponteiro para esse objeto.
Espero que tenha curtido mais esse post da série sobre estruturas de dados em C. Continue acompanhando o blog pra mais dicas, tutoriais e artigos sobre Python, C, Linux e computação em geral!
