Algoritmos e Estruturas de Dados/Tabela de Hash

Em ciência da computação a tabela hash (de hashing, no inglês), também conhecida por tabela de espalhamento, é uma estrutura de dados especial, que associa chaves de pesquisa (hash) a valores. Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado. É algumas vezes traduzida como tabela de escrutínio.

Complexidade e usos comuns

Tabelas hash são tipicamente utilizadas para implementar vetores associativos, sets e cache|caches. São tipicamente usadas para indexação de grandes volumes de informação (como bases de dados). A implementação típica busca uma função hash que seja de complexidade O(1), não importando o número de registros na tabela (desconsiderando colisões). O ganho com relação a outras estruturas associativas (como um vetor simples) passa a ser maior conforme a quantidade de dados aumenta. Outros exemplos de uso das tabelas hash são as tabelas de transposição em jogos de xadrez para computador até mesmo em serviços de DHCP.

A função de espalhamento

A função de espalhamento ou função hash é a responsável por gerar um índice a partir de determinada chave. Caso a função seja mal escolhida, toda a tabela terá um mau desempenho.

O ideal para a função de espalhamento é que sejam sempre fornecidos índices únicos para as chaves de entrada. A função perfeita seria a que, para quaisquer entradas A e B, sendo A diferente de B, fornecesse saídas diferentes. Quando as entradas A e B são diferentes e, passando pela função de espalhamento, geram a mesma saída, acontece o que chamamos de colisão.

Na prática, funções de espalhamento perfeitas ou quase perfeitas são encontradas apenas onde a colisão é intolerável (por exemplo, nas funções hash da criptografia), ou quando conhecemos previamente o conteúdo da tabela armazenada). Nas tabelas hash comuns a colisão é apenas indesejável, diminuindo o desempenho do sistema. Muitos programas funcionam sem que seu responsável suspeite que a função de espalhamento seja ruim e esteja atrapalhando o desempenho.

Por causa das colisões, muitas tabelas hash são aliadas com alguma outra estrutura de dados, tal como uma lista encadeada ou até mesmo com árvore AVL|árvores balanceadas. Em outras oportunidades a colisão é solucionada dentro da própria tabela.

Exemplo de função de espalhamento e colisão

Imagine que seja necessário utilizar uma tabela hash para otimizarmos uma busca de nomes de uma lista telefônica (dado o nome, temos que obter o endereço e o telefone). Nesse caso, poderíamos armazenar toda a lista telefônica em um vetor e criar uma função de espalhamento que funcionasse de acordo com o seguinte critério:

        Para cada nome começado com a letra A, retornar 0
        Para cada nome começado com a letra B, retornar 1
        ...
        Para cada nome começado com a letra Z, retornar 25

O exemplo anterior poderia ser implementado, em Linguagem de programação C|C, da seguinte forma:

 	int hashExemplo(char * chave)
	{
		return (chave[0]-65);
	}

Agora inserimos alguns nomes em nossa lista telefônica:

José da Silva; Rua das Almas, 35; Telefone (11) 888-9999

Ricardo Souza; Rua dos Coqueiros, 54; Telefone (11) 222-4444

Orlando Nogueira; Rua das Oliveiras, 125; Telefone (11) 444-5555

Agora inserimos mais um nome:

Renato Porto; Rua dos Elefantes, 687; Telefone (11) 333-5555

Como se pode notar, a função de exemplo causaria muitas colisões. Se inserirmos um outro nome começado com a letra R, teremos uma outra colisão na letra R. Se inserirmos "João Siqueira", a entrada estaria em conflito com o "José da Silva".

Resolvendo colisões

Um bom método de resolução de colisões é essencial, não importando a qualidade da função de espalhamento. Considere um exemplo derivado do paradoxo|paradoxo do aniversário: mesmo que considerarmos que a função irá selecionar índices aleatórios uniformemente em um vetor de um milhão de posições, há uma chance de 95% de haver uma colisão antes de inserirmos 2500 registros.

Há diversos algoritmos de resolução de colisão, mas os mais conhecidos são Encadeamento Separado e Endereçamento Aberto.

Encadeamento Separado

É a solução mais simples, em que normalmente um registro aponta para uma lista encadeada em que são armazenados os registros em conflito. A inserção na tabela requer uma busca e inserção dentro da lista encadeada; uma remoção requer atualizar os índices dentro da lista, como se faria normalmente.

Estruturas de dados alternativas podem ser utilizadas no lugar das listas encadeadas. Por exemplo, se utilizarmos uma Árvore AVL|árvore balanceada, podemos melhorar o tempo médio de acesso da tabela hash para O(log n) ao invés de O(n). Mas como as listas de colisão são projetadas para serem curtas, o overhead causado pela manutenção das árvores pode fazer o desempenho cair.

Apesar disso, as árvores podem ser utilizadas como proteção contra ataques que buscam criar overhead propositalmente - descobrindo uma forma da função gerar repetidamente o mesmo índice - e derrubar o sistema (ataques DOS). Nesse caso, uma árvore balanceada ajudaria o sistema a se manter estável, por ser uma estrutura com grande capacidade de crescimento.

Endereçamento Aberto

No método de Endereçamento Aberto os registros em conflito são armazenados dentro da própria tabela. A resolução das colisões é realizadas através de buscas padronizadas dentro da própria tabela.

A forma mais simples de fazer a busca é procurar linearmente na tabela até encontrar um registro vazio ou o registro buscado. Outras formas utilizadas incrementam o índice exponencialmente: caso o registro não seja encontrado na posição 10, será buscado na posição 100, depois na posição 1000. A inserção tem que seguir o mesmo critério da busca.

Outra forma mais complexa de implementar o Endereçamento Aberto é criar uma nova função de espalhamento que resolva o novo conflito (também chamado de double hashing). Na prática, o que acontece nesse caso é que o vetor da tabela é formado por uma seqüência de funções de espalhamento auxiliares, onde a chave de entrada será o valor gerado pela função anterior. Esse tipo de implementação pode ser útil em casos muito específicos, com enormes quantidades de dados, mas normalmente o overhead não justifica a experiência.

Indexação Perfeita

Se tivermos uma relação fixa de registros, podemos obter uma função que indexe os itens sem que ocorra nenhuma colisão, chamada função de espalhamento perfeita. Podemos até mesmo buscar uma função de espalhamento perfeita mínima, que, além de não causar colisões, preenche todas as posições da tabela. As funções de espalhamento perfeitas fazem o acesso aos dados ser O(1) no pior caso.

Existem métodos que atualizam a função de espalhamento de acordo com a entrada, de forma que nunca ocorra colisão. O inconveniente dessa técnica é que a própria atualização da função de espalhamento causa overhead do sistema.

Problemas e comparações com outras estruturas

Apesar das tabelas hash terem em média tempo constante de busca, o tempo gasto no desenvolvimento é significativo. Avaliar uma boa função de espalhamento é um trabalho duro e profundamente relacionado à estatística. Na maioria dos casos soluções mais simples como uma lista encadeada devem ser levados em consideração.

Os dados na memória ficam aleatoriamente distribuídos, o que também causa overhead no sistema. Além disso, e mais importante, o tempo gasto na depuração e remoção de erros é maior do que nas árvore AVL, que também podem ser levadas em conta para solução do mesmo tipo de problema.