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 No exemplo ao lado utilizase um arranjo de tamanho N = 10.000 e a seguinte função hash: h(k) = 4 últimos dígitos de k

0 1 2 3 4 9997 9998 9999

∅
025.612.000-01 981.101.000-02

∅
451.229.000-04

∅
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

0∅ 1 2∅ 3∅ 4

612-0001

229-0004

101-0004

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

Note