Estrutura de Dados

Estrutura de Dados
TABELAS HASH

Roteiro
• Contextualização
• Conceitos Básicos
• Hashing (método de pesquisa)
– Hashing Perfeito
– Hashing Imperfeito
• Colisões
– Métodos de Tratamento de Colisões
• Limitações e demais aplicações

Roteiro
• Contextualização
• Conceitos Básicos
• Hashing (método de pesquisa)
– Hashing Perfeito
– Hashing Imperfeito
• Colisões
– Métodos de Tratamento de Colisões
• Limitações e demais aplicações

Contextualização
• Dado um conjunto de pares (chave,valor)
– determinar se uma chave está no conjunto e o valor associado
– inserir um novo par no conjunto
– remover um par do conjunto
• Estruturas que podem ser usadas
– Tabelas simples (vetores ou listas)
– Árvores de busca
– Tabelas de espalhamento (hash)

Contextualização
• Os métodos de pesquisa vistos até agora buscam informações armazenadas com base na comparação de suas chaves.
• Para obtermos algoritmos eficientes, armazenamos os elementos ordenados e tiramos proveito dessa ordenação. Contextualização
• Conclusão: os algoritmos mais eficientes de busca mostrados até o momento demandam esforço computacional O(n), quando usamos uma tabela hash, esta pode realizar tais operações em tempo esperado O(1).

• Veremos agora, o método de pesquisa conhecido como hashing (tabela de dispersão, espalhamento, indexação, escrutínio ou método de cálculo de endereço). Na média dos casos, é possível encontrar a chave com apenas UMA OPERAÇÃO de LEITURA.

Contextualização
• Em algumas aplicações, é necessário obter o valor com poucas comparações, logo, é preciso saber a posição em que o elemento se encontra, sem precisar varrer todas as chaves.
• A estrutura com tal propriedade é chamada de tabela hash.
20 mod 8 = 4
0

20 ?

1

64

11 ?
11 mod 8 = 3

2

45 mod 8 = 5
3

4

11 20

5

6

7

7

45 ?

Contextualização
• A utilização de hashing envolve
– Computar a função de transformação
– Tratar colisões.