Aula de Estrutura de dados sobre tabelas espalhamento

Prévia do material em texto

Estruturas de Dados
Tabelas de Espalhamento
Prof. Eduardo Alchieri
 
Tabelas de Espalhamento
(introdução)
 Uma estrutura como, as árvores binárias de busca, que 
trabalhe na ordem de log n é muito eficiente, mas em algumas 
situações é necessário o acesso instantâneo aos dados: O(1)
 Para isso, utiliza-se uma “função mágica” que calcula o 
endereço do dado.
 Ideia geral: usar uma função f(x) que associa as chaves do 
espaço de busca a um conjunto de inteiros entre 0 e k-1, 
correspondente ao índice numa tabela contendo os valores 
sendo procurados.
 
Tabelas de Espalhamento
(introdução)
 Exemplo: inventário de 100 itens
 Itens identificados por uma chave de 2 dígitos
 Vetor de 100 elementos onde o índice i é a própria chave
 E se forem menos de 100 itens? O mesmo vetor também 
resolve
 E se os itens forem identificados por uma chave de 7 
caracteres?
 índice = função_de_dispersão(chave)
 A função de dispersão associa chaves de pesquisa a uma 
posição (índice) no vetor.
 
Tabelas de Espalhamento
(introdução)
 Exemplo: inventário de 100 itens
0
1 Item 10
2
3 Item 50
4
5
6
7 Item 40
...
99
Item 10 (item_10)
Item 40 (item_40)
Item 50 (item_50)
Função
de
dispersão
 
Tabelas de Espalhamento
(introdução)
 Algumas concessões são feitas:
 Não é requerido que haja qualquer ordem dos itens na 
tabela
 Não permite recuperar o elemento antecessor/ sucessor
 Embora ainda queremos remover itens, não é o principal 
objetivo fazer operações de remoção tão eficientes quanto 
as operações de localização e inserção
 Para conseguir operações em O(1)
 A ordem de inserção dos elementos não têm influência
 O número de elementos não têm influência
 Não há comparações desnecessárias
 
Tabelas de Espalhamento
(introdução)
 Tabela de dispersão: permite realizar buscas eficientes em um 
conjunto de elementos armazenados em uma tabela (um vetor) 
de maneira não ordenada
 Mecanismos de inserção e recuperação do elemento
 Dado um par {chave, elemento}, onde chave é a chave de 
busca e elemento é o elemento/dado a ser armazenado:
 Inserção: 
 Utilizando a chave, calcula-se o índice da posição na 
tabela onde o elemento deve ser armazenado
 Inserir o elemento na posição calculada
 Recuperação (busca/remoção)
 Utilizando a chave, calcula o índice onde o elemento 
está armazenado
 Pega o elemento na posição do índice calculado
 
Tabelas de Espalhamento
(operações)
 Principais operações
 Dado um conjunto de pares (chave,valor)
 Determinar se uma chave está no conjunto e o valor 
associado (busca)
 Inserir um novo par no conjunto
 Remover um par do conjunto
 Uma tabela de dispersão (espalhamento) é uma estrutura de 
dados eficiente
 A busca por um elemento, no pior caso, pode levar O(n)
 O tempo médio esperado de busca é na ordem de O(1)
 
Tabelas de Espalhamento
(vantagens/desvantagens)
 Vantagens:
 Algoritmos simples e eficientes para inserção, busca e 
remoção
 Desvantagens:
 Nenhuma garantia de balanceamento (depende da função 
de dispersão)
 Espaço subutilizado nas tabelas (depende da função de 
dispersão)
 O grau de espalhamento é sensível à função de dispersão 
utilizada e ao tipo de informação usada como chave
 
Tabelas de Espalhamento
(colisões)
 E se duas (ou mais) chaves forem mapeadas para o mesmo 
índice ?
 Colisão!!!
 
Tabelas de Espalhamento
(colisões)
 Colisões é um grande problema!!!
 Problema do aniversário: Dado um grupo de 23 (ou mais) 
pessoas escolhidas aleatoriamente, a chance de que duas 
pessoas terão a mesma data de aniversário e de mais de 
50%. Para 57 ou mais pessoas, a probabilidade é maior do 
que 99%.
 A colisão pode ser evitada conhecendo-se todas as chaves
 Escolhe-se a função de dispersão ideal (perfeita) para 
obter a indexação perfeita
 Como isto não é prático, outras técnicas são 
utilizadas
 
Tabelas de Espalhamento
(colisões)
 Fator de carga (σ ): razão entre o número de chaves e o 
tamanho da tabela
 Geralmente < 0.7 (com uma boa função de dispersão)
 Fator de carga alto indica que a memória esta sendo bem 
utilizada, mas implica em maior probabilidade de colisão.
 Fator de carga baixo implica em menor probabilidade de 
colisão mas indica que a memória esta sendo desperdiçada
 
Tabelas de Espalhamento
(colisões)
 Dois métodos para tratar colisões:
 Endereçamento aberto
 Resolução de colisões através de encadeamento
 
Tabelas de Espalhamento
(colisões)
 Endereçamento aberto (reespalhamento)
 A ideia é procurar por outra posição desocupada na tabela
 Nestes casos, chama-se tabela de espalhamento
 Três possibilidades:
 
Tabelas de Espalhamento
(colisões)
 Resolução de colisões através de encadeamento
 Modifica a estrutura da tabela de forma que a mesma possa 
comodar mais do que um elemento por localização
 Cada posição do vetor possui uma lista ligada
 Nesta caso é chamada de tabela de dispersão
 Em nosso exemplo:
 
Tabelas de Espalhamento
(colisões)
 Análise
Pesquisa sem sucesso Pesquisa com sucesso
 
Tabelas de Espalhamento
(funções de dispersão)
 Uma boa função de disperção satisfaz a condição de 
espalhamento uniforme simples:
 Cada chave tem a mesma probabilidade de ser mapeada 
para cada uma das entradas da tabela
 Uma abordagem comum é derivar uma função de dispersão 
cujo comportamento esperado seja independente de 
qualquer padrão existente nos dados
 Na prática utilizamos heurísticas para criar uma função de 
espalhamento que apresenta um bom desempenho
 
Tabelas de Espalhamento
(funções de dispersão)
 Estudaremos na sequência três métodos de concepção de 
funções de espalhamento
 Espalhamento por divisão
 Espalhamento por multiplicação
 Espalhamento universal
 
Tabelas de Espalhamento
(funções de dispersão)
 Espalhamento por divisão
 A função de dispersão (h) mapeia a chave k para uma das 
entradas ao tomar o resto da divisão de k por m:
 h(k) = k mod m
 Por exemplo, para m = 12 e k = 100
 h(100) = 4
 Quando usamos o método da divisão, devemos evitar certos 
valores de m:
 Devemos evitar potências, pois para m = 2p, h(k) é 
simplesmente os p bits menos significativos
 É preferível fazer com que h(k) dependa de todos os 
bits de k, não apenas dos p menos significativos
 
Tabelas de Espalhamento
(funções de dispersão)
 Espalhamento por divisão
 Bons valores para m são números primos não muito 
próximos de potências de 2
 Suponha que desejamos alocar n = 2000 cadeias de 8 bits, 
e que não nos importamos em procurar em listas de 
tamanho médio 3.
 Então, podemos fazer m = 701 pois 701 é um número primo 
próximo de 2000/3; σ = 2000/3 que é aprox. 3
 Note que 701 não é muito próximo de potências de 2. As 
duas potências mais próximas são 512 e 1024
 A função de espalhamento toma a forma:
 h(k) = k mod 701
 
Tabelas de Espalhamento
(funções de dispersão)
 Espalhamento por multiplicação
 O método utiliza uma constante A, 0 < A < 1, sendo h(k) 
calculado como:
 Note que (kA mod 1) é a parte fracionária de kA
 A vantagem do método de multiplicação é que o valor de m 
não é crítico como no método da divisão
 
Tabelas de Espalhamento
(funções de dispersão)
 Falhas potenciais dos métodos anteriores
 Na pior das hióteses, um adversário poderia escolher n 
chaves mapeadas para uma mesma entrada, resultando em 
um tempo de busca O(n)
 A única forma efetiva de melhorar esta situação é escolher 
uma função de espalhamento aleatoriamente, que seja 
independente das chaves que serão armazenadas na tabela
 Esse mecanismo é chamadode Espalhamento Universal, e 
resulta em um bom desempenho médio
 
Tabelas de Espalhamento
(funções de dispersão)
 Espalhamento Universal
 A ideia principal atrás do espalhamento universal é escolher 
uma função de espalhamento de forma aleatória, em tempo 
de execução, a partir de uma classe de funções 
cuidadosamente definida
 Devido à randomização, o algoritmo apresenta desempenho 
variável a cada execução, até mesmo para uma mesma 
entrada
 Seja H uma coleção finita de funções de espalhamento que 
mapeiam um dado universo de chaves U para um nímero do 
conjunto {0, 1, . . . ,m − 1}
 A coleção H é dita universal se para cada x, y de chaves 
distintas de U, o número de funções h pertencentes a H tal 
que h(x) = h(y) é precisamente |H|/m
 
Tabelas de Espalhamento
(funções de dispersão)
 Espalhamento Universal
 Em outras palavras, com uma função escolhida 
aleatoriamente dentre os elementos de H, a chance de uma 
colisão entre x e y, x diferente de y, é precisamente 1/m
 A probabilidade de escolher uma funçao h pertencente a 
H é 1/|H|
 A probabilidade de h gerar um conflito entre x e y é |
H|/m
 Portanto, a probabilidade de uma função h escolhida 
aleatoriamente gerar um conflito é
 (|H|/m) * (1/|H|) = 1/m
 
Tabelas de Espalhamento
(funções de dispersão)
 Espalhamento Universal
 Teorema: Se uma função h, escolhida de uma coleção 
universal de funções de dispersão, é usada para espalhar 
chaves em uma tabela de tamanho n, onde n ≤ m, então o 
número esperado de colisões envolvendo uma chave 
particular x é menor do que 1.
 
Tabelas de Espalhamento
(resumo)
 Tabela de disperção/espalhamento: um vetor que contém os 
itens nas posições indicadas pela função de disperção
 Função de disperção: função que mapeia cada chave em uma 
localização (índice) da tabela que contem o ítem
 Colisões: quando a função de dispersão mapeia mais do 
que uma chave para o mesmo índice
 Esquemas para tratar colisões: indicam posições diferentes 
para chaves envolvidas em uma colisão
 Requisitos para uma função de dispersão
 Ser fácil de computar (O(1))
 Uma boa função evita colisões
 Uma boa função tende a espalhar as chaves pelo vetor
 
Tabelas de Espalhamento
(considerações)
 Tabelas de espalhamento/dispersão têm tempo médio de 
busca constante.
 A avaliação de uma boa função de dispersão é complexa
 Os dados na memória ficam aleatoriamente distribuídos
 
Tabelas de Espalhamento
(limitações)
 Estrutura de dados do tipo dicionário, que não permite:
 Armazenar elementos repetidos
 Recuperar elementos sequencialmente (ordenação)
 Recuperar o elemento antecessor/sucessor
 Para otimizar a função de dispersão é necessário conhecer a 
natureza da chave a ser utilizada.
 No pior caso, a ordem das operções pode ser O(n)
 Podem necessitar de redimensionamento
 O custo da função de dispersão pode ser proibitivo
 
Tabelas de Espalhamento
(aplicações)
 Vetor associativo (cujos índices são strings arbitrárias), 
especialmente em linguagens interpretadas (AWK, Perl, e PHP)
 Indexação de bancos de dados (embora árvores sejam mais 
comuns)
 Cache de memória: memória auxiliar para acelerar o 
processamento
 Conjuntos (indica a existência e recupera rapidamente)
 Representação de objetos em linguagens de programação 
dinâmicas (Perl, Python, JavaScript, e Ruby)
 Representação única de dados (em LISP, para evitar a criação 
de strings repetidas)
 Etc.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28