Aula 014 - Tabela Hash (1)

Prévia do material em texto

Tabela Hash
2º Semestre
Prof. Stefano B. B. R. P. Mathias
Estrutura de Dados
AULA 14
Objetivos:
Entender sobre o que são Tabelas 
Hash.
Tópicos
• Introdução
• Hash
• Função de Hashing
• Exemplo de Hashing Perfeito
• Hashing Imperfeito
Tópicos (cont...)
• Colisões
• Exemplo de Hashing Imperfeito
• Tratamento de colisões: Lista encadeada
• Tratamento de colisões: Endereçamento aberto
Introdução
• Conforme visto na aula anterior, os métodos de busca procuram um
valor comparando este com cada elemento de um conjunto de
dados.
• Para que os métodos de busca sejam mais eficientes, os elementos
desse conjunto devem ser ordenados, mas sabemos que a ordenação
de um conjunto possui um custo adicional.
• Sabendo disso, com o objetivo de possuir um método de busca
eficiente, o mesmo deve armazenar os elementos do conjunto de
forma ordenada para tirar proveito disso no futuro.
Hash
• Existe uma outra forma de se armazenar e buscar elementos de uma
coleção que é a utilização de Tabelas Hash (também conhecida como
Tabela de Dispersão ou Espalhamento).
• Os elementos são armazenados em uma tabela que é endereçada a
partir de uma transformação aritmética (uma função) sobre a chave
de pesquisa.
• Para utilizar hash, podemos utilizamos uma estrutura de dados
conhecida como dicionário (que é uma generalização de um vetor).
Um dicionário possui uma chave e um valor.
Hash (cont...)
Exemplo:
Função de Hashing
• O sucesso da Tabela Hash está condicionado a escolha (ou criação) de
uma boa função de Hashing, já que a mesma é responsável por
receber uma chave e retornar um índice.
• Uma função de Hashing ideal é aquela que não possua colisões, seja
fácil de processar e que faça os elementos da tabela Hash ficarem
espalhados de maneira uniforme.
• Para que a mesma não possua colisões, a função deve ser injetora ou
bijetora.
Exemplo de Hashing Perfeito
Exemplo: Considere armazenar os dados dos alunos de uma turma de
um determinado curso. Cada aluno possui um RA numérico com 7
dígitos e esse é utilizado para identifica-lo.
• Os dados a serem armazenados do aluno serão: o número da
matrícula, seu nome e seu e-mail.
• Para guardar as informações de cada aluno, precisaremos de 4 bytes
para a matrícula e 200 bytes para armazenar um nome e um e-mail
com no máximo 100 caracteres cada um.
• Se quisermos o acesso a cada aluno em tempo constante O(1)
poderíamos utilizar a matrícula como índice da tabela Hash.
Exemplo de Hashing Perfeito (cont...)
• Só que para isso, iriamos pagar um preço alto por armazenamento,
pois teríamos que criar um array com 10.000.000 de posições (a
matrícula começa com o número 0.000.000 e vai até o número
9.999.999).
• 10.000.000 x 200 bytes = 2.000.000.000 => 2Gb.
• Então para economizar espaço em disco, mas ainda utilizar um
hashing perfeito devemos identificar as partes significativas da
chave.
Exemplo de Hashing Perfeito (cont...)
• Supondo que a turma seja do 1º Semestre de 1997 do Curso de
Engenharia, uma função que retorna o hashing perfeito seria:
Hashing Imperfeito
• Quando duas ou mais chaves distintas do conjunto A são submetidas
a função de hashing e as saídas são iguais, conclui-se que a função de
hashing é imperfeita.
• Uma função de hashing imperfeita é uma função Sobrejetora.
• Essa situação é chamada de colisão e existem alternativas para tratar
esse tipo de situação.
Colisões
• É comum o acontecimento de colisões, pois não se pode garantir que
as funções de hashing tenham uma boa distribuição dos endereços.
• Geralmente ocorre quando o número de chaves possíveis é muito
maior que o número de endereços disponíveis nas tabelas.
• Para contornar esse problema, pode-se utilizar listas encadeadas ou
endereçamento aberto.
Exemplo de Hashing Imperfeito
Exemplo: Armazenar o nome MÁRIO em um vetor de 5 posições.
• Cada letra do nome será uma chave, logo, M Á R I O.
• A função de hashing retornar o resto da divisão entre a posição da letra na
tabela ASCII e o tamanho do vetor.
Letra Código ASCII Função de hashing Endereço
M 77 77 mod 5 2
Á 193 193 mod 5 3
R 82 82 mod 5 2
I 73 73 mod 5 3
O 79 79 mod 5 4
Tratamento de colisões: Lista encadeada
• Cada posição de endereço da tabela deve apontar para uma lista.
• Cada inclusão na tabela poderá inicializar uma lista e incluir o
elemento na mesma.
• A função de hashing deverá ser “boa” para evitar uma grande lista
em cada posição de endereço.
Tratamento de colisões: Lista encadeada 
(cont...)
Tratamento de colisões: Lista encadeada 
(cont...)
Tratamento de colisões: Endereçamento 
aberto (cont...)
• Essa abordagem não utiliza listas encadeadas e nenhuma outra
informação adicional.
• Basicamente quando ocorrer uma colisão, existirá um cálculo que
indicará o próximo endereço no qual a informação deverá ser
buscada.
• Para inclusão de elementos, o calculo de endereços será realizado até que
um endereço vazio seja encontrado.
• Para buscar um elemento, o calculo de endereços será realizado até
encontrar o elemento procurado (podendo encontrá-lo ou não).
Tratamento de colisões: Endereçamento
aberto (cont...)
• Uma opção para a aplicação do Endereçamento aberto é a sondagem
linear.
Exemplo: considere o mesmo exemplo para armazenar a palavra
MÁRIO. A função de hashing possui um novo parâmetro k, que indica
quantos endereços a mais serão necessários para a alocação.
Tratamento de colisões: Endereçamento
aberto (cont...)
• O fato da inclusão ser feita na ordem de escrita da palavra, faz com
que determinados caracteres sejam movidos para outras posições.
• Essa abordagem, transforma a tabela de endereços em uma
referência circular, ou seja, após calcular o hash e chegar até a última
posição da tabela, o processo é repetido do começo para garantir
que a tabela está cheia.
M -> Endereço 2 + k = 0 -> 2
Á -> Endereço 3 + k = 0 -> 3
R -> Endereço 2 + k = 2 -> 4
I -> Endereço 3 + k = 2 -> 0
O -> Endereço 4 + k = 2 -> 1
Tratamento de colisões: Endereçamento
aberto (cont...)
Tratamento de colisões: Endereçamento
aberto (cont...)
Problemas:
• Pode aumentar a complexidade para buscar/remover um elemento em caso
de colisão.
• Em caso de inserção de elementos, fica limitado ao tamanho da tabela.
• Pode criar um bloco de dados que ficam e uma mesma região.
Referências
• Crédito de conteúdo a professora: Cristina Boeres.
• Notas de aula da professora citada acima: 
http://www2.ic.uff.br/~boeres/slides_ed/ed_TabelaHash.pdf
• Tabela ASC II: 
https://marquesfernandes.com/desenvolvimento/codigo-ascii-
tabela-ascii-completa/
• Conteúdo sobre funções: 
https://www.somatematica.com.br/emedio/funcoes/funcoes6.php
Referências (cont...)
• Interface map do Java: https://www.devmedia.com.br/conhecendo-
a-interface-map-do-
java/37463#:~:text=Essa%20interface%20%C3%A9%20um%20objeto,
faz%20parte%20do%20pacote%20java
• Implementações no GitHub: 
https://github.com/bluyus/AulasEstruturaDados