Tabelas Hash
Prof. Frederico Brito Fernandes
[email protected]
CONTEÚDO
(1) Auto-avaliação
(2) Tabelas Hash
(3) Tipos de funções hash
(4) Colisão
(5) Algoritmo de Cichelli
(6) Conclusões
(1) Auto-avaliação
Ordenação/Classificação
• Antes de prosseguir:
– Considerando o vetor de inteiros a seguir, execute os algoritmos vistos
na aula passada (quickSort e mergeSort), e escreva as alterações
realizadas nesse vetor, em cada iteração realizada
vetor
iteração
4
8
3
2
1
7
1ª
2ª
3ª
4ª
5ª
6ª
...
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
2
(2) Hash
Tabelas de dispersão/espalhamento (Hash Tables)
• Motivação:
– Desejamos armazenar os dados referentes aos clientes de uma loja.
– Cada cliente é individualmente identificado pelo seu nº de CPF (o CPF
é a chave de busca).
– Podemos então usar o nº de CPF como chave de busca de um cliente
cadastrado no sistema.
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
3
(2) Hash
Exemplo de aplicação
Estrutura, Pesquisa e Ordenação de Dados
0
1
2
3
4

97
98
99

02561200001
98110100002
Maria
45122900004
João
20075199998
Ana
José

…
• Projetamos a tabela hash para
que ela armazene entrada na
forma (CPF, Nome), onde o
CPF é um inteiro de 11
dígitos positivos
• Nossa tabela hash usa um
array de tamanho N = 100 e a
função hash é h(k) = os
últimos dois dígitos de k,
onde k é chave de busca, i.e.,
o CPF
• Como seria o cálculo
realizado pela função hash?
Frederico Brito Fernandes

4
(2) Hash
Exemplo de aplicação
Estrutura, Pesquisa e Ordenação de Dados
0
1
2
3
4

97
98
99

02561200001
98110100002
Maria
45122900004
João
20075199998
Ana
José

…
• Uma função hash h mapeia
chaves de um dado tipo para
inteiros em um intervalo fixo
de [0, N - 1], onde N é o
tamanho da tabela
• Exemplo:
h(k) = k mod N é a
função hash para chaves
inteiras
• O inteiro retornado pela
função h(k) é chamado de
valor hash da chave k
Frederico Brito Fernandes

5
(2) Hash
Definições
• Uma tabela hash para
uma chave de um dado
tipo consiste de
– Uma função hash h
– Um Array (chamado de tabela)
de tamanho N
Estrutura, Pesquisa e Ordenação de Dados
• O objetivo é armazenar
um
registro/objeto/estrutura
que possua chave de
busca k na posição i =
h(k) do array
• E dispersar as chaves na
tabela de forma
aparentemente aleatória
Frederico Brito Fernandes
6
(2) Hash
Definições
• Não é apenas um método de pesquisa, mas
também um método de organização física de
tabelas;
• o armazenamento de cada entrada da tabela é
associado a um endereço calculado pela
aplicação de uma função a chave de entrada;
• a eficiência da pesquisa neste tipo de
organização depende fundamentalmente da
função de cálculo de endereço;
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
7
(3) Tipos de funções hash
Divisão
• Divisão – a função de hashing deve garantir que o nº por
ela retornado seja um índice válido para uma entrada da
tabela
• H(c) = C mod 5
– Exemplo com 100 chaves para 5 entradas
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
8
(3) Tipos de funções hash
Enlaçamento
• Enlaçamento – a chave é dividida em diversas partes.
As partes são combinadas ( somadas por exemplo) para
gerar o endereço alvo
• Ex.: CPF= 123.456.789.22
– H(cpf) = 12+34+56+78+92+2 = 274 (total de endereços = 5 x
99 = 495 + 9 = 504
– H(cpf) = 123+456+789+22 = 1390
H(cpf) = cpf mod 1000
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
9
(3) Tipos de funções hash
Meio Quadrado
• Função meio-quadrado – a chave é elevada ao quadrado
e parte dela é usada como endereço (os bits do centro)
• H(16) = 0000 0001 0000 0000 = 256
0001 0000 = 16
• H(12) = 0000 0000 0110 0100 = 100
0000 1100 = 6
• 1.024 entradas – 10 bits
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
10
(3) Tipos de funções hash
Extração
• Extração – apenas uma parte da chave é usada para
gerar o endereço
• Ex.: matrícula: 2010110256
período
área
ano
– H(mat) = 0256
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
11
(4) Colisão
Nem tudo é perfeito...
• Voltando ao exemplo da motivação inicial, o problema
que surge é que provavelmente existirão dois ou mais
clientes da loja que apresentarão os últimos dois dígitos
no nº de CPF iguais.
• Dizemos que há uma colisão, pois
registros/objetos/estruturas diferentes são mapeados para a
mesma posição na tabela.
• Vale salientar que não há como eliminar completamente a
ocorrência de colisões em tabelas hash.
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
12
(4) Colisão
Tratamento de colisão
• Devemos minimizar as colisões e usar um método que,
mesmo com colisões, saibamos identificar cada elemento
da tabela individualmente.
• Vale lembrar que uma tabela de dispersão nunca terá todos
os elementos preenchidos
• Uma ocupação acima de 75% eleva o número de colisões,
descaracterizando a idéia central desta estrutura de dados
• Portanto, podemos garantir que sempre existirá uma
posição livre na tabela
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
13
(4) Colisão
Tratamento de colisão
• Encadeamento Separado: cada célula na tabela aponta
para uma lista encadeada de registros/objetos/estruturas
• Encadeamento Separado é simples, mas requer memória
adicional fora da tabela
0
1
2
3
4
Estrutura, Pesquisa e Ordenação de Dados
02561200001
Ana
45122900004
20075199904
Zé
Frederico Brito Fernandes
Bia
14
(4) Colisão
Tratamento de colisão
• Sondagem Linear: cada célula na tabela possui um
ponteiro para o registro/objeto/estrutura que representa a
informação armazenada na tabela de dispersão
• Procuramos o próximo índice livre da tabela (usando
incremento circular) para armazenar o novo elemento.
• Os índices da tabela que não têm elementos associados
são preenchidos com o valor NULL.
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
15
(4) Colisão
Sondagem Linear
• O item que está colidindo é
colocado em uma célula
diferente da tabela
• A sondagem linear lida com
colisões colocando o item que
colidiu na próxima célula
disponível (circularmente)
• Exemplo:
– N = 13
– H(k) = k mod N
– Insira as chaves 18, 41, 22, 44,
59, 32, 31, 73, nesta ordem
– Na colisão,
h’(k)=(h(k) +1) mod N
0 1 2 3 4 5 6 7 8 9 10 11 12
41
18 44 59 32 22 31 73
0 1 2 3 4 5 6 7 8 9 10 11 12
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
16
(4) Colisão
Busca com Sondagem Linear
• get(k)
– Sondamos posições
consecutivas até que
• Um item com chave k é
encontrado, ou
• Uma célula vazia é
encontrada, ou
• N células foram sondadas sem
sucesso
– Cada índice da tabela que tem
um elemento associados é
preenchido com o endereço do
nó que contém o elemento
Estrutura, Pesquisa e Ordenação de Dados
Algorithm get(k)
i  k mod N
p0
do
c  A[i]
if c = 
return null
else if c->key = k
return c->element
else
i  (i + 1) mod N
pp+1
while p != N
return null
Frederico Brito Fernandes
17
(4) Colisão
Atualizações com Sondagem Linear
• Inserções ou atualizações
• put(k, object/struct/record)
• Para lidar com deleções, nós
usamos ponteiros para null
• remove(k)
– Buscamos um item com chave k
– Se este item for encontrado,
substitua o ponteiro para o nó que
continha o item por null e retorne o
item
– Caso contrário, retorne null
– Iniciamos na célula
i = k mod N
– Sondamos células consecutivas
até que
• Uma célula i encontrada
esteja vazia (null)
• Amazenamos o item
(object/struct/record) na
célula
• Retorne true
– Se N células foram
sondadas sem sucesso
então retorne false
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
18
(5) Cichelli
Função hash perfeita
• Desenvolvido por Richard J. Cichelli para criação de
funções hash perfeitas considerando um pequeno
número de palavras:
h(palavra) = ( comprimento(palavra) + g(primeiraLetra(palavra)) +
g(ultimaLetra(palavra)) ) mod N
onde: a função g() deverá ser encontrada de forma exaustiva
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
19
(5) Cichelli
Função hash perfeita
O algoritmo possui 3 etapas:
1.
Frequência:
•
Cálculo de ocorrências da primeira e última letra;
2. Ordenação:
•
3.
As palavras são ordenadas de forma decrescente;
Busca:
•
•
•
•
Tentativa de encontrar a função g() por meio de tentativas,
colocando-se o valor de 0..MAX para cada letra;
Os valores mapeados de h() são armazenados;
Se para 0..MAX a colisão persiste, o algoritmo retrocede para a
palavra anterior;
Nem sempre a busca vai ser realizada com sucesso, ou seja, o
algoritmo não garante que não haja colisões;
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
20
(5) Cichelli
Função hash perfeita
Ex: N=9, MAX=4
Calliope, Clio, Erato, Euterpe, Melpomene, Polyhymnia,
Terpsichore, Thalia e Urânia
1 Frequência:
Estrutura, Pesquisa e Ordenação de Dados
LETRA
Nº de OCORRÊNCIAS
A
3
C
2
E
6
M
1
O
2
P
1
T
2
U
1
Frederico Brito Fernandes
21
(5) Cichelli
Função hash perfeita
Ex: N=9, MAX=4
Calliope, Clio, Erato, Euterpe, Melpomene, Polyhymnia,
Terpsichore, Thalia e Urânia
2 Ordenação:
Estrutura, Pesquisa e Ordenação de Dados
PALAVRA
Primeira + Última
DECRESCENTE
Calliope
2+6=8
Euterpe
Clio
2+2=4
Calliope
Erato
6+2=8
Erato
Euterpe
6+6=12
Terpsichore
Melpomene
1+6=7
Melpomene
Polyhymnia
1+3=4
Thalia
Terpsichore
2+6=8
Clio
Thalia
2+3=5
Polyhymnia
Urânia
1+3=4
Urânia
Frederico Brito Fernandes
22
(5) Cichelli
Função hash perfeita
3
Busca:
PALAVRA
g()
h()
h() reservados
Euterpe
E=0
7
[7]
Calliope
C=0
8
[7, 8]
Erato
O=0
5
[5, 7, 8]
Terpsichore
T=0
2
[2, 5, 7, 8]
Melpomene
M=0
0
[0, 2, 5, 7, 8]
Thalia
A=0
6
[0, 2, 5, 6, 7, 8]
4
[0, 2, 4, 5, 6, 7, 8]
[0, 1, 2, 4, 5, 6, 7, 8]
Clio
Polyhymnia
P=0
1
Urânia
U=0
6 (*)
COLISÃO:
(1) Tentar U de 1..4;
(2) Permanecendo, retroceder
para palavra anterior
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
23
(5) Cichelli
Função hash perfeita
3
Busca:
PALAVRA
g()
h()
h() reservados
Polyhymnia
P=0
1
[0, 1, 2, 4, 5, 6, 7, 8]
Urânia
U=0
6 (*)
U=1
7 (*)
U=2
8 (*)
U=3
0 (*)
U=4
1 (*)
P=1
2 (*)
P=2
3
U=0
6 (*)
U=1
7 (*)
U=2
8 (*)
U=3
0 (*)
U=4
1
continuação
Polyhymnia
Urânia
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
[0, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
24
(6) Conclusões
Eficiência da busca
• O pior caso ocorre quando
todas as chaves inseridas
colidirem
• Neste caso, buscas, inserções
e remoções tem tempo
execução O(n)
Estrutura, Pesquisa e Ordenação de Dados
• Buscas, inserções e remoções
em uma tabela hash bem
projetada tem tempo de
execução constante, i.e., O(1)
• Aplicações práticas:
– Bancos de dados pequenos
– compiladores
– Caches de browser
(navegadores)
Frederico Brito Fernandes
25