Prof. Frederico Brito Fernandes [email protected] Tabelas Hash CONTEÚDO (1) Auto-avaliação (2) Tabelas Hash (3) Tipos de funções hash (4) Colisão (5)

Prof. Frederico Brito [email protected]

Tabelas HashTabelas HashTabelas HashTabelas Hash

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

Frederico Brito FernandesFrederico Brito Fernandes 2Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados

Ordenação/ClassificaçãoOrdenaçã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

(1) Auto-avaliação

vetor

iteração 4 8 3 2 1 7

1ª

2ª

3ª

4ª

5ª

6ª

...


Tabelas de dispersão/espalhamento (Hash Tables)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.

(2) Hash


Exemplo de aplicaçãoExemplo de aplicação

• 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?

01234

979899

…

45122900004

98110100002

20075199998

02561200001 Maria

José

João

Ana

(2) Hash


Exemplo de aplicaçãoExemplo de aplicação

• 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

01234

979899

…

45122900004

98110100002

20075199998

02561200001 Maria

José

João

Ana

(2) Hash


DefiniçõesDefiniçõ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

• 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

(2) Hash


• 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;

(2) Hash

DefiniçõesDefinições


DivisãoDivisã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

(3) Tipos de funções hash


• 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

EnlaçamentoEnlaçamento



• 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

Meio QuadradoMeio Quadrado



• Extração – apenas uma parte da chave é usada para gerar o endereço

• Ex.: matrícula: 2010110256

período

área

ano– H(mat) = 0256

ExtraçãoExtração



Nem tudo é perfeito...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.

(4) Colisão


Tratamento de colisãoTratamento 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

(4) 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

01234 45122900004 20075199904

02561200001

Ana

Zé Bia

(4) 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.

(4) Colisão


Sondagem LinearSondagem 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 18445932223173 0 1 2 3 4 5 6 7 8 9 10 11 12

(4) Colisão


Busca com Sondagem LinearBusca 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

Algorithm get(k)i k mod Np 0do

c A[i]if c

return null else if c->key k

return c->elementelse

i (i 1) mod Np p 1

while p ! Nreturn null

(4) Colisão


Atualizações com Sondagem LinearAtualizações com Sondagem Linear

• 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

• Inserções ou atualizações

• put(k, object/struct/record)– 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

(4) Colisão


Função hash perfeitaFunçã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

(5) Cichelli



O algoritmo possui 3 etapas:1. Frequência:

• Cálculo de ocorrências da primeira e última letra;

2. Ordenação:• As palavras são ordenadas de forma decrescente;

3. 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;

(5) Cichelli



Ex: N=9, MAX=4

Calliope, Clio, Erato, Euterpe, Melpomene, Polyhymnia, Terpsichore, Thalia e Urânia

Frequência:

(5) Cichelli

11 LETRA Nº de OCORRÊNCIAS

A 3

C 2

E 6

M 1

O 2

P 1

T 2

U 1



Ex: N=9, MAX=4

Calliope, Clio, Erato, Euterpe, Melpomene, Polyhymnia, Terpsichore, Thalia e Urânia

Ordenação: PALAVRA Primeira + Última

Calliope 2+6=8

Clio 2+2=4

Erato 6+2=8

Euterpe 6+6=12

Melpomene 1+6=7

Polyhymnia 1+3=4

Terpsichore 2+6=8

Thalia 2+3=5

Urânia 1+3=4

(5) Cichelli

22 DECRESCENTE

Euterpe

Calliope

Erato

Terpsichore

Melpomene

Thalia

Clio

Polyhymnia

Urânia



Busca:

(5) Cichelli

33 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]

Clio 4 [0, 2, 4, 5, 6, 7, 8]

Polyhymnia P=0 1 [0, 1, 2, 4, 5, 6, 7, 8]

Urânia U=0 6 (*)

COLISÃO:COLISÃO:

(1)(1) Tentar U de 1..4;Tentar U de 1..4;

(2)(2) Permanecendo, retroceder Permanecendo, retroceder para palavra anteriorpara palavra anterior



Busca:

(5) Cichelli

33 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 (*)

Polyhymnia P=1 2 (*)

P=2 3 [0, 2, 3, 4, 5, 6, 7, 8]

Urânia U=0 6 (*)

U=1 7 (*)

U=2 8 (*)

U=3 0 (*)

U=4 1 [0, 1, 2, 3, 4, 5, 6, 7, 8]

continuação


Eficiência da buscaEficiê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)

• 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)

(6) Conclusões

Documents

Prof. Frederico Brito Fernandes [email protected] Tabelas Hash CONTEÚDO (1) Auto-avaliação (2) Tabelas Hash (3) Tipos de funções hash (4) Colisão (5)