Introdução a Tabelas Hash - Computação UFCGdalton/cursos/edados/IntroducaoATabelasHash.pdf · tabelas hash Mas, qual o custo

© 2004 Dalton Serey - DSC/UFCG V0.2

Estruturas de Dados e AlgoritmosEstruturas de Dados e Algoritmos

Introdução a Tabelas HashIntrodução a Tabelas Hash

Dalton SereyDalton SereyDepartamento de Sistemas e ComputaçãoDepartamento de Sistemas e ComputaçãoUniversidade Federal de Campina GrandeUniversidade Federal de Campina Grande


O que são mapas mesmo?O que são mapas mesmo?

● Mapas relacionam valores a chaves● Pense em mapas como tabelas...

Professor Disciplinacamilo lp1jorge grafos

joseluce labp1lula teoria

walfredo lp2

colunade chaves

colunade valores



● Podemos adicionar novos pares...● M[“dalton”] := “edados”

Professor Disciplinacamilo lp1jorge grafos


walfredo lp2



● Podemos adicionar novos pares...● M[“dalton”] := “edados”

Professor Disciplinacamilo lp1dalton edadosjorge grafos


walfredo lp2



● Podemos recuperar valores pelas chaves...● print M[“lula”]



walfredo lp2



● Podemos recuperar valores pelas chaves...● “teoria”



walfredo lp2


Como implementar mapas?Como implementar mapas?● Listas?● Conjuntos de pares?● Quais os custos dessas implementações?


Mapas em TabelasMapas em Tabelas● Idéia:

– guardar valores em uma tabela indexada por inteiros...– e mapear chaves em posições da tabela...

Professor poscamilo 3dalton 6jorge 5

joseluce 1lula 4

walfredo 2

Disciplina1 labp12 lp23 lp14 teoria5 grafos6 edados

um vetor!


Mapas em TabelasMapas em Tabelas● Claramente podemos usar um vetor como tabela!● A questão é: como mapear chaves em valores?

Professor poscamilo 3dalton 6jorge 5

joseluce 1lula 4

walfredo 2


Tabelas HashTabelas Hash

● A solução é usar uma função que calcule um valor inteiro a partir da chave em questão...

● Vamos denominar melhor os elementos envolvidos neste esquema...

universode chaves

posiçõesna tabela

função hashU Th


Tabelas de acesso diretoTabelas de acesso direto

● Se podemos fazer |T| = |U|– ou seja, se podemos alocar uma tabela com uma

posição para cada chave,● Então, basta adotar h:U → {1, 2, ..., m}

– sobrejetora: toda chave leva a alguma posição– injetora: cada posição corresponde a uma única chave– observe que, neste caso, m = |U|

● Esquema chamado de tabela de acesso direto



● O código não pode ser mais simples...● E quais os custos?

Insere(Elemento e, Chave c)1: T[h(c)] := e

Remove(Chave c)1: T[h(c)] := null

Elemento Recupera(Chave c)1: return T[h(c)]



● Contudo, nem sempre U é pequeno!● Por exemplo, suponha que a chave seja a

matrícula de um aluno da UFCG...– trata-se de um inteiro de 8 dígitos– logo, são 100.000.000 de chaves– se cada posição da tabela ocupar míseros 4 bytes,

precisamos de mais de 380Mbytes apenas para a tabela...

– mesmo que o mapa esteja vazio!



● Chamemos de K o conjunto das chaves que serão efetivamente armazenadas na tabela

● Na prática, |U| >> |K|...– logo, nossa tabela deveria ter a dimensão de |K|...– mais que isso seria desperdício de memória

● Como podemos fazer isso?● É impossível com tabelas de acesso direto!

– Por quê? Para que a função seja bijetora é preciso que U e T tenham a mesma cardinalidade!



● Solução: relaxar a condição de injetividade!● Ou seja, permitiremos que mais de uma chave seja

mapeada em uma única posição da tabela...● Como |U| >> |K| = |T|, se tivermos sorte, no uso

prático nunca ocorrerão duas chaves que sejam mapeadas para a mesma posição...



● O problema é que onde a Lei de Murphy vale...● Colisão: ocorrência de uma chave cujo valor de

hash é igual ao de outra chave já armazenada no mapa.

● O que fazer quando ocorrem colisões?



● Uma solução simples: ao invés de armazenarmos um valor em cada posição da tabela, armazenamos uma lista de valores...

● Neste caso, ao ocorrer uma colisão, basta anexar o novo valor lido à lista correspondente à chave...

● Como fica o código?



● Quais os custos das operações?

Insere(Elemento e, Chave c)1: T[h(c)].insere(Par(e,c))

Elemento Recupera(Chave c)1: para cada Par(e,k) em T[h(c)]2: if k = c3: return e4: return null



● É fácil perceber que a inserção é O(1)...● Mas quanto custa Recupera?

Insere(Elemento e, Chave c)1: T[h(c)].insere(Par(e,c))




● Pior caso: toda a lista T[h(c)] é percorrida e ela contém os |K| elementos esperados para o mapa...

● Como n = |K|, no pior caso, o custo é O(n)




● Contudo, este caso só ocorre se a função mapear todos as chaves armazenadas para uma única posição!

● Quais as chances disso ocorrer?




● A idéia é usar a probabilidade a nosso favor...● A escolha da função de hash é feita

criteriosamente para minimizar essa probabilidade● Na prática, forçamos a chance a ser nula...● Isso nos leva a considerar a análise do caso médio

como melhor estimativa do desempenho para tabelas hash

● Mas, qual o custo do caso médio?



● Se escolhermos muito bem a função de hash, então teremos uma distribuição uniforme das chaves na tabela...

● Como a tabela tem o mesmo número de posições que de chaves armazenadas, há uma boa probabilidade de que tenhamos 1 chave em cada posição

● Nessas condições, podemos dizer que o custo esperado da recuperação é O(1)


Tabelas Hash: análiseTabelas Hash: análise● Situação de pior caso para o acesso

– todos as chaves do mapa em uma única posição– o acesso ocorre nessa mesma posição– a chave procurada não está no mapa

● A lista tem n elementos, logo o tempo é O(n)

● Qual a validade dessa análise?– a função de hash tem que ser terrível– pouquíssimas chances de ser realista na prática


Tabelas Hash: análiseTabelas Hash: análise● Conceito: fator de carga

● É o tamanho médio das listas da tabela.● O tempo esperado de acesso é

= nm

O 1


Tabelas Hash: análiseTabelas Hash: análise● Na prática, escolhemos m = O(n)● Logo,

● E, portanto, o tempo esperado de acesso é

O 1O 1=O 1

= nO n

=O 1



● Logo, podemos implementar mapas cujas operações de inserção, recuperação e remoção operam em tempo O(1).

● Com os devidos cuidados, é fácil garantir esse desempenho na prática...

● O fundamental é controlar o fator de carga– controlando o tamanho da tabela– com base no número de elementos armazenados

● ...e utilizar uma boa função de hash!


ExercíciosExercícios

● Dê uma olhada no código da class HashMap de Java.

● Quais as características necessárias de uma função de hash a ser usada em uma tabela de acesso direto? E para uma tabela hash?

● O que é uma colisão?

Documents

Introdução a Tabelas Hash - Computação UFCGdalton/cursos/edados/IntroducaoATabelasHash.pdf · tabelas hash Mas, qual o custo