hashing

Estruturas de Dados

Hashing
Prof. Ricardo J. G. B. Campello
Parte deste material é baseado em adaptações e extensões de slides disponíveis em http://ww3.datastructures.net (Goodrich & Tamassia).

Motivação
Árvores AVL permitem realizar as operações básicas de busca, inserção e remoção de itens em tempo O(log n), o n é o no. de itens
É possível conseguir desempenho melhor ???

1

Hashing
Uma abordagem para tentar obter desempenho superior àquele das árvores AVL é conhecida como hashing
Essa abordagem utiliza uma estrutura de dados denominada tabela hash
Também denominada tabela de dispersão

Tabela Hash
Uma tabela hash para um dado tipo de chave consiste de:
Uma função hash h
Um arranjo (tabela) de tamanho N

Uma função hash h mapeia chaves de um dado tipo em inteiros em um intervalo fixo [0, N − 1]
O valor inteiro h(k) ∈ [0, N − 1] é chamado de valor hash da chave k

2

Tabela Hash
Aplicação em Mapas / Dicionários:
Item com chave k armazenado no índice i = h(k) da tabela
O índice é calculado, não procurado

Tabela Hash - Exemplo
Tabela hash para um mapa armazenando itens (CPF,
Dados Pessoais), onde a chave CPF é um inteiro positivo com 11 dígitos

h(k) = 4 últimos dígitos de k

∅

9997
9998
9999

∅

025.612.000-01
981.101.000-02

∅
451.229.000-04

…

No exemplo ao lado utilizase um arranjo de tamanho
N = 10.000 e a seguinte função hash:

0
1
2
3
4

200.751.799-98

∅

Pode haver conflitos...?

3

Colisões
Colisões ocorrem quando diferentes chaves são mapeadas sem distinção na mesma célula da tabela
Colisões podem ocorrer tanto na fase de codificação das chaves (h1) como na fase de compressão (h2)
Ocorrendo na fase de codificação, não há como serem revertidas na fase de compressão
Colisões requerem tratamentos a

posteriori que, por sua vez, demandam esforço computacional
Funções hash devem ser simples e rápidas de calcular, minimizando ao máximo colisões

0∅
1