aula02

Prévia do material em texto

2ºAula
TABELAS HASH
Objetivos de aprendizagem
Ao término desta aula, vocês serão capazes de: 
• entender o que são tabelas Hash;
• compreender o que é a função de dispersão;
• saber como tratar colisões.
Olá,
Nesta aula, vamos abordar mais uma estrutura fundamental 
para a Computação: as Tabelas Hash. Essas tabelas fornecem 
uma forma de armazenamento que permite uma busca rápida 
dos dados, desde que a pessoa conheça a chave. 
Leiam atentamente esta aula e façam os exercícios. Se 
enfrentarem alguma dúvida, estaremos a sua disposição na área 
do aluno.
Bons estudos!
15
Estrutura de Dados II 14
Seções de estudo
1. Entendendo o problema e o que são as Tabelas 
Hash
2. Resolvendo Colisões
1 - Entendendo o problema e o que 
são as Tabelas Hash
Na disciplina de Estruturas de Dados I, vocês viram 
algoritmos para resolver dois problemas, que são considerados 
elementares na Computação: a Ordenação e Busca.
Em relação a busca, vocês viram que podemos resolver 
de duas formas. Quando temos um conjunto linear de dados 
não-ordenados, usualmente fazemos a busca de maneira 
sequencial, percorrendo elemento por elemento. Já quando 
temos um conjunto de elementos ordenados, podemos usar 
a busca binária para conseguirmos uma resposta mais rápida. 
Porém, em certas situações, nem sempre a busca binária 
pode ser a melhor solução para buscar um dado. Sendo assim, 
vamos falar sobre, um novo conceito, o dicionário de dados. 
Podemos denominá-lo como um conjunto dinâmico de 
dados, onde em cada elemento há um subconjunto de dados 
- ou seja, um registro - no qual um desses dados satélites é 
uma chave, para que o acesso aos dados seja realizado.
Em um dicionário de dados, podemos definir as 
seguintes operações:
• Busca: dado um dicionário de dados S e um 
item K, consiste em retornar um ponteiro para o 
elemento X do conjunto, onde X.chave = K.
• Insere: dado um dicionário S e um ponteiro para 
o registro X, o método consiste em adicionar o 
elemento X ao dicionário.
• Remove: dado um dicionário S e um ponteiro para 
o registro X, o método consiste em remover um 
item X ao dicionário.
Definido esse conceito, vamos apresentar o problema 
que justifica a criação dessa estrutura de dados. Esse problema 
ocorre quando temos muitos dados para ser armazenados e 
precisamos armazená-los, de forma que a busca seja rápida. 
Vamos ver alguns contextos que se encaixam nesse cenário.
• Contexto nº 1: suponhamos que você trabalha 
em uma operadora de telefonia. Neste momento, 
a operadora está cuidando de 1 milhão de telefones, 
onde em cada telefone há um cliente associado, 
que é identificado pelos seus dados pessoais (RG, 
CPF, Endereço, Cidade etc). Nesta operadora, o 
atendimento é iniciado quando o cliente informa o 
número de telefone associado. Assim, é necessário 
que a empresa implemente um sistema eficaz de 
busca de clientes pelo número de telefone associado;
Figura 1 - Amostra de dados aplicada ao Contexto Nº 1, mostrando os dados 
relacionados a um número de telefone.Fonte: Acervo Pessoal.
• Contexto nº 2: o Banco Nacional das Couves está 
implantando um novo sistema para armazenar 
os dados dos clientes. Os clientes são indexados 
pelo número da conta associada. Além disso, são 
armazenados os dados da conta neste registro 
(como saldo, histórico de transferências etc). Esse 
banco usa a mesma sequência de numeração para 
todas as contas, onde esse número pode chegar 
de 000.000 a 799.999. Da mesma forma que o 
contexto anterior, o cliente informa o número da 
sua conta para iniciar seu atendimento. Assim, 
é fundamental um sistema de busca eficaz pelo 
número da conta.
Figura 1 - Amostra de dados aplicada ao Contexto Nº 2, mostrando os dados 
relacionados a um número de conta.Fonte: Acervo Pessoal.
Os dois contextos apresentados são diferentes, 
mas são semelhantes entre si. Há uma necessidade pelo 
armazenamento de um grande número de dados, sendo 
que são indexados por uma chave.
Se analisarmos as estruturas de dados que 
apresentamos, veremos que podemos resolver esse 
problema. Mas, algumas situações podem ocorrer:
• Se armazenarmos em um vetor, podemos 
armazenar cada registro em um item do vetor. 
E assim, bastará indicar a respectiva chave para 
acessar imediatamente o elemento. Porém, 
independente, se tivermos 10, 1000 ou 1 milhão 
de clientes, temos que alocar a quantidade de itens 
a ser armazenados de forma prévia. Isso é ruim, 
pois estamos - em alguns casos - desperdiçando 
memória. No caso do banco, teremos que alocar 
800 mil posições, mesmo que tenhamos apenas 
100 clientes cadastrados.
• Se armazenarmos em uma lista ligada, poderíamos 
ter o armazenamento de forma incremental, 
salvando dados à medida que os dados estão 
sendo criados. O problema é que na lista ligada, 
temos que fazer a busca sequencial, o que pode 
causar uma degradação no desempenho. Imagine 
se buscarmos o cliente João das Flores, que 
está na última posição da lista de clientes da 
operadora telefônica. Teríamos que percorrer 
999.999 registros antes de chegarmos ao registro 
desejado.
 
Assim, chegamos a nossa solução: usar uma estrutura 
de dados que ofereça uma flexibilidade de armazenamento 
e recuperar um dado com poucas operações. Podemos 
criar um vetor de n posições, onde em cada elemento é 
armazenado um registro.
Para que possamos armazenar os dados, usamos uma 
regra: através da chave, computamos uma função para 
definir qual será a posição que armazenaremos o item. Por 
exemplo, definimos que o resto da divisão da chave pelo 
16
15
número de elementos do vetor será o lugar para onde irá 
o dado.
Figura 3 - Exemplo de Tabelas Hash. Fonte: Acervo Pessoal.
Você não deve ter percebido, mas acabamos de 
mostrar o conceito das tabelas de dispersão ou tabelas 
hash. Formalmente, podemos definir como uma estrutura 
aplica uma função aritmética f(k) em uma chave k, e através 
dessa função, temos o endereço de armazenamento do 
dado na tabela - nome a qual damos esse vetor.
Essa estrutura foi concebida com a ideia do acesso 
randômico à memória, onde os dados podem ser 
armazenados em lugares diferentes na memória. Assim, ao 
termos uma chave computada por meio de uma fórmula, 
podemos acessar rapidamente o dado que desejamos.
Mas, que nome dar a esta função que calcula qual é a 
posição? Veremos a seguir.
1.1 - Função de dispersão
Para a função f(k) que computa qual será a posição de 
armazenamento é dado o nome de função de dispersão. 
Autores da área sempre recomendam que uma boa 
função de dispersão deve distribuir de forma uniforme os 
elementos pelos endereços e ser facilmente computado, 
ou seja, a função não deve demorar para computar a 
chave, caso contrário, perdemos os ganhos que obtivemos 
com essa estrutura de dados.
Existem várias formas de calcular o endereço de 
armazenamento. Vejam:
• Método da divisão: é o nome do método 
que usamos na nossa explicação. Consiste em 
dividir a chave pelo tamanho da tabela e, assim, 
aproveitarmos o resto da divisão. Então, se 
queremos armazenar o elemento com a chave 
80 em uma tabela com 11 posições, fazemos o 
seguinte cálculo:
f(80) = 80 mod 11 = 3
O resto da divisão - neste caso, 3, - será o endereço 
onde o elemento X será armazenado. De acordo com 
Cormen et. al. (2012) para que a função tenha um bom 
desempenho, o tamanho da tabela deve ser um número 
primo e não próximo de uma potência de 2. 
Figura 3 - Exemplo do método da divisão. Fonte: Acervo Pessoal.
• Método da dobra: consiste em fazer “dobras” 
sucessivas nos dígitos da chave, somando os 
números que serão sobrepostos, sem considerar 
o “vai-um”. Essa operação prossegue até que seja 
obtido o número de dígitos desejado para a chave.
Figura 4 - Exemplo do método da dobra. Fonte: NONATO, 2003.
• Método da multiplicação: existem diversas 
variações deste método. A mais conhecida é o 
método do meio quadrado, que consiste na seguinte 
regra: multiplica-se a chave por ela mesma, e o 
resultado é convertido em uma palavra de n bits. 
Dessa palavra, aproveitamosos números centrais, 
que passam a ser o endereço do elemento X. 
Szwarcfiter (1994) relata que se separarmos 10 
bits desse cálculo, teremos 1024 endereços base. 
A seguir veremos um exemplo:
f(34) = 34*34 = 1156 = 0000 1156 = 0011
Apesar de termos bons algoritmos de cálculo de 
17
Estrutura de Dados II 16
endereços de armazenamento, as vezes é inevitável que dois 
elementos sejam designados (mapeados) para o mesmo 
endereço. Quando isso ocorre, temos uma colisão. Por 
exemplo, se usarmos uma tabela com 11 posições, e usarmos 
o método da divisão, as chaves 33 e 99 serão designados para 
o mesmo endereço 0. 
Figura 5 - Situação de uma colisão em uma tabela hash.Fonte: Acervo Pessoal.
Mas, existem soluções interessantes para resolver essa 
situação. Veremos isso na seção a seguir.
2 - Resolvendo Colisões
Existem várias soluções que podemos adotar para 
resolver o problema das colisões. Vejamos a partir de agora.
2.1 - Encadeamento Fechado
Para essa situação, usamos uma lista encadeada em cada 
uma das posições da tabela. Assim, a posição pode armazenar 
vários elementos que forem mapeados pela mesma posição, 
sem a preocupação de termos um limite. Ou seja, todos os 
elementos que forem mapeados para o mesmo endereço vão 
ser inseridos em uma mesma lista.
Figura 6 - Demonstração do encadeamento fechado. Fonte: Acervo Pessoal.
A vantagem é que o número de elementos a ser 
mapeados na busca é reduzido, dependendo da qualidade 
da função de dispersão. Porém, temos como desvantagens 
o uso de um campo extra para os ponteiros de ligação e a 
necessidade de adotarmos um tratamento especial para as 
chaves, pois teremos um elemento inserido diretamente na 
tabela e elementos inseridos na lista encadeada. 
Uma solução que podemos adotar para contornar 
isso é transformar a tabela de endereços em uma tabela 
de ponteiros, em que cada ponteiro aponta para a lista 
correspondente. Assim, armazenamos todos os elementos 
diretamente nas listas.
correspondente ao seu endereço. Fonte: Acervo Pessoal.
Vale lembrar que a eficácia dessa forma de armazenamento 
depende da eficácia da função de dispersão. Se muitos elementos 
forem mapeados para o mesmo endereço, poderemos ter uma 
lista longa, e assim, podemos ter problemas de desempenho.
mesmo endereço. Assim, podemos ter um problema de desempenho. Fonte: 
Acervo Pessoal.
2.2 - Hashing Linear
Este método consiste em armazenar os dados que são 
mapeados em um mesmo lugar em posições posteriores na 
tabela. Assim, ao invés de armazenarmos em uma tabela 
separada, colocamos todos os dados em uma mesma tabela, 
usando os espaços vagos. Quando um dado for mapeado em 
uma chave ocupada, o sistema procurará a primeira posição 
vazia da tabela para preencher este dado.
Figura 9 - Demonstração do método de Hashing Linear.Fonte: Acervo Pessoal.
18
17
 A vantagem dessa abordagem é a simplicidade de 
implementação. O problema é quando muitos dados são 
mapeados em uma mesma posição, fazendo que haja um 
agrupamento de dados em uma mesma área, e, da mesma 
forma que ocorre na abordagem anterior, pode ser mais 
demorado encontrar determinado dado.
Seção 2.3 - Hashing Duplo
 É considerado uma variação da abordagem anterior. 
Quando um dado for mapeado para uma posição ocupada 
na tabela, outra função de dispersão é chamada para calcular 
o incremento. Nesse exemplo, a chave 27 é mapeada na 
posição 3, já ocupada. Para resolver o problema calculamos 
um número extra para ser calculado junto com o resultado 
anterior, para que, assim, obtenhamos um novo endereço.
Figura 10 - Demonstração do método de Hashing Duplo.Fonte: Acervo Pessoal.
 A vantagem dessa abordagem é o espelhamento 
melhor das chaves. O problema desse método é que os 
elementos podem estar muito distantes um do outro, violando 
o princípio da localidade.
Atenção: As f rmulas aqui e pressas s estão para efeitos de 
demonstração. Você pode criar, através das premissas dos métodos 
mostrados nesta aula, a forma de calcular o endereço ou tratar 
colisões para a tabela em que você está trabalhando.
Uma boa função de dispersão, que evita muitas colisões, associada a 
uma forma de tratamento de colisões e ciente, pode fazer com que a 
sua tabela de dispersão seja rápida no processo de busca dos dados.
E assim, encerramos a nossa aula. Na próxima aula, 
vamos ver outra estrutura de dados: As árvores. Até mais!
Retomando a aula
Chegamos, assim, ao nal da segunda aula. Espera-se 
que agora tenha cado mais claro o entendimento de 
vocês sobre as tabelas Hash. Vamos, então, recordar?
1 - Entendendo o problema e o que são as Tabelas Hash
Nesta seção, vimos que as Tabelas Hash são estruturas 
que armazenam dados em uma tabela com n posições. A 
posição que o elemento será armazenado é definido por uma 
função de dispersão, que calcula esse endereço com base na 
chave. Existem vários tipos de funções de dispersão. Nesta 
aula, vimos também as três formas de criar a função de 
dispersão: Método da Divisão, Método da Dobra e Método 
da Multiplicação.
2 - Resolvendo Colisões
Nesta seção, vimos que uma colisão ocorre quando dois 
ou mais registros são mapeados para uma mesma posição. 
Para resolver esse problema, estudamos três soluções: 
Encadeamento Fechado (usamos listas encadeadas para 
armazenar os elementos que são designados para o mesmo 
endereço); Hashing Linear (consiste em armazenar os 
dados que são mapeados em um mesmo lugar em posições 
posteriores na tabela); e Hashing Duplo (quando usamos outra 
função para calcular uma nova posição a ser armazenada).
CORMEN, Thomas H.; et. al.. Algoritmos: teoria e 
prática. Rio de Janeiro: Campus, 2012.
KNUTH, Donald Ervin. The art of computer programming. 
3. ed. Amsterdam: Addison-Wesley, 1998.
SZWARCFITER, Jayme Luiz; MARKENZON, 
Lilian. Estruturas de dados e seus algoritmos. 2. ed. Rio de Janeiro: 
LTC, 1994.
Vale a pena ler
Vale a pena
FEOFILOFF, Paulo. Hashing. São Paulo: USP, 2017. 
Disponível em: <https://www.ime.usp.br/~pf/estruturas-
de-dados/aulas/st-hash.html>. Acesso em: 07 ago. 2018.
NONATO, Luis Gustavo. Método da Dobra. 
USP, 2003. Disponível em: <http://www.lcad.icmc.usp.
br/~nonato/ED/Hashing/node36-b.html>. Acesso em: 
08 ago. 2018.
RICARTE, Ivan L. M. Tabelas Hash. UNICAMP, 
2003. Disponível em: <http://www.dca.fee.unicamp.br/
cursos/EA876/apostila/HTML/node26.html>. Acesso 
em: 07 ago. 2018.
Vale a pena acessar
19
Estrutura de Dados II 18
DARELA, Vitor; ORLEÃES, Rafael. Tabelas 
Hash. Disponível em: <https://www.youtube.com/
watch?v=m891Sdamb3U>. Acesso em: 05 ago. 2018. 
PARALUPPI, Paulo. Tabelas Hash - Estrutura de 
Dados - Unicamp. Disponível em: <https://www.youtube.
com/watch?v=Non0I_OSt9o>. Acesso em: 03 ago. 2018. 
Vale a pena assistir
Minhas anotações
20