Hashing e Estruturas de Dados

Prévia do material em texto

estrutura de dados II – 60 horas
Prof: Juliano Ratusznei.
Email: juliano.ratusznei@unicid.edu.br
A teoria consiste em organizar os dados em estruturas semelhantes a fichários
Criar um índice por ordem alfabética e/ou numérica
Definir estruturas específicas para armazená-los
Separar os dados por tipos e assuntos
HASHING
2
 implementação de tabelas de símbolos por meio de:
 tabelas de dispersão => tabelas de hash.
Um tabela de símbolos é uma tabela com duas colunas:  
uma coluna de chave (keys) 
uma de valor. (values)
 Dizemos que cada linha da tabela é um item.  Cada item associa um valor a uma chave.
Vetores, matrizes, listas ligadas, pilha, fila, entre outros
HASHING – Tabela de símbolos (TS)
3
	chave 		valor
 www.ebay.com 	66.135.192.87
 www.princeton.edu 	128.112.128.15
 www.cs.princeton.edu 	128.112.136.35
 www.harvard.edu 	128.103.60.24
 www.yale.edu 	130.132.51.8
 www.cnn.com 	64.236.16.20
 www.google.com 	216.239.41.99
 www.nytimes.com 	199.239.136.200
 Hashing tem dois ingredientes fundamentais: 
uma função de hashing (estrutura de armazenamento com índices)
um mecanismo de resolução de colisões. (dados podem ser duplicados, evitar duplicatas)
HASHING
4
 Problemática
Imagine um pequeno país que possui 10 mil cidadãos. Considere que esta tabela leva o número do CPF e o nome do cidadão. 
Como armazenar a tabela?
HASHING
5
 chave 		valor
 0586	José Carlos
 0603	Alberto Santos
 0644	Ingrid Silva
 ...		 ...
 3675	Julio de Campos
 
 Como armazenar a tabela?
Vetor com 10 mil posições. Utilizamos a própria 
chave como índice do vetor.
O vetor é conhecido como “tabela de hash” e:
terá muitas posições vagas (desperdício de espaço), mas
a busca (get) e a inseção (put) serão extremamente rápidas.
HASHING
6
 chave 		valor
 0586	José Carlos
 0603	Alberto Santos
 0644	Ingrid Silva
 ...		 ...
 3675	Julio de Campos
 
HASHING
Exemplo 2:  Imagine uma lista ligada cujas chaves são nomes de pessoas. Suponha que a lista está em ordem alfabética.
Para acelerar as buscas, divida a lista em 26 pedaços: como uma lista telefônica
nomes começando com "A“
nomes começando com "B“ ......
7
chave 		valor associado
Antonio Carlos 	8533151 
Arthur Silva 		4210328 
Bruna Carvalho 	7532199 
... 			... 
Vitor Lima 		5535944 
Wellington Silva 	5159760 
Yan Fraga 		9537822 
HASHING
Para acelerar as buscas, divida a lista em 26 pedaços: como uma lista telefônica
nomes começando com "A“
nomes começando com "B“ ......
Assim temos:
um vetor de 26 posições é a tabela de hash
cada posição do vetor aponta para o começo de uma das listas.
8
chave 		valor associado
Antonio Carlos 	8533151 
Arthur Silva 		4210328 
Bruna Carvalho 	7532199 
... 			... 
Vitor Lima 		5535944 
Wellington Silva 	5159760 
Yan Fraga 		9537822 
HASHING
um vetor de 26 posições é a tabela de hash
cada posição do vetor aponta para o começo de uma das listas.
Comparamos com a busca binaria?
Comparamos com a busca sequencial?
9
Funções de hashing
Uma tabela de dispersão ou tabela de hash (hash table) é um vetor cada uma de cujas posições armazena zero, uma, ou mais chaves (e valores associados). 
10
Parâmetros importantes:
M :  número de posições na tabela de hash
N :  número de chaves da tabela de símbolos
    = N/M :  fator de carga (load factor)
Função de espalhamento
Função de hashing (hash function) transforma cada chave em um índice da tabela de hash.
Espalha as chaves utilizando alguma lógica de espalhamento / balanceamento.
Responde a pergunta: Em qual posição da tabela de hash devo colocar esta chave?. 
A função de hashing espalha as chaves pela tabela de hash.
11
Função de espalhamento
A função de hashing espalha as chaves pela tabela de hash.
A função de hashing associa um valor hash (hash value), entre 0 e M−1, a cada chave.
No exemplo dos CPFs temos 1 e a função de hashing é nome.charAt(0). Pois temos sobreposições de elementos.
Nesse caso a função de hashing produz uma colisão quando duas chaves diferentes têm o mesmo valor hash e portanto são levadas na mesma posição da tabela de hash:
12
Função de espalhamento
Exemplo: Chaves são números de identificação (7 dígitos) de estudantes da universidade  e  M vale 100:
Uma possível função de hashing: 2 primeiros dígitos da chave. Outra possibilidade: 2 dígitos do meio. Outra possibilidade: 2 últimos dígitos. Qual dessas espalha melhor as chaves pelo intervalo 0 . . 99?
13
8536152
7210629
8536339
8536002
...
8067490
8536106
8536169
8531845
Função de espalhamento
Outro exemplo: função de hashing que leva qualquer número de CPF brasileiro (que tem nove dígitos)
Correspondente dígito verificador (um número entre 0 e 99). 
Por exemplo, leva 111444777 em 35.) 
O dígito verificador de um CPF depende de todos os dígitos do CPF.
Ideal: a função de hashing deveria usar todos os dígitos da chave; assim, chaves ligeiramente diferentes serão levadas em números muito diferentes. 
podemos usar o valor hash como checksum para verificar a integridade de um dado!
14
Função de espalhamento
15
	Escolha M e a função de hashing de modo a
	diminuir o número de colisões;
 espalhar bem as chaves pelo intervalo 0 . . M−1.
Função de hashing modular
Que funções de hashing são usadas na prática?
Se as chaves são inteiros positivos, podemos usar a função modular
 resto da divisão por M:
Exemplos com M = 100 , M = 43 e M=18
Em hashing modular, é bom que M seja primo (Utilizado pela maioria das funções hash).
16
		Hash		
	Chave	M =100	M=43	M=18
	6613	13	34	7
	374	74	30	14
	9608	8	19	14
	5521	21	17	13
	1830	30	24	12
	8582	82	25	14
	8833	33	18	13
	3073	73	20	13
	7138	38	0	10
	5254	54	8	16
	3756	56	15	12
	101	1	15	11
	3066	66	13	6
	8816	16	1	14
	7941	41	29	3
	8838	38	23	0
	6686	86	21	8
	9767	67	6	11
	460	60	30	10
	588	88	29	12
	6958	58	35	10
	2723	23	14	5
Função de hashing modular
No caso de strings, podemos iterar hashing modular sobre os caracteres da string:
No lugar do multiplicador 43, poderia usar qualquer outro inteiro primo, mas suficientemente pequeno para que os cálculos não produzam sobrecarga do sistema.
17
int hashString(const char *s, int M) {
 int h = 0;
 for (int i = 0; s[i] != '\0'; i++) {
 h = (43 * h + s[i]) % M;
 }
 return h;
}
Hashing Ideal?
Hipótese do Hashing Uniforme:  Vamos supor que nossas funções de hashing distribuem as chaves pelo intervalo de inteiros 0 . . M−1 de maneira uniforme (todos os valores hash igualmente prováveis) e independente.
18
Hashing Ideal?
Exemplo: Supõe-se que os números sorteados pela Loteria Federal são todos igualmente prováveis. Supõe-se também que são independentes:  só porque “13” nunca foi sorteado, ele não tem maior probabilidade de sair no próximo sorteio.
Nenhuma função determinística satisfaz a Hipótese do Hashing Uniforme.  
(Essa impossibilidade é uma questão profunda e fundamental em Ciência da Computação.) 
Mas a hipótese é útil porque permite fazer cálculos para prever o desempenho aproximado de tabelas de hash.
19
Hashing Código
20
Hashing Código
21
Hashing Código
22
Referencias
FEOFILOFF. P. Hashing; Departamento de Ciência da Computação Instituto de Matemática e Estatística da USP
https://www.ime.usp.br/~pf/estruturas-de-dados/aulas/st-hash.html
Atualizado em 21-05-2018
23
image2.png
image3.png
image4.emf
ABCVWY8533151Antonio4210328Arthur Silva7532199Bruna Carvalho5535944Vitor Lima5159760Wellington Silva9537822 Yan FragaBUSCAVetor HashLista de Nomes com A
image1.jpeg
image5.png
image6.png
image7.png
image8.svg
 
.MsftOfcThm_Accent1_Fill {
 fill:#9ACD4C; 
}.MsftOfcThm_Accent1_Stroke {
 stroke:#9ACD4C; 
}
 
image9.png
image10.png
image11.png
image12.png
image13.png
image14.png