C: Hash tables, arrays associativos, dicionários…

Não sei quantos nomes existem para descrever esta forma de organizar séries de dados na memória, esses três do título foram as que eu consegui pensar em 5 segundos. :P

Enfim, comecemos pela forma mais simples de armazenar séries de dados na memória, arrays, seguiremos para listas, árvores, e então chegaremos às hash tables. Se tudo que você quer é um exemplo de implementação, vá ao fim do artigo.

Arrays

Internamente, quando se declara um array, um bloco de memória contínuo é alocado. Isso significa que elementos de um array estão sempre próximos entre si e que percorrer todo um array é relativamente rápido. O ponto fraco dos arrays é não serem flexíveis: Um array de tamanho 5 tem tamanho 5 e pronto, acabou. É possível criar um array b com tamanho 6 e copiar os 5 primeiros elementos de a para b, mas o array a continua tendo tamanho 5. No entanto, se esse tipo de operação começa a se tornar frequente demais, a vantagem de performance do array começa a desaparecer.

Primeiro, é necessário alocar o novo array e copiar os elementos. Depois, é necessário limpar o array anterior, ou daremos início a um gasto desnecessário de memória.

Com o problema da flexibilidade em mente [1], foi criado um novo método para lidar com séries de dados, as listas ligadas/linkadas.

Listas

Listas ligadas recebem esse nome porque cada nó (node) se liga a outro. Existem algumas formas diferentes de se implementar isso, como:

  • Cada elemento aponta para o próximo. O último aponta para NULL. É assim que funcionam as cons cells em Lisp, Haskell e aposto que em várias outras linguagens.
  • Cada elemento aponta para o próximo e o anterior. Isso facilita algumas operações, mas complica outras. Há um aumento no consumo de memória também, já que são necessários dois ponteiros.

Existem outras formas, assim como variações dessas. Lembre-se que há sempre uma troca entre consumo de memória e eficiência no processamento. Existem formas de usar listas que apontam para o próximo elemento e para o anterior usando apenas um ponteiro, mas para isso é necessária uma operação a mais (XOR).

Um detalhe sobre listas: geralmente os novos elementos dela são “empurrados” (push) no começo da lista, ao invés de adicionados (append) ao fim da mesma. O código fica muito mais rápido assim, já que não é necessário percorrer toda a lista para adicionar um novo elemento.

Existem também as árvores binárias, que estruturalmente são parecidas com listas, mas que apresentam outras vantagens e desvantagens.

Árvores binárias

Árvores binárias facilitam muito nas buscas: Se a condição c for verdadeira, siga à esquerda, senão, siga à direita. Isso significa que mesmo em árvores muito grandes, o número de “passos” dados é relativamente pequeno. Para se ter uma idéia, em uma árvore com 100.000 elementos, no máximo 17 “passos” terão de ser dados (\log_2 100.000 = 16,6 ). No entanto, para que isso seja verdade, a árvore tem de estar bem equilibrada (tanto o lado esquerdo como o direito terem o mesmo número de níveis). Existem algoritmos para isso, mas não entrarei nesses detalhes.

Toda essa agilidade em buscas vem com um preço: a inclusão de novos elementos em uma árvore é mais próxima da função append em uma lista que um push. Apesar de não ser necessário atravessar a árvore toda, ainda é necessário fazer comparações e tomar decisões a partir daí. Além disso, árvores consomem um pouco mais de memória, já que são necessários dois ponteiros (esquerda e direita) ao invés de só um (próximo) como geralmente é o caso em listas.

Por fim, existem as hash tables, que mistura arrays com listas e tem bom desempenho em buscas.

Hash tables

Hash tables são arrays de pequenas listas. No entanto, esse array não é acessado sequencialmente. Para ficar mais claro, vou começar com a função que dá nome a esse método: a função de hash.

Função hash
Esta função tem por objetivo associar um número a uma “coisa”. No exemplo que darei mais a diante, a função hash associa um número a uma pessoa a partir de seu nome. É esse número que nos dirá em que posição do array a “coisa” será armazenada; por isso, é preciso levar duas coisas em consideração: seu tempo de execução, já que ela será executada na adição de novos elementos e na busca por elementos já existentes, e a probabilidade de ela gerar o mesmo número para representar objetos diferentes.

Colisões
Se por um acaso a função hash gerar o mesmo número n para dois elementos, o programa não travará, nem o elemento anterior será apagado. O que ocorrerá é que a posição n deixará de conter unicamente um elemento, agora ela contém uma pequena lista de dois elementos.

Por que todo esse alarde sobre funções hash que gerem números diferentes? Pelo simples fato de que se você incluiu 10 elementos em um array com 10 posições, era de se esperar que em geral cada posição tivesse apenas um elemento. No entanto, com uma função hash ruim, pode acontecer de uma única posição ter, por exemplo, oito elementos. Analisando a performance deste caso, parece muito mais uma lista que uma hash table.

Lembre-se de que a função hash não pode ser aleatória ou depender do tempo, por exemplo, ou você não irá encontrar o elemento na hora de fazer uma busca!

O Array
O número de colisões entre os números não depende exclusivamente da função hash. É evidente que se o programa for salvar 1000 elementos em um array de 10 posições, haverá várias colisões. Pelo outro lado, salvar 10 elementos em um array de 1000 posições é um desperdício enorme de memória.

O código

Creio que o código esteja bastante claro, mas qualquer coisa perguntem. Se vocês quiserem “ver” um caso de colisão, troque o 5 na linha #define REGISTROS 5 por 4.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Define o numero de posicoes no array. Note que esse nao eh o limite maximo */
#define REGISTROS 5

/* Abstracao de uma pessoa. Apenas para exemplo. */
typedef struct Pessoa Pessoa;
struct Pessoa {
    char *nome;
    char *profissao;
    unsigned short idade;
    unsigned short senha;
    Pessoa *proxima;
};

/* Onde os registros serao salvos */
Pessoa *pessoas[REGISTROS];

unsigned int hash(const char *nome);
unsigned int registrar_pessoa(Pessoa *p);
Pessoa *achar_pessoa(const char *nome);

int main(int argc, char *argv[])
{
    /* Exemplos */
    Pessoa joao = { "Joao Ninguem", "Bohemio", 21, 6969, NULL };
    Pessoa jose = { "Jose Pessoa",  "Nerd", 12, 1234, NULL };
    
    
    registrar_pessoa(&joao);
    registrar_pessoa(&jose);

    achar_pessoa("Joao Ninguem");
    achar_pessoa("Jose Pessoa");
    achar_pessoa("Maria Pessoa");

    return 0;
}

/* Dado um nome, retorna um numero no intervalo [0,REGISTROS[ */
unsigned int hash(const char *nome)
{
    char *p = nome;
    unsigned int soma = 0;

    while(*p != 0) /* caractere nulo indica fim da string */
    {
        soma += *p;
        p++;
    }
    
    return(soma % REGISTROS);
}

/* Registra uma pessoa no array */
unsigned int registrar_pessoa(Pessoa *p)
{
    unsigned int posicao;
    if(p == NULL)
        exit(1);

    posicao = hash(p->nome);
    
    /* Posicao vazia, basta incluir a pessoa aqui */
    if(pessoas[posicao] == NULL)
    {
        pessoas[posicao] = p;
    }

    /* Houve uma colisao entre as posicoes, devemos usar o campo "proxima" */
    else
    {
        Pessoa *tmp = pessoas[posicao];
        while(tmp->proxima != NULL) tmp = tmp->proxima;
        tmp->proxima= p;
    }

    printf("registrado em %u.\n", posicao);
    return(posicao);
}    

Pessoa *achar_pessoa(const char *nome)
{
    unsigned int posicao = hash(nome);
    Pessoa *p = pessoas[posicao];

    for(; p!=NULL ; p = p->proxima)
    {
        /* Nome foi encontrado */
        if(strcmp(p->nome, nome) == 0)
        {
            printf("pessoa encontrada em %u.\n", posicao);
            return(p);
        }
    }

    /* Se a funcao chegar aqui, o loop terminou sem encontrar a pessoa, entao
     * ela nao existe */
    printf("pessoa nao encontrada.\n");
    return(NULL);
}

[1] Não tenho certeza se historicamente os arrays se desenvolveram antes das listas, eu creio que sim.

Publicidade

3 Respostas para “C: Hash tables, arrays associativos, dicionários…

  1. José Oliveira junho 18, 2010 às 10:29 am

    Viva…Gostei muito deste post, está muito esclarecedor ;)
    parabéns, explica muito bem…
    estou a estudar programação, mas há uma coisa que não entendi bem! neste momento tenho de trabalhar com pilhas, filas, filas com prioridade, Arrays associativos e Árvores Binárias…
    Percebi bem quando é vantajoso uma estrutura do tipo pilha para a resolução de um problema (por exemplo, quando queremos inverter uma sequẽncia, visto ser uma estrutura de dados LIFO); também percebi quando é necessário usar as filas com prioridade (tipo o sistema de atendimento de um hospital, em que existem diferentes prioridades, ou a saida de alimentos de uma instituiçao, visto que ha alimentos que duram menos tempo que outros)…
    Contudo, tenho de resolver problemas em que preciso de escolher uma destas estruturas de dados e não sei qual devo usar….
    Consegue explicar-me quando é que é vantajoso usar um array Associativo e uma árvore binária? Suponho que a árvore binária seja usada quando queremos guardar um certo número de elementos e posteriormente encontrá-los com facilidade, é isso?
    Tenho mesmo dificuldade em perceber o tipo de problemas que o array associativo é uma boa aposta…

    Obrigado, José Oliveira =)

    • _andre junho 19, 2010 às 10:58 am

      Nós podemos dizer que, de certa forma, todo array é associativo. Acontece, porém, que os arrays “normais” associam um número (uma posição) a uma informação. Por exemplo, o empregado 1 se chama João e tem 32 anos, enquanto que a empregada 2 se chama Maria e tem 45 anos:

      empregados[1] = { “João”, 32 };
      empregados[2] = { “Maria”, 45 };

      Mas como saber qual o número do empregado X? Precisaríamos investigar os elementos do array até encontrar o que queríamos. Por outro lado, podíamos fazer diferente: em vez de associar uma posição a uma informação, associar uma informação a outra. Nesse mesmo exemplo dos empregados João e Maria, teríamos:

      empregados[“João”] = 32;
      empregados[“Maria”] = 45;

      A mesma ideia poderia ser utilizada para um catálogo de endereços. O array associaria o nome da pessoa a seu endereço, número de telefone e aniversário:

      endereço[“Pedro”] = {“Rua das palmeiras, 123”, “454-7887”, “12/12/1975” }
      endereço[“Juca”] = {“Avenida Principal, 77”, “454-7889”, “30/03/1987” }

      Bem melhor que ter que procurar endereço por endereço até encontrarmos a pessoa que queríamos, concorda?

      Quanto as árvores binárias, é basicamente isso, sim.

  2. José Oliveira junho 21, 2010 às 6:43 am

    Muito obrigado andré =D….

    agora já absorvi o conceito….e se me pedirem para fazer um dicionário ou lista telefónica, vou usar arrays associativos…em que a key será o nome da pessoa/palavra do dicionário =)

    Muito obrigado, Abraço

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s

%d blogueiros gostam disto: