Estruturas de dados para IA III

Prévia do material em texto

Estruturas de dados para IA III	
APRESENTAÇÃO
As tabelas hash, também conhecidas como tabelas de dispersão ou tabelas de espelhamento, são 
responsáveis pelo armazenamento de coleções de valores, em que cada valor estará associado a 
uma chave. A utilização das tabelas hash varia desde aplicações simples, como sistemas de 
armazenamento de dados, até sistemas complexos, como de mapeamento de tráfego aéreo. Por 
meio do desenvolvimento das tabelas hash, também foi possível evoluir em estudos sobre a 
utilização de ponteiros para tratamento de conflitos, quando temos o armazenamento de 
múltiplos dados, como, por exemplo, em tecnologias de Big Data.
Nesta Unidade de Aprendizagem, você estudará o funcionamento das tabelas hash ou tabelas de 
dispersão, discutindo a ocorrência de colisões nas tabelas hash e sua respectiva implementação 
por meio da linguagem Python.
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Definir tabelas hash.•
Discutir a resolução de colisões em tabelas hash.•
Implementar tabelas hash em Python.•
DESAFIO
Em uma empresa de soluções por meio de inteligência artificial, foi solicitada a criação de uma 
base de dados distribuída que se utiliza de aprendizagem de máquina (machine learning).
Foi sugerido então que a base de dados distribuída fosse um data mart, que é um subconjunto de 
um DW (data warehouse) responsável por segmentar a base por determinado conhecimento.
Logo, conforme a base de dados (data mart) fosse aprendendo por tentativa e erro, esse 
conhecimento deveria ser armazenado em uma tabela que atrelasse determinado conhecimento a 
uma chave única, evitando, assim, que determinado conhecimento fosse repetido.
Imagine que você é o profissional responsável por essa demanda. Caso ocorra duplicidade no 
armazenamento do data mart, qual mecanismo você poderia utilizar para tratar as colisões, 
evitando overflow?
INFOGRÁFICO
As tabelas hash, ou tabelas de dispersão, são conhecidas por implementarem mecanismos de 
tratamento de colisões, aprimorando, assim, o processo de armazenamento de dados. A 
resolução de conflitos por meio das tabelas hash também ajudou na evolução de sistemas 
embarcados, onde a limitação de memória gerava as colisões de dados, que por meio de tabelas 
hash podem ser evitadas e tratadas. 
No infográfico a seguir, veja a apresentação de duas resoluções para colisões em uma tabela 
hash, demonstrando o funcionamento da colisão na associação de valores e chaves. 
 
CONTEÚDO DO LIVRO
As tabelas hash são estruturas de dados fundamentais na resolução de colisões que ocorrem no 
armazenamento de dados. Logo, são fundamentais o tratamento e a resolução de colisões a fim 
de que o processamento e armazenamento de dados de diversos tipos de sistemas ocorram de 
forma eficaz. 
Neste capítulo, são abordadas as principais características da estrutura de dados conhecida como 
tabela hash ou tabela de dispersão, com abordagem da linguagem de programação Python. São 
definidas as tabelas hash, suas colisões e sua implementação em linguagem Python.
Leia o capítulo Estruturas de dados para IA III, da obra Inteligência artificial, base teórica desta 
Unidade de Aprendizagem.
Boa leitura.
INTELIGÊNCIA 
ARTIFICIAL
Pedro Henrique Chagas Freitas 
Estrutura de dados 
para IA III
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
 � Definir as tabelas hash.
 � Analisar a resolução de colisões em tabelas hash.
 � Implementar as tabelas hash em Python.
Introdução
Neste capítulo, você estudará o funcionamento das tabelas hash, a re-
solução de colisões nelas e sua implementação por meio da linguagem 
Python.
Tabelas hash
As tabelas hash também são conhecidas como tabelas de dispersão ou de 
espelhamento e responsáveis pelo armazenamento de coleções de valores, em 
que cada valor está associado a uma chave (PERKOVIC, 2016). As chaves, 
por sua vez, devem ser distintas e utilizadas para realizar o mapeamento dos 
valores nessa tabela, sendo que a função que faz esse mapeamento, na maioria 
dos casos, se chama hashing (COPPIN, 2010).
Um exemplo clássico é a implementação de uma tabela de dispersão com 
um vetor, que, neste caso, terá oito posições, logo, a função hashing será h(x) 
= x MOD 8. Utiliza-se o MOD porque ele representa o resto de uma divisão, 
como 10 MOD 8 = 2, em que 10/8 equivale ao quociente 1 e resto 2 ou 8*1 
+ 2 = 10.
Pode-se sugerir que a função h(k) é a posição original da chave k, a qual 
deve ser inserida nessa posição da tabela (DROZDEK, 2017). Assim, realiza-se 
a inserção de uma coleção de valores, com suas respectivas chaves em uma 
tabela de dispersão, conforme você pode ver no Quadro 1.
ID Chave Valor
0
1 25 LIA
2 18 ANA
3
4
5 5 RUI
6
7 31 GUT
Quadro 1. Tabela de dispersão
Observe que, na tabela de dispersão no Quadro 1, há uma coleção de valores 
e suas respectivas chaves e posições (ID). Diante disso, o valor GUT foi inserido 
na posição (ID) 7 do quadro, considerando que a chave associada a ele é 31, 
logo h(31) = 7. O que ocorreria se fosse inserido na tabela o valor ROT com 
chave 33 na posição 1? Teria h(33) = 1, sendo que a posição 1 da tabela já está 
sendo ocupada, neste caso, as chaves 25 e 33 colidiram (DROZDEK, 2017). 
Assim, conclui-se que duas chaves x e y colidem, se h(x) = h (y).
Portanto, ocorrem colisões de chaves em uma tabela hash ou de dispersão, 
porque, na maioria das vezes, o domínio das chaves é maior que a quantidade 
de posições da tabela, sendo seu número de posições finito. Porém, não se pode 
negar a inserção de uma chave se a tabela tiver posições livres, por isso, foram 
criadas estratégias para lidar com essas colisões. Lembre-se que a utilização 
da função hashing é recomendada para inserção em uma tabela com muitos 
dados que tenham faixas de valores variáveis (COPPIN, 2010).
Fundamentalmente, as tabelas hash ou de dispersão implementam a inter-
ligação entre chaves e valores, realizando a resolução das colisões, o que tem 
uma aplicação prática em bancos de dados normalizados ou nos distribuídos. 
Nesses bancos, o controle de colisões é crítico, e a implementação dessas 
tabelas essencial para o encadeamento das chaves e dos índices de valores, 
conforme você pode observar no Quadro 1.
Estrutura de dados para IA III2
As tabelas de dispersão foram criadas com o objetivo de realizar buscas rápidas para 
a obtenção de valores desejados a partir de chaves. Alguns estudiosos atribuem sua 
criação ao trabalho de Hans Peter Luhn na International Business Machines (IBM), em 
1953, mas outros afirmam que as primeiras utilizações dessas tabelas ocorreram em 
1960, com compiladores e interpretadores da linguagem BASIC, usada na dispersão 
de variáveis e seu armazenamento (DROZDEK, 2017).
Figura 1. Dispersão de chaves e índices de valores na tabela hash.
Chaves
Índice 
de valores Hash de chaves e valores
:
:
0
1
872
873
874
998
999
John Smith
Lisa Smith
Sam Doe
Sandra Dee
+ 1-555-8976Lisa Smith
+1-555-5030Sam Doe
+1-555-9655Sandra Dee
+1-555-1234John Smith
Colisões em tabelas hash
Para entender as colisões em tabelas hash, a melhor forma é mostrando como 
uma colisão ocorre. Portanto, pressuponha que você tenha uma tabela de 
dispersão para armazenamento de valores, conforme as chaves, logo, haverá 
uma associação entre chave e valor, que responde aos seguintes parâmetros:
 � W, o número de posições na tabela hash ou de dispersão.
 � K, o número de chaves de outra tabela (chamada tabela key).
 � X, o fator de associação entre as duas tabelas (X = K/M).
3Estrutura de dados para IA III
A partir disso, você precisa aplicar uma função de associação entre as 
chaves da tabela key e as posições da tabela de dispersão, ocorrendo a função 
hashing, responsável por transformar cada chave em um índice da tabela hash 
(DROZDEK, 2017). Logo, essa função implementa a seguinte requisição: 
“qual posição da tabela hash deverá ser associadaàs chaves da tabela key”. 
Assim, a função hashing inicializa uma alocação dinamicamente das chaves 
na tabela de dispersão, associando esta à tabela key.
A função hashing ainda associa um valor hash, entre 0 e W – 1, a cada 
chave. Por exemplo, caso existam cadastros de pessoa física (CPF) como chave 
(lembrando que eles podem ser chaves, pois não se duplicam) e a necessidade 
de associá-los aos registros gerais (RG), estes seriam a tabela hash; e CPF, 
a tabela key.
Consequentemente, a função hashing produziria ao longo da associação 
diversas colisões, que ocorrem quando duas chaves diferentes têm valor igual 
para essa função e são alocadas na mesma posição da tabela hash, conforme 
você pode conferir nos Quadros 2 e 3.
Chave Índice Valores
a 2 xyz
b 0 pqr
c 3 ijk
d 2 uvw
e … …
f … …
g … …
h … …
Quadro 2. Tabela hash
Estrutura de dados para IA III4
Índice da tabela hash Chaves/valores
0
1
2
3
… (W – 1) … (W – 1)
Quadro 3. Tabela hash
Observe que houve colisões no índice hashing com associação da chave 2 
duas vezes, respectivamente com as chaves a e d e os valores xyz e uvw. Como 
foi citado anteriormente, esse tipo de situação é comum em banco de dados, 
quando há a indexação de uma grande quantidade de dados em tabelas, logo, 
as tabelas hash ou de dispersão costumam utilizar vetores na função hashing 
para realizar a associação entre as tabelas (COPPIN, 2010).
Logo, conclui-se que há colisões quando os vetores apontarem para o 
mesmo índice ou a função hashing coincidir duas chaves diferentes para o 
mesmo índice, como ocorreu no exemplo anterior, com as chaves a e d. Por-
tanto, colisões são normais, mas a função hashing pode ser acompanhada de 
diversas estratégias ou outras funções para evitar ao máximo o número de sua 
ocorrência. Por melhor que seja o projeto da tabela hash, ela sempre terá coli-
sões, assim, deve-se implementar também o mecanismo de tratamento delas, 
que dependem diretamente da finalidade para a qual essa tabela é utilizada. 
Há dois mecanismos padrões que auxiliam no tratamento das colisões em 
tabelas hash: o endereçamento aberto e o encadeamento. No endereçamento 
aberto, tem-se o armazenamento de colisões na própria tabela, ocorrendo a 
5Estrutura de dados para IA III
busca por colisões e a resolução com a alocação destas em registros vazios, 
cuja inserção segue a lógica first in, first out (FIFO) na qual se resolve as 
colisões conforme elas são encontras (COPPIN, 2010). O problema desse tipo é 
que cria uma sobrecarga na estrutura em que fica a tabela, pois, à medida que 
há alocação, ocorrem as colisões e, em paralelo, a realocação dos elementos 
colididos, podendo-se adicionar lógicas paralelas para auxiliar na mitigação 
dessa sobrecarga (PERKOVIC, 2016).
Já no encadeamento, tem-se o atrelamento paralelo dos dados, assim, con-
forme há a associação da tabela hash e a ocorrência das colisões, realiza-se o 
armazenamento dos dados em estruturas encadeadas fora dessa tabela. Dessa 
forma, os elementos são armazenados em duas posições, uma de armazena-
mento na tabela e outra encadeada paralelamente. Caso aconteça uma colisão, 
busca-se na tabela encadeada outra posição até verificar uma que a resolva, 
armazenando-a nesta (DROZDEK, 2017).
Conclui-se que as tabelas hash são estruturas de dados que não permi-
tem o armazenamento repetido de elementos, por isso, haverá colisões e seu 
tratamento.
Tabelas hash em Python
A seguir, você pode visualizar a implementação de uma tabela de dispersão 
utilizando a linguagem Python. Nesse caso, utiliza-se a classe hash, oriunda 
das bibliotecas do Python, para implementar a função hashing e os métodos 
necessários para a criação da tabela, inserindo comentários nas linhas do 
código.
 
# Tabela Hash
class Hash: 
 def _ _ init _ _ (self,tam): 
 self.tab = {} 
 self.tam _ max = tam 
 def funcaohash(self, chave): 
 v = int(chave) 
Estrutura de dados para IA III6
 return v%self.tam _ max 
 def cheia(self): 
 return len(self.tab) == self.tam _ max 
 def imprime(self): 
 for i in self.tab: 
 print("Hash[%d] = " %i, end="")
 print (self.tab[i])
 def apaga(self, chave):
 pos = self.busca(chave)
 if pos != -1:
 del self.tab[pos]
 print("-> Dado da posicao %d apagado" %pos) 
 else:
 print("Item nao encontrado")
 def busca(self, chave):
 pos = self.funcaohash(chave)
 if self.tab.get(pos) == None: 
 return -1 
 if self.tab[pos] == chave: 
 return pos
 return -1
 def insere(self, item):
 if self.cheia():
 print("-> ATENÇÃO Tabela Hash CHEIA")
 return
 pos = self.funcaohash(item)
 if self.tab.get(pos) == None: 
 self.tab[pos] = item
 print("-> Inserido HASH[%d]" %pos)
 else: 
 print("-> Ocorreu uma colisao na posicao %d" %pos) 
# Fim da tabela Hash
7Estrutura de dados para IA III
# Início do tratamento de colisões na tabela hash, utilizando 
busca por endereçamento aberto
tamanhoHash = 7
tab = Hash(tamanhoHash)
print("\n")
print(" Tabela HASH Sem Colisões (%d itens) " %tamanhoHash)
for i in range (0,tamanhoHash,1):
 print("\nInserindo elemento %d" %(i + 1));
 item = input(" - Forneca valor numerico inteiro: ")
 tab.insere(item)
item = input("\n - Insira o valor numérico inteiro para bus-
car: ")
pos = tab.busca(item)
if pos == -1:
 print("Item não encontrado")
else:
 print("Item encontrado na posição: ", pos)
item = input("\n – Insira o valor numérico inteiro para apa-
gar: ")
tab.apaga(item)
print("\nImprimindo conteudo")
tab.imprime()
print("\n")
COPPIN, B. Inteligência artificial. Rio de Janeiro: LTC, 2010. 664 p.
DROZDEK, A. Estrutura de dados e algoritmos em C++. 4. ed. São Paulo: Cengage Lear-
ning, 2017. 708 p.
PERKOVIC, L. Introdução à computação usando Python: um foco no desenvolvimento 
de aplicações. Rio de Janeiro: LTC, 2016. 516 p.
Estrutura de dados para IA III8
DICA DO PROFESSOR
Quando ocorrem colisões em tabelas hash, é possível resolvê-las por meio de dois mecanismos-
padrão: o endereçamento aberto e o encadeamento. No endereçamento aberto, temos o 
armazenamento das colisões dentro da própria tabela hash.
Nesta Dica do Professor, acompanhe o funcionamento dos mecanismos de endereçamento 
aberto e encadeamento para resolução de colisões em tabelas hash. 
Conteúdo interativo disponível na plataforma de ensino!
 
EXERCÍCIOS
1) As tabelas de dispersão, ou tabelas hash, também são conhecidas como tabelas de 
espelhamento, tendo em vista que nelas os valores armazenados estarão associados 
diretamente a uma chave. Determine o valor da chave para o elemento 22, por meio 
da função hashing h(x) mod y, onde y = 10.
A) 9.
B) 2.
C) 7.
D) 8.
E) 4.
2) 
Em uma tabela de dispersão, a função que realiza o mapeamento dos valores dentro 
da tabela se chama função hashing.
Determine o valor da chave de associação onde ocorre uma colisão entre os elementos 
5 e 10, considerando a tabela hashing h(x) 2 mod w, onde w = 5.
A) 3.
B) 4.
C) 1.
D) 2.
E) 0.
3) Em uma tabela de dispersão, as duas principais colunas que vão referenciar os 
vetores são o índice, a chave e o valor. Na resolução de colisões por meio do 
endereçamento aberto, em qual posição deverá ser armazenado o elemento colidido?
A) Após o primeiro elemento armazenado.
B) Após a primeira posição do índice.
C) Após a última posição livre do índice.
D) Antes da primeira posição ocupada do índice.
E) Antes da última posição livre do índice.
4) 
Conforme a associação é realizada em uma tabela hash, podem ocorrer colisões. Os 
dois mecanismos de tratamento de colisões que realizam o armazenamento das 
colisões para busca de alocações em lugares que estejamvazios são:
A) endereçamento aberto e encadeamento.
B) endereçamento fechado e endereçamento.
C) encadeamento aberto e vetorização.
D) encadeamento aberto e atrelamento.
E) endereçamento vazio e orquestramento.
5) Diante das colisões que ocorrem em uma tabela hash, o mecanismo para tratamento 
de colisões que realiza o atrelamento paralelo dos dados por meio do armazenamento 
em estruturas fora da tabela hash é chamado de:
A) endereçamento.
B) vetorização.
C) referenciamento.
D) encadeamento.
E) atrelamento.
NA PRÁTICA
As implementações de wikis ocorrem com o atrelamento de conhecimentos a chaves, formando, 
assim, bibliotecas que se referenciam por temas. Nessas bibliotecas, por meio das tabelas hash, é 
possível ter páginas únicas sobre determinado assunto.
Veja a seguir como esse processo ocorre, por exemplo, na Wikipédia.
 
SAIBA MAIS
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do 
professor:
Tabelas hash
Veja neste vídeo uma contextualização sobre a estrutura das tabelas hash. 
Conteúdo interativo disponível na plataforma de ensino!
Tabela hash – tratamento de colisões
Veja neste vídeo o tratamento de colisões por meio de associações de chaves e valores em 
tabelas hash.
Conteúdo interativo disponível na plataforma de ensino!
Calculando colisões em um hash uniforme
Este vídeo mostra um exercício de demonstração do cálculo de colisões em uma tabela hash 
uniforme.
Conteúdo interativo disponível na plataforma de ensino!