Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 Tabela Hash 1 Estrutura de Dados e Algoritmos Prof. Cláudio Campelo, PhD Departamento de Sistemas & Computação / UFCG Estruturas vistas até agora 2 � Estruturas lineares: vetor, fila, lista e pilha � Ordenadas ou não � Árvores Binárias de Pesquisa � Ordenadas � Heaps Binárias � Chaves com certa ordem � Todas são estruturas de busca e levam tempo até encontrar o elemento desejado 8 2 6 4 1 9 5 2 6 1 7 8 4 9 5 2 6 1 4 2 Estruturas vistas até agora 3 � Estruturas lineares: vetor, fila, lista e pilha � Ordenadas ou não � Árvores Binárias de Pesquisa � Ordenadas � Heaps Binárias � Chaves com certa ordem � Todas são estruturas de busca e levam tempo até encontrar o elemento desejado 8 2 6 4 1 9 5 2 6 1 7 8 4 9 5 2 6 1 4 Será que existe alguma forma de estruturar os dados para que as pesquisas sejam O(1)? Problema 4 � Cenário: � Suponha que desejamos ter inserção, remoção, pesquisa em O(1) para um sistema que gerencie os N discentes e docentes do DSC/UFCG? Assuma que cada pessoa possui um número identificador único no intervalo [1..N]. � Que estrutura de dados vocês escolheriam? 3 Tabela de Acesso Direto 5 Admitindo que K é relativamente pequeno Tabela de Acesso Direto 6 � Poucos elementos � Seja k ∈ U = {0,1,2...,m-1} � Todas as chaves da tabelas são distintas � Criar Array A � A[0..m-1] � A[k] = x, � se k = key[x] � ou A[k] = null 1 3 4 6 7 80 / / / / / / / key=2 João key=9 Leila key=5 Maria 2 5 9 Chaves (K) h(k) = k Acesso direto 4 Tabela de Acesso Direto 7 � Operações (inserir, remover, pesquisar) utilizando a tabela de acesso direto. Direct-Address-Search(T, k) return T[k] Direct-Address-Insert(T, x) T[key[x]] ← x Direct-Address-Delete(T, x) T[key[x]] ← NIL Tabela de Acesso Direto (Problemas) 8 O que acontece se U for muito grande? E se K for muito pequeno em relação a U? O que acontece quando |U| é muito maior que length(T)? 5 Tabelas Hash 9 � Também conhecidas como tabelas de dispersão � Resolve o problema quando |U| > length(T) mantendo o tempo de acesso em O(1) em média. � Não usa a identidade para mapear chaves em indices mas uma função de hashing. � Se |U| > length(T) pelo menos duas chaves são mapeadas para o mesmo índice (colisão) � É impossível não ter colisões � Elas devem ser minimizadas }1,...,0{: −→ mUh Tabela Hash 10 � Exemplo de colisão )(kh 6 Características 11 � Não precisamos ocupar |U| posições na tabela � Ocupamos menos espaço do que com a tabela de acesso direto � Espaco: O(|K|), onde K é o conjunto de chaves guardadas � Dá para conseguir acesso com tempo O(1) na média � O elemento com chave k é guardado na posição h(k) da tabela � h é a função hash � h tem que ser determinística Exemplo 12 � Seja h(k)=k%10 uma função hash que mapeia de chaves do universo K em {2,5,9,100,107}. Considere uma tabela com m=10 células. / / / / / / / Universo de Chaves (U) 2 ... 9 ... 5 ... 2 5 9 K 7 Exemplo 13 � O que acontece se utilizarmos a função hash h(k)=k%10 para inserir os elementos {2,5,9,12}? / / / / / / / Universo de Chaves (U) 2 ... 9 ... 5 ... 2 5 9 12 Colisões 14 � Tabela hash ideal seria aquela sem colisão � Impossível quando |U| > m (tamanho da tabela) � Existem mais chaves que posições � Duas ou mais chaves são mapeadas em um mesmo índice � Escolher uma boa função hash para minimizar as colisões 8 Resolução de Colisões (Abordagens) 15 � Endereçamento fechado � Elementos com mesmo código hash são colocados na mesma posição da tabela (chaining) � Na verdade, inseridos na cabeça da lista já que existe a idéia que o o elemento inserido será usado em breve � Endereçamento aberto � Chaves com mesmo código hash são colocadas em posições diferentes Endereçamento Fechado: Chaining 16 � Usar uma lista encadeada 9 Exercício 17 � Implemente as operações (inserir, remover, pesquisar) utilizando a resolução de conflitos by chaining. � Inserir(T,x) � Remover(T,x) � Pesquisar(T,k) Exercício 18 � Implemente as operações (inserir, remover, pesquisar) utilizando a resolução de conflitos by chaining? � Inserir(T,x) � Inserir x na cabeça de T[h(key(x))]; � Remover(T,x) � Deletar x da lista T[h(key(x))]; � Pesquisar(T,k) � Buscar x na lista T[h(k)]; 10 Exercício 19 � Implemente as operações (inserir, remover, pesquisar) utilizando a resolução de conflitos by chaining? � Inserir(T,x) � Inserir x na cabeça de T[h(key(x))]; � Remover(T,x) � Deletar x da lista T[h(key(x))]; � Pesquisar(T,k) � Buscar x na lista T[h(k)]; Faça a análise do pior caso das operações (inserir, remover, pesquisar) Exercício 20 � Qual seria a tabela final considerando endereçamento fechado (resolução por chaining) e função de hash h(k)=k%2 e chaves do universo K={2,4,6,8}? 11 Exercício 21 � Qual seria a tabela final considerando endereçamento fechado (resolução por chaining) e função de hash h(k)=k%2 e chaves do universo K={2,4,6,8}? / 8 ... 2 4 6 6 ... 4 ... 2 ... 8 Fator de Carga 22 � A função h faz um hashing uniforme simples � Chaves possuem igual probabilidade de serem mapeadas para qualquer um dos índices � Cada célula da tabela vai ter um número mais ou menos igual de elementos � Origina a noção de load factor (fator de carga) α (numero médio de elementos em cada lista) � n = número de chaves � m = número de células na tabela � α = n/m � Exemplo: qual o fator de carga de uma tabela hash com 50 células e 100 chaves? 12 Exercício 23 � Qual o limite assintoticamente restrito usando o fator de carga (α) para uma pesquisa? Exercício 24 � Qual o limite assintoticamente restrito usando o fator de carga (α) para uma pesquisa? ... ... h(ki) ... h(kj) ... h(kn) ... ... T i Θ(1+ α) Aplicar a função hash 13 Exercício 25 � Quando uma pesquisa será feita em Θ(1)? Exercício 26 � Quando uma pesquisa será feita em Θ(1)? � α = n/m = O(1) � n = O(m) ... ... h(ki) ... h(kj) ... h(kn) ... ... T i Θ(1+ α) 14 Exercício 27 � Vamos utilizar a função hash h(k) = k%m (m=10) para guardar os RGs. Qual o último dígito do RG de vocês? Como vai ficar a tabela hash depois de inserirmos todos os RGs de vocês? � Será que tem alguma função hash melhor? Exercício 28 � Vamos utilizar a função hash h(k) = k%m (m=10) para guardar os RGs. Qual o último dígito do RG de vocês? Como vai ficar a tabela hash depois de inserirmos todos os RGs de vocês? � Será que tem alguma função hash melhor? Como escolher uma função hash? 15 Características da Função Hashing 29 � Minimizar o número de colisões � Satisfazer a hipótese de hashing uniforme � Qualquer chave tem a mesma probabilidade de ser mapeada em qualquer um dos m slots. Mas é difícil � Alguns métodos ajudam � Divisão � Multiplicação � Consideramos as chaves como números � Fácil de mapear Strings,... para números Método da Divisão 30 � Usa o resto da divisão para encotrar valores hash � Neste método a função hash é da forma: � Método rápido (requer apenas uma divisão) h(k) = k mod m Número de células da tabela 16 Exercício 31 � Seja K = {2,4,12,10,5}, desenhe a tabela final considerando as seguintes funções hash (utilize a resolução de conflitos por chaining). As tabelas possuem 2, 5 e 10 células � h=k mod 2 � h=k mod 5 � h=k mod 10 Métododa Divisão 32 � O método da divisão garante boas funções de hashing? � O que basicamente muda entre as funções hash no método da divisão? � Qual(is) valor(es) escolhemos para m? 17 Método da Divisão 33 � O método da divisão garante boas funções de hashing? � O que basicamente muda entre as funções hash no método da divisão? � Qual(is) valor(es) escolhemos para m? � Não escolha um m tal que tenha um divisor d bem pequeno � Não escolha m = 2r, � Escolha m sendo um número primo que não seja próximo das potências de 2 ou 10 Exercício 34 � Suponha as chaves {200, 205, 210, 215, 220, ..., 595}. � Se eu escolher a função h(k) = k %100. Vai existir colisão em alguma célula? Se sim, quantas? � Se eu escolher a função h(k) = k %101. Vai existir colisão? Se sim, quantas? 18 Exercício 35 � Suponha as chaves {200, 205, 210, 215, 220, ..., 595}. � h(k) = k %100 : Cada célula preenchida terá quatro chaves � h(k) = k %101 : Cada célula preenchida terá uma chave 0 ... 5 ... 10 ... 200, 300, 400, 500 205, 305, 405, 505 210, 310, 410, 510 101 202 303 404 505 200 205 210 215 220, ... , 295, 300 099 003 008 013 018, ... , 093, 098 305 310 315 320 325, ... , 395, 400 002 007 012 017 022, ... , 092, 097 Applet 36 � http://www.cse.yorku.ca/~aaw/Hang/hash/Hash.html � http://www.engin.umd.umich.edu/CIS/course.des/cis 350/hashing/WEB/HashApplet.htm 19 Método da Multiplicação 37 � Neste método a função hash é da forma: � k é a chave � A é uma constante entre (0..1) � Um bom valor é � m (número de células) geralmente é 2p, onde p é inteiro � O valor de m não é crítico como no método da divisão � Um pouco mais lento do que o da divisão h(k) = �m (k.A mod 1) Extrai a parte fracionária de k.A ...6180339887.02/)15( =−≈A Exercício 38 � Calcule o codigo hash h = �m (kA mod 1) das chaves ({2, 3, 4, 5, 6, 10, 15}), onde A = 0.2 e m = 1000 h(2) = �1000 (2x0.2 mod 1) = 400 h(3) = �1000 (3x0.2 mod 1) = 600 h(4) = �1000 (4x0.2 mod 1) = 800 h(5) = �1000 (5x0.2 mod 1) = 000 h(6) = �1000 (6x0.2 mod 1) = 200 h(10) = �1000 (10x0.2 mod 1) = 000 h(15) = �1000 (15x0.2 mod 1) = 000 20 Tabela com Endereçamento Aberto 39 � Até agora vimos a resolução de conflitos por chaining (Endereçamento Fechado) � Precisa de uma estrutura de dados auxiliar (lista) � E se não tivermos listas para resolver as colisões? � Precisamos de um número m bem maior de células. � Chaves que colidam precisam ter seu hash code “recalculado” para encontrar um slot vazio � Todas as chaves estão em alguma célula. Cada entrada da tabela contém um elemento ou NIL Outra Forma de Resolver Conflitos 40 � Endereçamento aberto faz uso de um probe. � Examina a tabela (sequencial ou não) até encontrar um slot vazio. � A sequência de posições sendo examinadas dependem da chave. � Função hash é estendida � posição = h(k,p) � k = chave � p = probe 21 Exemplo: Inserção 41 � Insira a chave k=100 � Probe h(100,0) � Probe h(100,1) � Probe h(100,2) 200 / / 150 / / / 999 / / 100 Algoritmo: Inserção 42 22 Exemplo: Pesquisa 43 � Pesquisa a chave k=100 � Probe h(100,0) � Probe h(100,1) � Probe h(100,2) 200 / / 150 / / / 999 / / Algoritmo: Pesquisa 44 23 Endereçamento Aberto (Deleção) 45 � Como fazer uma remoção com endereçamento aberto? � Podemos atribuir NIL diretamente na posição da chave a ser removida? Endereçamento Aberto (Deleção) 46 � Como fazer uma remoção com endereçamento aberto? � Não podemos simplesmente dizer que o slot esvaziou colocando NIL � Usar uma flag (valor especial DELETED) ao invés de NIL � Alterar as funções � Inserir (inserir no flag se ele for DELETED) � Pesquisar (continuar a pesquisa no flag ao invés de NIL) 24 Exemplo 47 � Remova a chave k=100 � Probe h(100,0) � Probe h(100,1) � Probe h(100,2) � Pesquisar até achar a chave (remova – coloque um flag DELETED) ou uma célula vazia 200 / 100 150 / / / 999 / / X E como ficaria a inserção? Exemplo 48 || T[j] = DELETED 25 Hashing com Probing 49 � Como escolher a função hash no endereçamento aberto usando o probe? � Por que não utilizar a função h(k,i) = k%m? � Precisamos usar i para que o endereço mude. � Três técnicas são usadas para computar as sequências de probes � Linear Probing � Quadratic Probing � Double Hashing Linear Probing 50 � Dada uma função de hash ordinária (obtida por divisão ou multiplicação): � O método usa a função de hash da forma: � Slots buscados linearmente: � Fácil de implementar mas apresenta problemas � Clustering Primário – clusters podem surgir quando slots ocupados se agrupam. Isso aumenta o tempo da busca. }1,...,1,0{:' −→ mUh mikhikh mod))('(),( += ]1[ ... ]1)('[ )]('[( − + mT khT khT 26 Exercício 51 � Seja m=10, h(k) = k mod 5. Utilize o probing linear para inserir os valores ({10,15,2,12,4,8}) h(k,i) = (k mod 5 + i) mod 10 Probing Quadrático 52 � Neste método a função hash é da forma: � c1 e c2 são constantes � Primeiro elemento buscado T[h’(k)]. Demais variam com função quadrática de i. � Evita o clustering primário � Pode ocorrer um Clustering Secundário – duas chaves com mesmo probe inicial geram mesma sequência de probes � Mas é melhor do que o anterior Método da Divisão ou Multiplicação micickhikh mod))('(),( 221 ++= 27 Exercício 53 � Seja m=10, c1=3, c2=5, h(k) = k mod 5. Utilize o probing quadrático para inserir os valores ({10,15,2,12,4,8}): h(k,i) = (k mod 5 + 3i + 5i2) mod 10 Exercício 54 � Compare a resposta anterior com o linear probing e o endereçamento fechado (h(k) = k mod 10) com chaining para inserir os valores ({10,15,2,12,4,8}): h(k) = k mod 10 h(k,i) = (k mod 5 + i) mod 10 h(k,i) = (k mod 5 + 3i + 5i2) mod 10 28 Hashing Duplo 55 � Um dos melhores métodos para endereçamento aberto � Neste método a função hash é da forma: � A sequência de probe depende de duas formas em k. � Dicas � Faça h2(k) retornar um número ímpar e m ser um número 2p � Faça m ser um numero primo e h2(k) retornar um inteiro positivo menor que m � Excelentes resultados � Produz Θ(m) sequências (se aproxima mais do hashing uniforme simples) Método da Divisão ou Multiplicação mkhikhikh mod))(.)((),( 21 += Exercício 56 � Seja m=24, h1(k) = k mod 5 e h2(k) = k+1 mod 7. Utilize o hashing duplo para inserir os valores ({10,15,2,12,4,8}): h(k,i) = (k mod 5 + (k+1 mod 7).i) mod 24 29 POSCOMP 2009 57 Fator de Carga 58 � Qual o fator de carga no endereçamento aberto? � O load factor é ≤1 � Por que? 30 Lidando com Overflow 59 � O que fazer quando o vetor interno da tabela hash ficar cheio? � Duplicar quando estiver cheio? � Duplicar quando atingir uma certa capacidade? Rehashing 60 � Quando a capacidade preenchida (exceder 50%), as operações na tabela passam a demorar mais, pois o número de colisões aumenta � Expandir o array que constitui a tabela, e reorganizar os elementos na nova tabela � Novo tamanho: número primo próximo ao dobro da tabela atual 31 Exemplo 61 Tamanho = 13 34 40 X 11 95 3440 1195 Tamanho = 7 Object put() { ... if (++size > threshold) rehash(); ... } void rehash() { ... newcapacity = prime number near 2*buckets; buckets = new HashEntry[newcapacity]; threshold = (int) (newcapacity * loadFactor); ... } Exercício 62 � Quando devemos fazer o rehashing? � No endereçamento aberto não conseguirmos mais inserir um elemento � Quando metade databela estiver ocupada (limite de capacidade) 32 Implementação 63 � Hashtable � http://www.docjar.com/html/api/java/util/Hashtable.java.html � Ver funções � hash() � O código hash é delegado para cada classe � containsKey() � get() � put() � remove() � rehash() � equals( ) x hashCode( ). � a.equals(b) → hashCode(a) = hashCode(b) Tabela Hash (Implementação) 64 � Como seria representada uma tabela hash em Java? public interface Hashtable<T> { public boolean isEmpty(); public boolean isFull(); public int capacity(); public int size(); public void insert(T element); public void remove(T element) ; public T search(T element); public int indexOf(T element); } 33 Tabela Hash (Implementação) 65 � Separando a tabela de sua função hash? Hashtable HashFunction Tabela Hash (Implementação) 66 � Separando a tabela de sua função hash? Hashtable HashFunction HashFunctionClosedAddress int hash(Object element) HashFunctionOpenAddress int hash(Object element, int probe) HashFunctionDivision HashFunctionMultiplication HashFunctionLinearProbing HashFunctionQuadraticProbing HashFunctionDoubleHashing 34 Tabela Hash (Implementação) 67 � Separando a tabela de sua função hash? Hashtable HashFunction HashFunctionClosedAddress HashFunctionOpenAddress HashFunctionDivision HashFunctionMultiplication HashFunctionLinearProbing HashFunctionQuadraticProbing HashFunctionDoubleHashing HashtableClosedAddress HashtableOpenAddress Referências 68 � Capítulo 12 � 1a edição � Capítulo 11 � 2a edição
Compartilhar