Tabela Hash

Motivação

Algumas das estruturas de dados vistas anteriormente requerem que seus elementos (células dinâmicas) sejam inspecionados seqüencialmente até que a desejada seja encontrada. Em alguns casos, todos os N elementos devem ser inspecionados, em outros apenas uma parcela M / ≤ N são visitados e finalmente, existem casos em que o elementos detentor da chave que deseja-se acesso pode ser encontrado com apenas 1 operação (O(1)).

Exemplo:

1. Encontrar a maior chave (prioridade) em uma lista encadeada não ordenada – todos os N elementos da lista devem ser inspecionados;
2. Encontrar o elemento X da lista cujo dado de X = elemento – melhor caso O(1) pior caso O(N);
3. Remover o elemento que possui a maior chave em uma Heap – O(1).

No caso ideal, as chaves da estrutura devem ser acessadas em uma única instrução. Insto pode ser alcançado via a utilização de um array (estático/seqüencial)

No entanto, como visto anteriormente, a utilização de arrays apresenta algumas desvantagens se comparada a uma lista dinâmica.

Ainda, a utilização do índice dos arrays como chave de pesquisa pode ser problemática como mostra o exemplo a seguir:

Ex: Um programa para gerência e arquivamente de e-books desenvolvido para tablets utiliza uma chave seqüencial (1 para o primeiro livro adquirido, 2 para o seguindo e assim por diante) para indexar todos os livros gerenciados pelo sistema.

Desta forma, pode-se estruturar a informação do sistema (estrutura de dados do sistema) usando um simples array estático, digamos de N=10000 posições.

No entanto, a única pesquisa direta possível de ser feita em O(1) é pela ordem de compra dos e-books (chave) o que não é muito útil.

Caso desejemos pesquisar a lista de livros pelo nome do autor ou pelo título, devemos estruturar a informação de maneira diferente.

Existem vários problemas com esta forma de estruturar a informação:

1. Muitas posições (de fato, a maioria) do array nunca indexarão um autor válido (p. ex. quem chamaria “aaaaaaaaaa”?);
2. Existe uma possibilidade de mesmo uma chave que faça sentido, p. ex. “Chang” não seja utilizada;
3. Requer uma quantidade massiva de memória para acomodar o array.

Ainda, como mapear o nome p. ex. “aaaaaaaaad“ para o índice 4 do array?

Para tal é necessária uma função de, dada uma string de 10 caracteres (chave), retorne um inteiro que é o índice do array. Esta função é chamada:

• Função de mapeamento;
• Função de espelhamento;
• Função de hash.

Para que o esquema de armazenamento acima fosse útil, seria necessário um método de conversão da chave (um nome que faça sentido) para um inteiro (índice do array) dentro de uma faixa limitada.

Quaisquer duas chaves não devem ser convertidas/mapeadas para o mesmo índice. Podemos limitar o tamanho do array de indexação para uma faixa mais gerenciável se limitarmos o tamanho da chave a ser utilizada. Por exemplo, utilizando apenas dois caracteres teríamos:

O problema com tal limitação ocorre quando desejamos mapear duas chaves que começam com as mesmas letras. Por exemplo:

"adelio" -> (4)
"ademar" -> (4)

Função Hash

A função Hash ou função de espalhamento é o conceito central que fundamenta as tabelas Hash.

1public static int mapHash(String nome) {
2    int id1 = retornaIndiceNoAlfabeto(nome.charAt(0));
3    int id2 = retornaIndiceNoAlfabeto(nome.charAt(1));
4    return (26 * (id1 - 1)) + id2;
5}

A função Hash perfeita

Uma função de espalhamento perfeita mapeia todos os elementos de um conjunto de entradas C (chaves) para um conjunto de inteiros. Em essência, chamamos a função de espalhamento de perfeita se ela é uma função bijetora.

Se todas as chaves são conhecidas a priori, uma função de espalhamento perfeita pode ser usada para criar uma tabela de espalhamento perfeita que não apresentará nenhuma colisão.

A grande vantagem de espalhamento perfeito é o fato de que pesquisas em tempo constante serem possíveis. Tal fato contrasta consideravelmente com os modelos de endereçamento aberto ou encadeamento, onde o tempo de pesquisa é em geral baixo mas que pode vir a ser muito longo para alguns casos.

Escolhendo boas funções de espalhamento

Uma boa função de espalhamento é essencial para garantir boa performance em tabelas de espalhamento. Uma função de espalhamento não adequada para as chaves em questão tende a degradar o desempenho geral da tabela de espalhamento. No entanto, é importante ter em mente que a função de mapeamento compraz apenas uma pequena parte do todo a ser computado em uma tabela de espalhamento.

Um requisito básico para garantir o bom desempenho da função de espalhamento é que ela deve prover uma distribuição uniforme dos valores de espalhamento. Uma distribuição não uniforme tende a aumentar o numero de colisões assim como o custo associado para resolvê-las. Uniformidade na distribuição é em geral difícil de ser obtida, no entanto ela pode ser avaliada empiricamente via testes estatísticos. Note que a distribuição precisa ser uniforme apenas para tabelas de tamanho N que ocorrem na aplicação. Uma boa prática, no caso em que o array de índices seja atualizado dinamicamente é atualizar o tamanho do array para sempre exatamente o dobro ou metade do tamanho do array. Desta forma, é mais fácil garantir a uniformidade da função de mapeamento, bastando que a mesma seja atualizada em potência de 2.

Colisões

Uma colisão é definida como sendo o cálculo de um mesmo índice para duas chaves distintas.

Como visto anteriormente, a única forma de evitar que colisões ocorram no momento em que a função de espalhamento calcula o endereço de uma dada chave é sabendo a priori todas as possíveis chaves, o que leva a criação de uma função de espalhamento perfeita.

No entanto para a maioria das aplicações práticas, trabalha-se com funções de espalhamento que invariavelmente induzirão que eventualmente colisões ocorram. Existem diversas maneiras de se lidar com colisões. As duas maneiras mais usadas são:

1. Endereçamento Aberto: No endereçamento aberto elementos são inseridos nas posições calculadas pela função de espalhamento diretamente. Quando uma colisão ocorre, o registro que colide será inserido na próxima posição livre da tabela de espalhamento;
2. Encadeamento Separado: Ao invés de indexar um registro diretamente para o índice calculado com base em sua chave pela função de espalhamento, o registro é indexado

em uma estrutura de dados suplementar tal como uma lista encadeada. Quando uma colisão ocorre, o registro que colide é inserido na lista encadeada.

Considerações

Digamos que o ideal seria um conjunto de um pra um, em teoria, e para achar um elemento, bastava fazer o cálculo da chave e o acesso seria muito rápido. Contudo, precisaríamos de um vetor grande o suficiente para alocar TODAS as possíveis variações e isso, conforme o problema, principalmente os np-completos, seria inviável computacionalmente.

Então criamos vetores bem menores e lá colocamos os dados que vão chegando e tomamos por princípio que não precisaremos alocar todas as possíveis variações nessa estrutura, pelo menos esperamos que não. E quando temos um conflito, tem uma lista ali para receber os códigos que fecham na mesma chave.

Em resumo, as Tabelas Hash, são um tipo de estrutura para quebrar uma lista em partes, e porque fazemos isso? Porque pesquisar numa lista encadeada é complicado, temos que navegar toda ela até chegar no elemento que queremos. Se usar uma HASH de 4 chaves, quebraremos nossa lista em 4, a pesquisa tem a tendência de ser em torno de 4 vezes mais rápida, e por aí vai.

Exercícios

1. Calcule quantas posições seriam necessárias em um array para que o mesmo pudesse acomodar todas as possíveis chaves de “aaaaaaaaaaaa” a “zzzzzzzzzz”. Considere o alfabeto de 26 letras.
2. Quais são os dois tipos de colisões listados neste resumo? Descreva-os dando exemplos. (utilize diagramas para clarificar a explicação)
3. Quais são as duas condições necessárias para que uma função de espalhamento seja perfeita?
4. Explique a diferença entre índice e chave.
5. Site uma situação em que uma lista encadeada é mais indicada como estrutura de dados a ser escolhida e outra em que uma tabela de espalhamento é a melhor opção.
6. Caso as chaves utilizadas em uma tabela de espalhamento sejam strings, quais são as vantagens e desvantagens de se utilizar mais ou menos caracteres na função de espalhamento para o cálculo do índice no array de espalhamento?
7. Dê um exemplo em que a chave a ser utilizada não é uma string mas sim um valor numérico. Como seria a função de espalhamento neste caso?