Tabela de dispersão

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes fiáveis e independentes. (desde março de 2011). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

Em ciência da computação, uma tabela de dispersão (também conhecida por tabela de espalhamento ou tabela hash, do inglês hash) é uma estrutura de dados especial, que associa chaves de pesquisa 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.

História[editar | editar código-fonte]

A história da tabela de dispersão é incerta. Há quem credite sua criação a H. P. Luhn que, em 1953, teve a idéia enquanto trabalhava na IBM. Outra hipótese é de que foram inventadas pelos autores de compiladores para linguagens de programação nos anos 1960, como truque para manter as listas de variáveis de usuário e seus respectivos valores. Um interpretador de linguagem BASIC, por exemplo, não é muito mais do que uma calculadora com uma tabela de dispersão em que as variáveis e seus valores são armazenados.

Complexidade e usos comuns[editar | editar código-fonte]

Tabelas de dispersão são tipicamente utilizadas para implementar vetores associativos, conjuntos e 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 de dispersão 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 de dispersão são as tabelas de transposição em jogos de xadrez para computador até mesmo em serviços de DHCP.

Função de espalhamento[editar | editar código-fonte]

Tabela de dispersão com vetor simples e com vetor de listas.

A função de espalhamento ou função de dispersão é 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 de dispersão da criptografia), ou quando conhecemos previamente o conteúdo da tabela armazenada. Nas tabelas de dispersão 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 de dispersão são aliadas com alguma outra estrutura de dados, tal como uma lista encadeada ou até mesmo com árvores balanceadas. Em outras oportunidades a colisão é solucionada dentro da própria tabela.

Tipos[editar | editar código-fonte]

Método da divisão (método da congruência linear)

h (k) = k \pmod m

  • Potências de dois devem ser evitadas para valores de m.
  • m deve ser um número primo distante de pequenas potências de dois (m grande).

Exemplo:


k = 10028;

m = 5013;

h (10028) = 10028 mod 5013;

h (10028) = 2

(m é o tamanho da tabela)

Método da multiplicação (método da congruência linear multiplicativo)

h(k) = (m * (kA \pmod 1))

  • m normalmente é uma potência de dois.
  • A é uma constante, tal que 0 < A < 1.
  • Extrair a parte fracionária de kA, ou seja, kA \pmod 1.
  • Utilizar o piso do resultado.

Exemplo:


k = 123456;

m = 1024;

A = 0.61803\ldots;

\begin{align}
 h(k) & = 1024*(123456*0.61803\ldots \pmod 1) \\
      & = 1024*(76300,0041151\ldots \pmod 1) \\
      & = 1024*0,0041151\ldots \\
      & = 4.21386\ldots \\
      & = 4
\end{align}

Exemplo de função de espalhamento e colisão[editar | editar código-fonte]

Imagine que seja necessário utilizar uma tabela de dispersão 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, devolver 0. Para cada nome começado com a letra B, devolver 1, e assim por diante. Por fim, Para cada nome começado com a letra Z, devolver 25.

O exemplo anterior poderia ser implementado, em C, da seguinte forma:

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

Agora inserimos alguns nomes em nossa lista telefônica:

José da Silva; Rua das Almas, 35; Telefone (31) 3888-9999
Ricardo Souza; Rua dos Coqueiros, 54; Telefone (31) 3222-4444
Orlando Nogueira; Rua das Oliveiras, 125; Telefone (31) 3444-5555

Nossa função distribuiria os nomes assim:

Hash2.JPG

Agora inserimos mais um nome:

Renato Porto; Rua dos Elefantes, 687; Telefone (31) 3333-5555

E temos uma colisão:

Hash3.JPG

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".

Colisões[editar | editar código-fonte]

A função de dispersão pode calcular o mesmo índice para duas chaves diferentes, uma situação chamada colisão. Por conta disso, a função deve ser projetada para evitar ao máximo a ocorrência de colisões. Por mais bem projetada que seja a função de dispersão, sempre haverá colisões. A estrutura de dispersão utiliza mecanismos para tratar as colisões, que dependem de características da tabela usada.

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 do aniversário: mesmo que considerarmos que a função 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.

Mecanismos de tratamento[editar | editar código-fonte]

Os mecanismos mais comuns para tratamento de colisões são: endereçamento aberto e encadeamento.

Endereçamento aberto[editar | editar código-fonte]

A informação é armazenada na própria tabela de dispersão. Possui três estratégias: tentativa linear (incremental), tentativa quadrática e dispersão dupla.

Para a estratégia linear, é utilizada uma segunda função matemática para calcular a posição em que deve ser feita a próxima prova, a função de redispersão.

rh(pos, tentativas) = (pos + tentativas) mod Ttabela

Desta forma eliminamos o agrupamento primário porém geramos outro fenômeno conhecido como agrupamento secundário. Ocorre que as chaves de valores diferentes e mesmo valor de dispersão possuem a mesma sequência de provas.

Para a estratégia quadrática:

rh(pos, tentativas) = (pos + tentativas^{2}) mod Ttabela

Para reduzir o agrupamento primário, procura-se por um lugar livre através da fórmula: h+n2, em que h representa o índice da colisão e n o sequencial de busca pela nova posição.

Para a estratégia de dispersão dupla:

rh(ch, tentativas) = (h2(ch) + tentativas) mod Ttabela

Utilizamos então a função h2(ch):

h2(ch) = 1 + ch mod(Ttabela - 1)

Encadeamento[editar | editar código-fonte]

A informação é armazenada em estruturas encadeadas fora da tabela de dispersão. Encontra-se uma posição disponível na tabela e indicamos que esta posição é a que deve ser buscada em seguida. Os mais conhecidos são encadeamento separado e endereçamento aberto.

O 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 balanceada, podemos melhorar o tempo médio de acesso da tabela de dispersão para O(log n) ao invés de O(n). Mas como as listas de colisão são projetadas para serem curtas, a sobrecarga causada 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 sobrecarga 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.

Já 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 é realizada 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 décima posição, será buscado na centésima, depois na milésima. 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 dispersão dupla). Na prática, o que acontece nesse caso é que o vetor da tabela é formado por uma seqüência de funções de espalhamento auxiliares, em que 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 a sobrecarga não justifica a experiência.

Indexação perfeita[editar | editar código-fonte]

Se tivermos uma relação fixa de registros, podemos obter uma função que indexe os itens sem que ocorra uma 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 tempo de acesso aos dados ser de 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 sobrecarga do sistema.

Problemas e comparações com outras estruturas[editar | editar código-fonte]

Apesar das tabelas de dispersão 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 sobrecarga no sistema. Além disso, e mais importante, o tempo gasto na depuração e remoção de erros é maior do que nas árvores balanceadas, que também podem ser levadas em conta para solução do mesmo tipo de problema.

Limitações[editar | editar código-fonte]

A tabela de dispersão é uma estrutura de dados do tipo dicionário, que não permite armazenar elementos repetidos, recuperar elementos sequencialmente (ordenação), nem recuperar o elemento antecessor e sucessor. Para otimizar a função de dispersão é necessário conhecer a natureza da chave a ser utilizada. No pior caso, a ordem das operações pode ser O(N), caso em que todos os elementos inseridos colidirem. As tabelas de dispersão com endereçamento aberto podem necessitar de redimensionamento.

Aplicação[editar | editar código-fonte]

Suas aplicações incluem banco de dados, implementações das tabelas de símbolos dos compiladores, na programação de jogos para acessar rapidamente a posição para qual o personagem irá se mover e na implementação de um dicionário.

Em redes de computadores, NAT, Network Address Translation, também conhecido como masquerading é uma técnica que consiste em reescrever os endereços IP utilizando-se de uma tabela hash.

Ligações externas[editar | editar código-fonte]