Tabela Rash - C#

AED

Tabelas HASH

AED
●

Método tradicional de pesquisa: comparação de chaves

●

Chaves sem ordenação: pesquisa sequencial

●

Chaves organizadas: pesquisa binária
●

Árvores de pesquisa

AED
●

Tabelas Hash
●

Também chamadas de tabelas de dispersão

●

Endereçamento direto

●

Transformação aritmética da chave de pesquisa
2•
7•
−2•
10•
−7•
4•

•100
•16
•25
•49
•11
•4

AED
●

Tabelas Hash
●

●

Computar o valor da função de transformação e localizar a posição da tabela
Tratar possíveis colisões
–

Colisão: duas chaves vão para a mesma posição da tabela AED
●

Exemplo: f(x) = x%9
●

X = 34 → pos 7

Pos

Chave

0
1
2
3
4
5
6
7
8

34

AED
●

Exemplo: f(x) = x%9
●

X = 21 → pos 3

Pos

Chave

0
1
2
3

21

4
5
6
7
8

34

AED
●

Exemplo: f(x) = x%9
●

X = 18 → pos 0

Pos
0

Chave
18

1
2
3

21

4
5
6
7
8

34

AED
●

Exemplo: f(x) = x%9
●

X = 16 → pos 7
–

COLISÃO

Pos
0

Chave
18

1
2
3

21

4
5
6
7
8

34

AED
●

Tabelas Hash
●

Achar uma boa função de transformação

●

Tratar colisões

AED
●

Funções de transformação
●

Evitar colisões

●

Paradoxo do aniversário:
–
–

●

com mais de 23 pessoas juntas, há uma probabilidade maior que 50% de aniversários coincidentes
30 pessoas, cerca de 70% de coincidência

Ou seja, mesmo uma tabela com 365 “espaços” e apenas 30 chaves, podemos ter muitas colisões

AED
●

Funções de transformação
●

Boas funções:
–
–

Simples de computar
Saídas possíveis com probabilidades iguais

AED
●

Função identidade
●

f(x) = x

●

Fácil de computar?

●

Probabilidades iguais?

●

E o uso de espaço ocioso?

●

Quando usar?

AED
●

Divisão e resto
●

f(x) = x % N

●

N determina o tamanho da tabela

●

N também “determina” as colisões

●

Ex:
–

f(x) = x % 8
●
●
●