Tabelas Hash

Motivação
•Dada uma tabela com uma chave e vários valores por linha, quero rapidamente procurar, inserir e apagar registros baseados nas suas chaves

Tabelas Hash

•Estruturas de busca sequencial/binária levam tempo até encontrar o elemento desejado.
Ex: Arrays e listas

Ex: Árvores
8

5 2 6 1 7 8 4 9

2
5

•A estrutura com tal propriedade é chamada de tabela hash. 20 mod 8 = 4
1

2

3

4

5

6

1

6
4

• Os registros com as chaves são armazenados nessa tabela, e endereçados a partir de uma função de transformação sobre a chave de pesquisa
• A essa função dá-se o nome de Função HASHING
• Seja M o tamanho da tabela:
– A função de hashing mapeia as chaves de entrada em inteiros dentro do intervalo [1..M]
– A função de hashing h(kj)  [1,M] recebe uma chave

7

7

kj  {k0,..,km} e retorna um número i, que é o índice do

45 ?

subconjunto mi  [1,M] onde o elemento que possui essa

11 ?
11 mod 8 = 3

4

• Formalmente:

45 mod 8 = 5

11 20

64

1

Funções Hashing

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

0

6

Motivação

20 ?

2

9

Funções Hashing

chave vai ser manipulado

Resto da Divisão

• Método pelo qual:
– As chaves de pesquisa são transformadas em endereços para a tabela (função de transformação);
– Obtém-se valor do endereço da chave na tabela HASH

• Tal função deve ser fácil de se computar e fazer uma distribuição equiprovável das chaves na tabela
• Existem várias funções Hashing, dentre as quais:
–
–
–
–
–

Resto da Divisão
Meio do Quadrado
Método da Dobra
Método da Multiplicação
Hashing Universal

• Forma mais simples e mais utilizada
• Nesse tipo de função, a chave é interpretada como um valor numérico que é dividido por um valor
• O endereço de um elemento na tabela é dado simplesmente pelo resto da divisão da sua chave por M (Fh(x) = x mod M), onde M é o tamanho da