TABELAS DE DISPERSÃO/HASH - UBIcbarrico/Disciplinas/.../Teorica_TabelasHashing.pdf · Tabela de Hash 8/47 Tabela de Hash Definição-É um tipo de estruturação criado para o armazenamento

1/47

TABELAS DE

DISPERSÃO/HASH

Tabelas de Dispersão/Hash Programação II

Introdução 2/47

Introdução

Motivação

- Considerar o problema de pesquisar um determinado valor num vetor:

- Se o vetor não está ordenado, a pesquisa requer O(n) de complexidade.

- Se o vetor está ordenado, pode-se fazer a pesquisa binária que requer uma

complexidade de O(log n).

- Parece não haver melhor maneira de resolver o problema com custos melhorados.

Ideia

- Poderia haver maneira de resolver o problema em O(1), se o vetor estiver

organizado de uma determinada forma.


Introdução 3/47

Solução

- Arranjar uma função mágica que, dado um determinado valor a pesquisar, nos

diga exatamente a posição exata no vetor.

- Esta função é chamada função de dispersão (hash).

Exemplo

- Uma máquina produz por dia entre 0 e 5 peças de um determinado produto.

- Registar o número de peças produzidas ao longo de 1 ano.

- Pretende-se saber, por exemplo, em quantos dias se produziu k peças daquele

produto, com k = 0, …, 5.


Introdução 4/47

Exemplo – Solução 1

- Definir um vetor com índices de 0 a 365 e guardar no índice k-1 o número de

peças produzidas no dia k

0 1 2 3 4 5 6 7 362 363 364 365

0 4 3 5 2 0 0 5 . . . 0 0 2 0

- Determinar o número de dias em que se produziu p peças:

- implica percorrer todo o vetor e pesquisar o valor p naquele vetor, no sentido de

contar o número de vezes que aparece o valor p.

- Ordem de complexidade:

- O(n), n = tamanho do vetor


Introdução 5/47

Exemplo – Solução 2

- Definir um vetor V com índices de 0 a 5 e guardar no índice k o número de

dias que produziu-se k peças, com k = 0, …, 5.

Ou seja, se num dado dia produziu-se p peças, então o valor V[p] é

incrementado em 1 valor: V[p] = V[p] + 1

0 1 2 3 4 5

110 17 28 56 73 81

- Para determinar o número de dias em que se produziu p peças:

- basta pegar no valor contido no índice p do vetor V, V[p], que contém o número de

vezes/dias que foram produzidas p peças.

- Ordem de complexidade:

- O(1)


Introdução 6/47

Complexidade ideal – O(1)

- Vetor Ai com i = 1, ..., 65.535 (16 bits) inicializado a zeros

- Cada inserção de um número k seria: Ak = Ak + 1

- Cada remoção de um número k seria: Ak = Ak - 1

- Ak representa o número de vezes que o número k foi inserido

- Para procurar temos que fazer pesquisar(k):

se Ak > 0 então está encontrado.


Introdução 7/47

Problemas encontrados

- Tamanho do vetor

- com inteiros de 16 bits é um vetor com 65.535,

- com inteiros de 32 bits é um vetor com 4.294.967.296, o que é incomportável.

- O uso de strings

- Se tivermos strings em vez de inteiros não é possível indexar num vetor,

porque A'Ana' não existe.

Resolução do problema dos vetores grandes

- Usar uma função que mapeie grandes números ou strings transformados em

números mais pequenos ou manejáveis

- Esta função é chamada de Hash ou dispersão


Tabela de Hash 8/47

Tabela de Hash

Definição

- É um tipo de estruturação criado para o armazenamento de informação, sendo

- uma forma extremamente simples,

- fácil de se implementar e,

- intuitiva para se organizar grandes quantidades de dados.

Possui como ideia central

- a divisão do universo dos dados a ser organizado em subconjuntos mais fáceis

de serem manipulados.

A estruturação da informação em tabelas de hash visa

- permitir armazenar de grande quantidade de dados, e

- pesquisar rapidamente em grande quantidade de dados.


Tabela de Hash 9/47

As tabelas de hash são constituídas por 2 conceitos fundamentais

- Tabela de hash:

- estrutura que permite o acesso aos subconjuntos.

- Função de hash:

- função que realiza um mapeamento entre

- os valores das chaves (dados a organizar) e

- as entradas (posições) na tabela.


Propriedades da Tabela de Hash 10/47

Propriedades da Tabela de Hash

Criar um critério simples para

- Dividir o universo dos dados a organizar em subconjuntos com base em

alguma qualidade (critério) do domínio das chaves:

- possuir um índice que permita encontrar o início do subconjunto certo, depois de

calcular o valor de hash - isto é a Tabela de hash.

Saber em qual subconjunto procurar e colocar uma chave

- Indicar quantos subconjuntos se pretende;

- Criar uma regra de cálculo que, dada uma chave, determine em que

subconjunto se deve

- procurar pelos dados com esta chave, ou

- inserir este dado (caso seja um novo elemento).

- Isto é chamado de Função de hash.


Propriedades da Tabela de Hash 11/47

Gerir estes subconjuntos bem menores com um método simples

- Possuir uma estrutura ou um conjunto de estruturas de dados para os

subconjuntos.

- Existem duas filosofias:

- hashing fechado (ou de endereçamento aberto), ou

- hashing aberto (ou encadeado).

Alguns problemas que se colocam quando se usa tabelas de hash

- determinar uma função de hash que minimize o número de colisões;

- obter os mecanismos eficientes para tratar as colisões.


Função de Hash 12/47

Função de Hash

Objetivos da função de Hash

- ser eficiente

- distribuir todos os elementos de forma uniforme pelas posições da tabela

Exemplo

- Números inteiros x (chave) de 0 a 99 (dois dígitos)

- tam = 10 (tamanho da tabela)

- Pode-se construir uma função que coloque x no vetor em termos do algarismo das

dezenas (tam = 10):

- função matemática: h(x) = x / tam (/ = divisão inteira)

- Pode-se também construir uma função que coloque x no vetor em termos do

algarismo das unidades (tam = 10):

- função matemática: h(x) = x % tam (% = resto da divisão inteira)


Função de Hash 13/47

Colisões

- Quando a Função de hash é imperfeita poderão existir dois valores a serem

colocados na mesma posição do vetor - isto chama-se uma colisão.

- As colisões são normalmente tratadas como quem chega primeiro serve-se:

- o primeiro elemento a chegar a uma posição fica com ela.

- Terá de se arranjar uma solução eficiente para determinar o que se fazer com o

segundo valor que deveria ser colocado na mesma posição.

- O que fazer quando dois valores diferentes tentam ocupar a mesma posição?

- Hashing fechado ou endereçamento aberto:

- procura a partir dessa posição uma posição vazia.

- usar uma segunda função de hash, uma terceira, ...

- Hashing aberto ou encadeamento separado:

- usa a posição do vetor como cabeça de uma lista que vai conter todas as colisões

dessa posição.


Tabela de Hash 14/47

Tabela de Hash

Fator de ocupação l

- Definição:

λ = n / tam, em que

- n = número de elementos inseridos na tabela.

- tam = tamanho da tabela.

- Observação:

λ deve ser inferior a 1.


Hashing fechado 15/47

Hashing fechado

Exemplo 1

- Função de Hash: hash(x) = x % 100

- Pretende-se adicionar 196 à tabela de Hash.

Tabela de Hash

0

1

2

.

.

.

.

.

.

95

96 496

97 397

98

99 299



Exemplo 1 (cont.)



- hash(196) = (196 % 100) = 96

- Tabela(96) está ocupada

- Tabela(96) = 496 ≠ 196

Tabela de Hash

0

1

2

.

.

.

.

.

.

95

96 496

97 397

98

99 299



Exemplo 1 (cont.)



- hash(196) = (196 % 100) = 96


- Tabela(96) = 496 ≠ 196

- Tabela(96+1) está ocupada

- Tabela(97) = 397 ≠ 196

Tabela de Hash

0

1

2

.

.

.

.

.

.

95

96 496

97 397

98

99 299



Exemplo 1 (cont.)



- hash(196) = (196 % 100) = 96


- Tabela(96) = 496 ≠ 196


- Tabela(97) = 397 ≠ 196

- Tabela(96+2) está vazia

- Então, colocar 196 na posição 98:

Tabela(98) = 196.

Tabela de Hash

0

1

2

.

.

.

.

.

.

95

96 496

97 397

98 196

99 299



Exemplo 1 (cont.)



- hash(196) = (196 % 100) = 96


- Tabela(96) = 496 ≠ 196


- Tabela(97) = 397 ≠ 196


- Então, colocar 196 na posição 98:

Tabela(98) = 196.

- Foi utilizada a sondagem linear.

Tabela de Hash

0

1

2

.

.

.

.

.

.

95

96 496

97 397

98 196

99 299



Exemplo 2



Tabela de Hash

0

1

2

.

.

.

.

.

.

95

96 496

97 397

98 196

99 299



Exemplo 2 (cont.)



- hash(397) = (397 % 100) = 97


- Tabela(97) = 397 = 397

- Então, não inserir 397 na tabela, pois já existe.

Tabela de Hash

0

1

2

.

.

.

.

.

.

95

96 496

97 397

98 196

99 299



Exemplo 3



Tabela de Hash

0

1

2

.

.

.

.

.

.

95

96 496

97 397

98 196

99 299



Exemplo 3 (cont.)



- hash(598) = (598 % 100) = 98


- Tabela(98) = 196 ≠ 598

Tabela de Hash

0

1

2

.

.

.

.

.

.

95

96 496

97 397

98 196

99 299



Exemplo 3 (cont.)



- hash(598) = (598 % 100) = 98


- Tabela(98) = 196 ≠ 596


- Tabela(99) = 299 ≠ 596

- A posição 99 é a última posição e está ocupada.

Tabela de Hash

0

1

2

.

.

.

.

.

.

95

96 496

97 397

98 196

99 299



Exemplo 3 (cont.)



- hash(598) = (598 % 100) = 98


- Tabela(98) = 196 ≠ 596


- Tabela(99) = 299 ≠ 596

- A posição 99 é a última posição e está ocupada.

- Solução:

- Tratar a tabela como circular:

a posição seguinte da 99 é a posição 0.

- Assim, 598 vai para a posição 0:

Tabela(0) = 598.

Tabela de Hash

0 598

1

2

.

.

.

.

.

.

95

96 496

97 397

98 196

99 299



Problemas da sondagem linear

- Existência de blocos contíguos de posições ocupadas com grandes dimensões

(em geral quando λ > 0.5) — Clusters.

- Quanto maiores ficam os blocos, mais tendência têm para crescer.

- A sondagem é igual para elementos que colidem.



Exemplo 1



Tabela de Hash

0

.

.

.

.

.

.

93 593

94 793

95

96 496

97

98 196

99



Exemplo 1 (cont.)



- hash(293) = (293 % 100) = 93

- Tabela(93) = 593 ≠ 293

Tabela de Hash

0

.

.

.

.

.

.

93 593

94 793

95

96 496

97

98 196

99



Exemplo 1 (cont.)



- hash(299) = (293 % 100) = 93

- Tabela(93) = 593 ≠ 293


- Tabela(94) = 793 ≠ 293

Tabela de Hash

0

.

.

.

.

.

.

93 593

94 793

95

96 496

97

98 196

99



Exemplo 1 (cont.)



- hash(299) = (293 % 100) = 93

- Tabela(93) = 593 ≠ 293


- Tabela(94) = 793 ≠ 293


- Então colocar 293 na posição 97:

Tabela(97) = 293

Tabela de Hash

0

.

.

.

.

.

.

93 593

94 793

95

96 496

97 293

98 196

99



Exemplo 1 (cont.)



- hash(299) = (293 % 100) = 93

- Tabela(93) = 593 ≠ 293


- Tabela(94) = 793 ≠ 293


- Então colocar 293 na posição 97:

Tabela(97) = 293

- Foi utilizada a sondagem quadrática.

Tabela de Hash

0

.

.

.

.

.

.

93 593

94 793

95

96 496

97 293

98 196

99



Problemas da sondagem quadrática

- Cada sondagem tenta uma nova posição.

- Se o tamanho da tabela for, por exemplo, 16 (tam = 16),

então atinge-se sempre as posições 1, 2, 4 e 9;

- entra-se num ciclo infinito.

Resolução do problema

- tam tem de ser número primo

- é conveniente o fator λ ser menor ou igual a 0.5 (λ = n / dim ≤ 0.5)

- ao atingir-se λ = 0.5

- pode-se aumentar a tabela para um número primo superior e, de seguida

- passar os valores da tabela atual para a nova aplicando de novo a função de hash.

- A este método dá-se o nome de rehash



Pesquisa


- Construção da tabela usando a sondagem linear:

- hash(12) = 12 % 10 = 2

- hash(23) = 23 % 10 = 3

- hash(39) = 39 % 10 = 9

- hash(10) = 10 % 10 = 0

- hash(16) = 16 % 10 = 6

- hash(32) = 32 % 10 = 2 (colisão com 12)

- Tabela(2) = 12 ≠ 32

- Tabela(2+1) = 23 ≠ 32


Colocar 32 na posição 4: Tabela(4) = 32

Tabela de Hash

0 10

1

2 12

3 23

4 32

5

6 16

7

8

9 39



Pesquisa (cont.)


- Pesquisar o elemento 32:

- hash(32) = 32 % 10 = 2

- Tabela(2) = 12 ≠ 32 (continuar pesquisa)

- Tabela(2+1) = 23 ≠ 32 (continuar pesquisa)

- Tabela(2+2) = 32 = 32 (terminar pesquisa)

O elemento 32 está na tabela

Tabela de Hash

0 10

1

2 12

3 23

4 32

5

6 16

7

8

9 39



Pesquisa (cont.)



- hash(22) = 12 % 10 = 2

- Tabela(2) = 12 ≠ 22 (continuar pesquisa)



- Tabela(2+3) = vazia (terminar pesquisa)

O elemento 22 não está na tabela

Tabela de Hash

0 10

1

2 12

3 23

4 32

5

6 16

7

8

9 39



Problema da remoção (cont.)


- Remover o elemento 12:

- hash(12) = 12 % 10 = 2

- Tabela(2) = 12 = 12

Tabela de Hash

0 10

1

2 12

3 23

4 32

5

6 16

7

8

9 39





- Remover o elemento 12:

- hash(12) = 12 % 10 = 2

- Tabela(2) = 12 = 12

- A posição 2 fica vazia:

Tabela(2) = vazia

Tabela de Hash

0 10

1

2

3 23

4 32

5

6 16

7

8

9 39






- hash(32) = 32 % 10 = 2

- A posição 2 está vazia: Tabela(2) = nada

- Conclusão: 32 não está na Tabela.

- Conclusão errada:

- o elemento 32 está na posição 4: Tabela(4) = 32

Tabela de Hash

0 10

1

2

3 23

4 32

5

6 16

7

8

9 39



Resolução do problema da remoção

- Criar uma estrutura que assinale cada posição:

- Livre (vazia e nunca ocupada)

- Ocupada

- Removida (vazia mas já ocupada)

- Pesquisar/Remover

- Termina quando encontrar o objeto

- Termina quando encontrar uma posição Livre

- Continua quando encontrar uma posição Removida

- Inserir

- Insere o objeto quando encontrar uma posição Livre ou Removida


Hashing aberto 40/47

Hashing aberto

Conceitos gerais

- A estruturação dos dados é talvez a forma mais intuitiva de se implementar o

conceito de Hashing

- Consiste em ter um vetor de apontadores, com dimensão N, em que cada

elemento do vetor contém uma ligação para uma lista dos elementos a guardar

A pesquisa de um elemento efetua-se da seguinte forma:

- calcular, a partir de uma chave, qual o elemento do vetor é a cabeça da lista que se

pretende;

- pesquisar o elemento naquela lista, usando um qualquer algoritmo para o efeito.



Exemplo 1

- Armazenar os elementos: 19, 26, 33, 70, 79, 103 e 110.

- Função de hash: hash(x) = x % 10

- Construir a respetiva Tabela de hash.

- Os valores da função de hash para aqueles elementos são os seguintes:

- hash(19) = 9

- hash(26) = 6

- hash(33) = 3

- hash(70) = 0

- hash(79) = 9

- hash(103) = 3

- hash(110) = 0



Exemplo 1 (cont.)

- A Tabela de hash é a seguinte:

0 1 2 3 4 5 6 7 8 9

70 33 26 19

110 103 79



Exemplo 2

- Cada elemento do vetor é um apontador para uma lista de estruturas com o

mesmo valor da função de hash.

- Considere-se que

- a tabela (vetor) tem tamanho 13 (tam = 13) e

- a função de hash é a que consta na tabela que se segue

Chave A,B C,D E,F G,H I,J K,L M,N O,P Q,R S,T U,V X,Y W,Z

hash 0 1 2 3 4 5 6 7 8 9 10 11 12

- Calcular os valores de hash para as seguintes chaves:

Alce, Burro, Gato, Hiena, Pato, Sapo, Zebra, Vaca e Tigre.



Exemplo 2 (cont.)

- A tabela de hash é a seguinte:

0 1 2 3 4 5 6 7 8 9 10 11 12

Burro Gato Pato Tigre Vaca Zebra

Alce Hiena Sapo



Propriedades

- Reduz o número de comparações, quando comparado com a pesquisa

sequencial

- Necessidade de espaço em memória para armazenar o vetor de listas


Hashing (aberto e fechado) 46/47

Hashing (aberto e fechado)

Hashing aberto

- suporta a operação básica de remoção,

- as listas de colisão não se cruzam,

- o erro por defeito do pré-dimensionamento não é tão grave.

Hashing fechado

- se a tabela estiver num ficheiro poupam-se muitos acessos com a sondagem

linear, porque em geral os elementos que colidem estão fisicamente próximos.


Hashing (aberto e fechado) 47/47

Vantagens do Hashing

- No Hashing aberto,

- a complexidade das operações básicas (pesquisa, inserção e remoção) é constante

(O(n) = 1), no caso esperado.

- No Hashing fechado,

- a técnica é eficiente e só depende

- do fator de ocupação e

- da qualidade das funções de hash

Desvantagens do Hashing

- Não é uma estrutura dinâmica (o redimensionamento é necessário).

- Não suporta operações básicas que se baseiam em relações de ordem dos

elementos (mínimo, máximo, percurso ordenado, …).

- No Hashing aberto a complexidade das operações básicas (pesquisa, inserção e

remoção) é linear em relação ao número de elementos da tabela, no pior caso.


Documents

TABELAS DE DISPERSÃO/HASH - UBIcbarrico/Disciplinas/.../Teorica_TabelasHashing.pdf · Tabela de Hash 8/47 Tabela de Hash Definição-É um tipo de estruturação criado para o armazenamento