Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
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çãode
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 é chamado de 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 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28