Tabela hash - Universidade Federal de Ouro Preto

Tabelas Hash
Prof. Túlio Toffolo http://www.toffolo.com.br BCC202 – Aula 21 e 22
Algoritmos e Estruturas de Dados I

Pesquisa em Memória Primária
• Introdução - Conceitos Básicos
• Pesquisa Sequencial
• Pesquisa Binária
• Transformação de Chave (Hashing)‫‏‬
• Listas Encadeadas
• Endereçamento Aberto
• Hashing Perfeito

• Árvores de Pesquisa
• Árvores Binárias de Pesquisa
• Árvores AVL
2

Transformações de Chaves

PROGRAMAÇÃO
FUNÇÃO DE HASH
DE TRIPULAÇÕES

Transformação de Chave (Hashing)
• Os registros armazenados em uma tabela são diretamente endereçados a partir de uma transformação aritmética sobre a chave de pesquisa.
• Hash significa:
• Fazer picadinho de carne e vegetais para cozinhar.
• Fazer uma bagunça. (Webster’s New World Dictionary)‫‏‬
• Espalhar x Transformar (informática x computação)

4

Transformação de Chave (Hashing)
• Um método de pesquisa com o uso da transformação de chave é constituído de duas etapas principais:
1. Computar o valor da função de transformação, a qual transforma a chave de pesquisa em um endereço da tabela.
2. Considerando que duas ou mais chaves podem ser transformadas em um mesmo endereço de tabela, é necessário existir um método para lidar com colisões.

5

Transformação de Chave (Hashing)
• Qualquer que seja a função de transformação, algumas colisões irão ocorrer fatalmente, e tais colisões têm de ser resolvidas de alguma forma.
• Mesmo que se obtenha uma função de transformação que distribua os registros de forma uniforme entre as entradas da tabela, existe uma alta probabilidade de haver colisões.

6

Colisões
• O paradoxo do aniversário (Feller, 1968, p. 33)
• Em um grupo de 23 ou mais pessoas, existe uma chance maior do que 50% de que 2 pessoas comemorem o aniversário no mesmo dia.

• Assim, se for utilizada uma função de transformação uniforme que enderece 23 chaves randômicas em uma tabela de tamanho 365, a probabilidade