Tabela Hash: A tabela de Espalhamento ou Dispersão.

Hoje eu vou falar um pouco sobre Tabela Hash.  Bem, esta tabela é uma Estrutura de Dados bem como as Árvores.  Então, vamos entender o que seria esta tabela.

A tabela Hash é uma estrutura de dados que implementa o espalhamento, ou seja que associa chaves de pesquisa a valores. Ela também é conhecida por tabela de espalhamento ou dispersão. 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.

Ela pode ser representada por um vetor onde cada posição deste é chamada de encaixe e armazena uma uma classe de partição.

Complexidade e usos comuns

Tabelas hash são tipicamente utilizadas para implementar vetores associativos, sets 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 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 hash

Tabela hash com vetor simples e com vetor de listas.

A 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 hash é 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 hash, geram a mesma saída, acontece o que chamamos de colisão.

Na prática, funções hash 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 hash 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 árvores balanceadas. Em outras oportunidades a colisão é solucionada dentro da própria tabela.

Exemplo de função hash 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 hash 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 C, da seguinte forma:

        int hashExemplo(char * chave)

        {

                return (chave[0]-65);

        }

Agora inserimos alguns nomes à 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

A função distribuiria os nomes assim:

Agora inserimos mais um nome:

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

E temos uma colisão:

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 hash. Considere um exemplo derivado do 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 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 hash que resolva o novo conflito (também chamado de double hashing ou rehash ¹). Na prática, o que acontece nesse caso é que o vetor da tabela é formado por uma seqüência de funções hash 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 hash perfeita. Podemos até mesmo buscar uma função hash perfeita mínima, que, além de não causar colisões, preenche todas as posições da tabela. As funções hash perfeitas fazem o acesso aos dados ser O₍₁₎ no pior caso.

Existem métodos que atualizam a função hash 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 hash 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 hash é 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 árvores balanceadas, que também podem ser levadas em conta para solução do mesmo tipo de problema.

1 -  Double hashing ou rehash

Existem duas funções de Hash: Uma para usar normalmente  e outra para usar quando há colisões.

h1( i )=( i mod m ) = C1

h2 = ( i mod m-1 )+1 = C2  ---} usada quando há colisões

Para calcular o primeiro índice usa-se C1;

Para calcular o segundo índice ( se existir colisões) usa-se C1+C2;

Para calcular o terceiro índice ( se também existir colisões ) usa-se C1+2C2, depois C1+3C2, etc. 

Devemos normalizar  h1( i ) e h2 ( i ) para que o tamanho da tabela seja igual.

Nota: ( m ) e ( m-1 ) são primos entre si, para que o resto entre os 2 seja diferente de 0.

Exemplo:

 

h1( i ) = i mod 7 = C1

h2( i ) = ( i mod 6 ) +1 =C2

5     h1 ( 5 ) = 5  ----} 5 está vazio;

10   h1 ( 10 ) = 3 ----} 3 está vazio;

12   h1 ( 12 ) = 5 ----} 5 está ocupado, logo faz-se h2;

h2 ( 12 ) =1;

C1+C2 = 5 + 1 = 6  ----} soma-se o C1 com C2 logo 6 está vazio;

19  h1 ( 19 ) = 5 ----} 5 está ocupado logo fazemos o h2;

h2 ( 19 ) =2 = C1+C2= 5+2=7  ----} como o rehash é circular vai-se inserir no 0;

Nota: Se a posição  0  também estivesse ocupado recorreríamos a C1+2C2 

(iria inserir-se no 5+2(2)=9 ---}corresponde ao lugar 2)

Tipos:

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

h(k) = k(mod 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) = 10028mod5013;h(10028) = 2

(m é o tamanho da tabela)

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

h(k) = (m * (kA(mod 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(mod 1).

Utilizar o piso do resultado

Escrevi com base no trabalho dos alunos em Tecnologia em Sistemas de Informação: Claudio Cesconeto e Alex Sandro Oliveira. No mais, dei uma lida em Wiki e outros sites. Caso algo não condiz com o certo, corrija-me por comentário.