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.
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 1).
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.
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(1) 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.
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.
2 comentários :
Bah, ninguém comentou ainda hsuahsuahs
Não conseguiram nem respirar vendo tanto hash..mas eu entendo, atualmente faço a cadeira de estruturas avançadas de dados no curso de ciência da computação na Unisinos no RS.
Estou vendo as subsequentes funções do hash.
abraço!!
Me dói os olhooooos
aaaaaaaaah eu estou ficando cego suahsuhasu
muito bom o post
Postar um comentário