Buscar

Aula sobre Hashing (espalhamento)

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 5 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

� PAGE �2�
Hashing (ou espalhamento)
O que é Hashing?
Uma função de espalhamento (função hash) h(k) transforma uma chave k em um endereço. Este endereço é usado como a base para o armazenamento e recuperação de registros. É similar a uma indexação, pois associa a chave ao endereço relativo do registro. 
Diferenças:
no espalhamento os endereços parecem ser aleatórios - não existe conexão óbvia entre a chave e o endereço, apesar da chave ser utilizada no cálculo do endereço; 
no espalhamento duas chaves podem levar ao mesmo endereço (colisão) - portanto, colisões devem ser tratadas. 
Colisões
Exemplo:
Suponha que desejamos armazenar 75 registros em um arquivo, sendo que a chave para os registros é um campo sobrenome. Suponha que foi reservado espaço para manter 1.000 registros. Os registros podem ser "espalhados", por exemplo, através do seguinte procedimento: pega os dois primeiros caracteres do sobrenome e obtém suas representações ASCII (código numérico); multiplica estes números e usam os três dígitos menos significativos do resultado para servir de endereço. 
Exemplo:
nome: Maria da Silva
sobrenome: Silva
dois primeiros caracteres do sobrenome: Si
(S = 83) * (i = 105) = 8715
endereço: 715
Observe que os registros são colocados em posições aparentemente aleatórias, sem considerar a sua ordem alfabética. Entretanto, 2 sobrenomes diferentes podem produzir o mesmo endereço. Neste caso, ocorreu uma colisão (as chaves são sinônimas). 
Soluções:
Ideal: usar uma função de espalhamento perfeita, que não produz colisão. Mas isso é muito difícil (quase impossível) para mais de 500 chaves. A solução prática é tentar reduzir a um valor aceitável o número de colisões que podem ocorrer. 
Existem várias maneiras de reduzir o número de colisões:
Espalhamento dos registros. Busca por uma função, ou algoritmo, que distribua os registros relativamente por igual entre os endereços disponíveis (de forma razoavelmente aleatória). Problema no algoritmo do exemplo: chaves começando com Si são muito mais comuns do que chaves começando com Xz, por exemplo. 
Utilização de mais memória: é relativamente fácil achar um bom algoritmo quando se pode espalhar poucos registros em muitos endereços, em outras palavras, desperdiçar muito espaço (no exemplo: 75/1000=7,5%). 
Um Algoritmo Simples de Espalhamento
O objetivo é que a função "espalhe" as chaves da maneira mais uniforme possível entre os endereços disponíveis. 
O algoritmo tem 3 passos: 
representação da chave numericamente (caso a chave não seja numérica). Por exemplo, usa os códigos ASCII dos caracteres (todos) para formar um número. Por exemplo: 
 LOWELL$$$$$$ = 76 79 87 69 76 76 32 32 32 32 32 32 
subdivisão e soma (fold and add): subdivide o número em partes e soma as partes. No caso, subdivimos o número que descreve a chave em pares de códigos ASCII, que são tratados como valores inteiros, ao invés de caracteres:
 76 79 | 87 69 | 76 76 | 32 32 | 32 32 | 32 32 
Estes números inteiros podem ser somados, mas antes precisamos considerar o problema causado pela precisão limitada da máquina: em alguns sistemas, o maior inteiro permitido é 32.767 (15 bits), de maneira que se a soma resultar em um valor maior do que este podemos ter um overflow, ou um valor resultante negativo. Por exemplo, somando os primeiros 5 números o resultado é 30.588. Somando o último, 3.232, o resultado será maior que o máximo (33.820), causando um overflow. 
 
divisão do resultado da soma pelo espaço de endereçamento para obter o endereço final. O objetivo deste passo é reduzir o tamanho do número gerado no passo anterior de forma que ele fique no intervalo de posições endereçáveis do arquivo. Isto pode ser feito dividindo o resultado pelo número total de endereços disponíveis, e tomando o resto da divisão inteira, que será interpretado como o endereço base para o registro. Ou seja, se s é o resultado da soma, n é o número de endereços do arquivo, então a é o endereço, sendo que: 
			a = s MOD n 
O resto da divisão é um número entre 0 e n-1. 
Distribuição de registros entre endereços
A função de espalhamento perfeita (ou uniforme) para um dado conjunto de chaves seria uma que não produzisse nenhum sinônimo em um dado espaço de endereçamento. 
A pior função seria aquela que, qualquer que fosse a chave, geraria sempre o mesmo endereço (todas as chaves seriam sinônimas). 
Uma função aceitável é uma que gera poucos sinônimos - em geral, isto é mais provável de ocorrer se usarmos uma função que distribui as chaves aleatoriamente no conjunto de endereços disponíveis. 
Agora, como resolver o problema das colisões? 
1) Espalhamento Duplo
Uma segunda função de espalhamento é aplicada novamente toda vez que uma colisão ocorrer. O processo é repetido até uma posição livre ser encontrada (para inserção ou busca). 
Vantagem: tende a espalhar melhor as chaves pelos endereços.
Desvantagem: os endereços podem estar muito distantes um do outro (o princípio da localidade é violado), provocando seekings adicionais. 
2) Encadeamento com uma Área de Overflow Separada
Outra opção é alocar todos os sinônimos numa área especial de overflow (no final do arquivo, por exemplo).
Nesses casos, os endereços sem chaves na área primária nunca serão ocupados. 
Vantagens:
Resolve o problema de manutenção. 
Se a área primária é alocada de forma que o tamanho seja suficientemente grande para permitir poucos overflows, área de overflow pode ser uma simples seqüência de chaves. 
Desvantagem: overflow sempre requer outro acesso. 
3) Scatter Tables: Indexing Revisited
Quando, ao invés do registro todo, o arquivo na realidade guarda apenas as chaves e sua posição nos arquivos de dados, o hashing gera, na realidade, um índice, e o arquivo relacionado é chamado scatter table.
Tabelas de Espalhamento
Pode ser representada por um vetor onde cada posição, denominada encaixe, mantém uma classe de partição. O número de encaixes na tabela deve coincidir com o número de classes criadas pela função de espalhamento. Considerando que um conjunto P seja espalhado em P1, P2, P3, ..., Pn classes distintas, um vetor T[1..n] pode representar o espalhamento de maneira satisfatória, bastando associar a cada elemento T[i] uma classe Pi, 1
 i 
 n correspondente. Admitindo a existência de elementos sinônimos em P, é de se esperar que durante o espalhamento ocorra pelo menos uma colisão, ou seja, é possível que tenhamos que armazenar um elemento numa posição da tabela que já encontre ocupada por um outro valor. Uma forma de resolver este problema é chamada de espalhamento externo. No espalhamento externo, a tabela de hashing será um vetor cujos elementos são ponteiros para listas encadeadas que representam as classes do espalhamento.
O método da Divisão Inteira
A função a seguir, transforma as chaves em endereços relativos (para uma tabela contendo N=5 encaixes):
function hash(chave: integer):integer;
begin
 hash:= (chave mod N) + 1;
end;
A seguir, os valores de hashing gerados pela função:
hash(54) = (54 mod 5) + 1 = 5
hash(21) = (21 mod 5) + 1 = 2
Transformação de chaves alfanuméricas
Uma forma simples de se transformar uma chave alfanumérica num valor numérico consiste em considerar cada caractere da chave com um valor inteiro (correspondente ao seu código ASCII) e realizar uma soma com todos eles:
function hash_alfa(chave:string):integer;
var i,soma:integer;
begin
 soma:=0;
 for i:=1 to length(chave) do
 soma:= soma + ord(chave[i]);
 hash_alfa:= (soma mod N) + 1;
end;
Exemplos (considerando N=7 encaixes):
hash_alfa(‘Thais’) = 2
hash_alfa(‘Bia’) = 3
Aplicação com arquivo
						Área de Dados (primária)
	
	
	NÚMERO
	NOME
	SALÁRIO
	STATUS
	ELO
	
	0
	1950
	Enio
	$ 900
	T
	16
	Função HASH
	1
	1600
	Eber
	$ 800
	F
	0Endereço = F(chave)
	2
	
	
	
	
	0
	
	3
	
	
	
	
	0
	
	4
	3150
	Rui
	$ 550
	T
	0
	No exemplo,
	5
	2150
	Flavio
	$ 420
	F
	0
	F(chave)=Numero mod 13
	6
	1450
	Diogo
	$ 1200
	T
	0
	
	7
	
	
	
	
	0
	
	8
	1100
	Antonio
	$ 750
	T
	0
	
	9
	1400
	Claudio
	$ 600
	T
	0
	
	10
	1050
	Afonso
	$ 3200
	T
	17
	
	11
	
	
	
	
	0
	
	12
	1000
	Ademar
	$ 1200
	T
	14
						Área de Overflow
	
	
	NÚMERO
	NOME
	SALÁRIO
	STATUS
	ELO
	
	13
	1700
	Edson
	$ 500
	T
	0
	
	14
	2300
	Gerson
	$ 800
	T
	0
	
	15
	3000
	Ivan
	$ 630
	T
	13
	
	16
	2600
	Luis
	$ 5000
	T
	0
	
	17
	2766
	Pedro
	$ 3000
	T
	15
COLISÃO utilizando tratamento por encadeamento (utilização da área de extensão (overflow)): Os registros que colidem em um mesmo endereço são armazenados em uma área de extensão (overflow) e inseridos na lista encadeada correspondente na área principal (atualização do campo ELO). 
INSERÇÃO: é feita através da posição determinada para o armazenamento, através da função HASH.
REMOÇÃO: em geral é lógica.
Opções a serem construídas:
Insere
Altera
Consulta
Exclui
Reorganiza (exclui todos os registros marcados com status false)
Relatório (Exibe todos os registros, inclusive o número do registro no arquivo e o campo elo).
_1157950707.unknown
_1157950727.unknown

Outros materiais