·
Ciência da Computação ·
Outros
Send your question to AI and receive an answer instantly
Preview text
CET082 Organização e Recuperação da Informação Arquivos de Acesso Direto Prof Elinaldo Santos de Goes Júnior esgjunioruescbr Arquivos de Acesso Direto Arquivo no qual o acesso ao registro pode ser realizado diretamente sem que ocorra acesso aos registros anteriores Não é necessário que o arquivo esteja ordenado Arquivos de Acesso Direto Basta apenas termos o endereço do registro que queremos acessar O endereço de um determinado registro pode ser dado como um deslocamento em relação ao primeiro registro Endi i1tamanhoregistro Arquivos de Acesso Direto Tamanho do Registro idConta 4B CodAgencia 4B CodConta 4B NomeCliente 30B dataNasc 10B Total 52B Arquivos de Acesso Direto Reg4 4152 156 Arquivos de Acesso Direto Operações normalmente não são conduzidas pelo posição do registro mas pelo valor de chave do registro No exemplo queremos ler o registro 09 e não o registro na posição 04 Arquivos de Acesso Direto Como saber em que endereço um registro se encontra com uma determinada chave Indexação Estruturas de dados auxiliares Cálculos a partir do valor da chave hashing Tabelas hash Também conhecidas como tabelas de dispersão ou espalhamento São estruturas de dados que combinam uma tabela a uma função hash Tabelas hash Uma tabela hash para um certo tipo de chave consiste de uma função hash h um array chamado de tabela de tamanho N Ao implementar um mapa com uma tabela hash o objetivo é armazenar o item kv no índice i hk Tabelas hash Uma função hash h mapeia chaves de algum tipo para inteiros num intervalo fixo tipicamente 0 N1 onde N número de chaves Ex hk k mod N é uma função hash para chaves inteiras O inteiro hk é o valor hash da chave k Tabelas hash Ao invés de organizar os registros de um arquivo em função do valor de cada chave em relação às demais levase em conta somente o seu valor absoluto interpretado como um valor numérico Ou seja a chave é transformada num endereço de uma tabela 12 Tabelas hash Ex Tabela hash para um mapa contendo entradas CPF Nome onde CPF é um inteiro positivo com 11 dígitos Essa tabela hash usa um array de tamanho N 10000 a função hash hx últimos 4 dígitos de x 0 1 2 3 4 9997 9998 9999 29466150004 25740980002 24706429998 32576590001 Tabelas hash Ex hx x mod 5 Tabelas hash Normalmente uma função hash é especificada como a composição de duas funções código hash transforma a chave em um inteiro que possa ser convertido em um índice da tabela h1 chaves inteiros função de compressão transforma o int produzido pelo código hash em um índice da tabela h2 inteiros 0 N1 O código hash é aplicado primeiro e a função de compressão é então aplicada ao resultado hx h2h1x Tabelas hash Infelizmente a função hash não garante injetividade x y e hx hy Tabelas hash Se ao tentar inserir a chave x o compartimento de endereço hy estiver ocupado pelo chave y ocorrerá colisão Neste caso as chaves x e y são sinônimas em relação a h Tabelas hash Objetivo da função hash é espalhar ou dispersar as chaves adequadamente Produzir um número baixo de colisões Ser facilmente computável Ser uniforme Tabelas hash Produzir um número baixo de colisões É difícil pois depende da distribuição das chaves Ex A chave de um pedido de compra é composto pelo dia mês e ano do pedido O que acarreta em muitos elementos comuns nas chaves 25022015 27022015 Se a função h escolhida realçar estes elementos muitas colisões irão ocorrer Tabelas hash Ser facilmente computável Se a tabela é armazenada em memória secundária o tempo de cálculo não é um fator crítico A operação de IO dilui o tempo de cálculo É a condição mais fácil de ser atingida Tabelas hash Ser uniforme Significa que a função h deve ser tal que todos os compartimentos possuam a mesma chance de serem escolhidos Ou seja a probabilidade de que hx seja igual ao endereço base k deve ser 1n para todas as chaves x e todos os endereços k є 0 n1 Na prática é muito difícil de ser testada pois em geral a distribuição é desconhecida Tabelas hash Algumas funções são bastante empregadas na prática Método da divisão Método da Multiplicação Tabelas hash Método da divisão Uso da função mod hx x mod m m é a dimensão da tabela O resto da divisão de x por m é utilizado como endereço base Tabelas hash Método da divisão Alguns valores de m são melhores do que outros Se m for par hx será par quando x for par e ímpar quando x for ímpar O que é indesejável Estudos apontam bons resultados práticos para valores de m que Seja um número primo não próximo a potência de 2 Ou escolher m tal que não possua divisores primos menores que 20 Tabelas hash Método MAD Multiplique Adicione e Divida Fazer uso de outras operações para encontrar o índice hx ax b mod N a e b são inteiros 0 tais que a mod N 0 caso contrário todo inteiro mapearia para o mesmo valor b Tabelas hash Colisões Uma colisão ocorre quando objetos diferentes são mapeados para a mesma célula ou seja quando a função hash produz o mesmo resultado para duas ou mais chaves distintas no exemplo do mapa CPF NOME h29466150004 4 h31070380004 4 Tabelas hash Fator de carga Definese como fator de carga de uma tabela hash o valor α nm n é o número de registros armazenados na tabela m é tamanho da tabela Tabelas hash O número de colisões aumenta quando o fator de carga aumenta Diminuir o fator de carga leva a diminuição das colisões Ainda assim as colisões podem ocorrer Duas estratégias para lidar com colisões encadeamento separado endereçamento aberto Tabelas hash Encadeamento separado Consiste em manter m listas encadeadas uma para cada possível endereço base A tabela não possui nenhum registro apenas os ponteiros para as listas encadeadas Cada nó da lista encadeada contém Um registro Um ponteiro para o próximo nó Tabelas hash Encadeamento separado Ex Tabela de CPFs 31070380004 0 1 2 3 4 29466150004 25740980002 32576590001 Tabelas hash Encadeamento separado Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 31 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 36 36 mod 13 10 32 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 41 36 36 mod 13 10 41 mod 13 2 33 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 41 36 90 36 mod 13 10 41 mod 13 2 90 mod 13 12 34 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 18 41 36 90 36 mod 13 10 41 mod 13 2 90 mod 13 12 18 mod 13 5 35 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 18 36 90 28 mod 13 2 36 mod 13 10 41 mod 13 2 90 mod 13 12 18 mod 13 5 41 41 28 36 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 18 41 28 36 12 mod 13 12 28 mod 13 2 36 mod 13 10 41 mod 13 2 90 mod 13 12 18 mod 13 5 90 90 12 37 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 18 12 90 41 28 10 mod 13 10 12 mod 13 12 28 mod 13 2 36 mod 13 10 41 mod 13 2 90 mod 13 12 18 mod 13 5 36 36 10 38 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 18 36 10 12 90 54 mod 13 2 10 mod 13 10 12 mod 13 12 28 mod 13 2 36 mod 13 10 41 mod 13 2 90 mod 13 12 18 mod 13 5 41 28 41 28 54 39 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 41 18 36 28 54 10 38 mod 13 12 54 mod 13 2 10 mod 13 10 12 mod 13 12 28 mod 13 2 36 mod 13 10 41 mod 13 2 90 mod 13 12 18 mod 13 5 12 90 12 90 38 40 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 41 18 36 28 54 10 25 mod 13 12 38 mod 13 12 54 mod 13 2 10 mod 13 10 12 mod 13 12 28 mod 13 2 36 mod 13 10 41 mod 13 2 90 mod 13 12 18 mod 13 5 38 12 90 90 38 12 25 Tabelas hash Encadeamento separado Busca por um registro de chave x Calcular o endereço aplicando a função hx Percorrer a lista encadeada associada ao endereço Comparar a chave de cada nó da lista encadeada com a chave x até encontrar o nó desejado Se ao final da lista o valor não for encontrado o registro não está lá Tabelas hash Encadeamento separado Inserção de um registro de chave x Calcular o endereço aplicando a função hx Buscar o registro na lista associada ao endereço hx Se o registro for encontrado apresentar erro Se o registro não for encontrado inserir no final da lista Tabelas hash Encadeamento separado Exclusão de um registro de chave x Calcular o endereço aplicando a função hx Buscar o registro na lista associada ao endereço hx Se o registro for encontrado excluir Se o registro não for encontrado apresentar erro Tabelas hash Encadeamento separado Busca no pior caso É necessário percorrer a lista encadeada até o final para concluir que a chave não está na tabela Tabelas hash Encadeamento separado O gerenciamento das colisões é delegado a um mapa baseado em lista em cada célula Vantagens Implementação simples Execução rápida Desvantagem Consumo maior de memória devido às estruturas de dados auxiliares Tabelas hash Endereçamento Todos os itens são armazenados na própria tabela havendo ou não colisões Ao tentar inserir um item em uma posição já ocupada tentase em outras posições Tabelas hash Endereçamento Vantagem uso econômico de memória Desvantagens implementação mais complexa requer cuidados para evitar clustering agrupamento que prejudica a eficiência da tabela Tabelas hash Endereçamento por zona Neste método a tabela hash T é dividida em duas zonas Uma de endereço base de tamanho p E uma de sinônimos de tamanho s Assim m p s Sendo os valores de p e s fixos Tabelas hash Endereçamento por zona Nesse caso a função de dispersão deve obter endereços base na faixa 0 p1 E assim α nm 1 Tabelas hash Endereçamento Dois campos são necessariamente obrigatórios O primeiro armazena a chave O segundo contém o ponteiro que indica o próximo elemento na lista de sinônimos Tabelas hash Endereçamento por zona N 5 m 7 p 4 s 3 hx x mod 4 Tabelas hash Endereçamento por zona Num dado momento pode ocorrer de não haver mais espaços para inserir um novo registro na região reservada às colisões Um nova inclusão provocará a condição de overflow Aumentar a zona de colisões diminuindo a zona de endereços base diminui a possibilidade de overflow Tabelas hash Endereçamento aberto Outra solução é não utilizar zonas nesse caso qualquer endereço da tabela é de base ou colisão Neste caso pode ocorrer colisões secundárias Provenientes da coincidência de endereços para chaves que não são sinônimas Tabelas hash Endereçamento aberto Assim quando ocorre uma colisão a nova chave é inserida no primeiro espaço vazio A partir do compartimento onde ocorreu a colisão ou Do final da tabela Tabelas hash Endereçamento aberto Encontrar novos espaços não ocupados Quando ocorrer uma colisão calculase o novo endereço para o compartimento até que se encontre o compartimento vazio A busca terminará somente ao encontrar um endereço vazio ou até a exaustão da tabela Tabelas hash Endereçamento aberto Principais estratégias para resolver colisões com endereçamento aberto teste linear teste quadrático hash duplo Tabelas hash Endereçamento aberto Linear hkv hk i M Quadrático hkv hk i² M Duplo hkv hk ihk M Tabelas hash Endereçamento aberto Teste linear Colocamos o item que colide na próxima célula livre de maneira circular Ai Ai1 mod N Ai2 mod N onde i hk Cada inspeção de célula é chamada de teste Tabelas hash Endereçamento aberto Teste linear Suponha que o endereço base de uma chave x seja hx Suponha agora uma outra chave x ocupando o mesmo endereço de hx Assim tentamos armazenar x no endereço consecutivo a hx1 Caso esteja ocupado tentase o próximo hx2 e assim sucessivamente Tabelas hash Endereçamento aberto Teste linear Itens que colidem acabam agrupados Formação de clusters ou agrupamentos Colisões aumentam a sequência de testes Diminui o desempenho de todas as operações sobre a tabela hash Agrupamentos podem fundirse Perda de desempenho ainda mais severa 63 Tabelas hash Ex hk k mod N N13 insira as chaves 18 41 22 44 59 32 31 73 18 mod 13 5 Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø 41 mod 13 2 22 mod 13 9 44 mod 13 5 59 mod 13 7 32 mod 13 6 31 mod 13 5 73 mod 13 8 0 1 2 3 4 5 6 7 8 9 10 11 12 1 8 41 4 4 5 9 3 2 2 2 3 1 7 3 Total de testes 12345678910 11 12 13 14 15 16 17 18 19 Tabelas hash Endereçamento aberto Teste quadrático A proposta é reduzir os agrupamentos primários uma vez que aumentam o tempo de busca Assim deve ser obtido sequências de endereços para endereços base próximos porém diferentes Utilizase uma função de incremento quadrática Tabelas hash Endereçamento aberto Teste quadrático Colocamos o item que colide na primeira célula livre de uma série lista de possibilidades a distância entre as células nessa lista cresce em proporção geométrica Aif j mod N para j 0 1 2 onde f j j² ou seja Ai Ai1 mod N Ai4 mod N Ai9 mod N Ai16 mod N Tabelas hash Endereçamento aberto Teste quadrático Vantagem Minimiza o problema de agrupamento que ocorre no teste linear Desvantagens Cria seu próprio padrão de agrupamento Agrupamento secundário O conjunto de células ocupadas salta no array de maneira predeterminada Pode não achar célula livre mesmo que exista se N não for primo ou O array estiver com mais de 50 de ocupação Tabelas hash Endereçamento aberto Hash duplo Usa uma função de hash secundária hk e resolve colisões colocando um item na primeira célula livre na série i jhk mod N para j 0 1 N 1 a função de hash secundária hk não pode gerar zero Tabelas hash Endereçamento aberto Hash duplo Na dispersão dupla é utilizada duas funções de hash hk e hk Assim hk v hk ihk mod m O método distribui melhor as chaves do que os métodos anteriores Tabelas hash Endereçamento aberto Hash duplo Nos métodos anteriores se hk1 hk2 para k1 e k2 distintos ocorrerá as mesmas sequências de tentativas concentrando chaves em certas regiões da tabela Para isso ocorrer na dispersão dupla hk1 hk2 e hk1 hk2 Tabelas hash Endereçamento aberto Hash duplo hk v hk ihk mod m m 7 hk k mod m hk 1 k mod 5 Tabelas hash Endereçamento aberto Hash duplo hk v hk ihk mod m m 7 hk k mod m hk 1 k mod 5
Send your question to AI and receive an answer instantly
Preview text
CET082 Organização e Recuperação da Informação Arquivos de Acesso Direto Prof Elinaldo Santos de Goes Júnior esgjunioruescbr Arquivos de Acesso Direto Arquivo no qual o acesso ao registro pode ser realizado diretamente sem que ocorra acesso aos registros anteriores Não é necessário que o arquivo esteja ordenado Arquivos de Acesso Direto Basta apenas termos o endereço do registro que queremos acessar O endereço de um determinado registro pode ser dado como um deslocamento em relação ao primeiro registro Endi i1tamanhoregistro Arquivos de Acesso Direto Tamanho do Registro idConta 4B CodAgencia 4B CodConta 4B NomeCliente 30B dataNasc 10B Total 52B Arquivos de Acesso Direto Reg4 4152 156 Arquivos de Acesso Direto Operações normalmente não são conduzidas pelo posição do registro mas pelo valor de chave do registro No exemplo queremos ler o registro 09 e não o registro na posição 04 Arquivos de Acesso Direto Como saber em que endereço um registro se encontra com uma determinada chave Indexação Estruturas de dados auxiliares Cálculos a partir do valor da chave hashing Tabelas hash Também conhecidas como tabelas de dispersão ou espalhamento São estruturas de dados que combinam uma tabela a uma função hash Tabelas hash Uma tabela hash para um certo tipo de chave consiste de uma função hash h um array chamado de tabela de tamanho N Ao implementar um mapa com uma tabela hash o objetivo é armazenar o item kv no índice i hk Tabelas hash Uma função hash h mapeia chaves de algum tipo para inteiros num intervalo fixo tipicamente 0 N1 onde N número de chaves Ex hk k mod N é uma função hash para chaves inteiras O inteiro hk é o valor hash da chave k Tabelas hash Ao invés de organizar os registros de um arquivo em função do valor de cada chave em relação às demais levase em conta somente o seu valor absoluto interpretado como um valor numérico Ou seja a chave é transformada num endereço de uma tabela 12 Tabelas hash Ex Tabela hash para um mapa contendo entradas CPF Nome onde CPF é um inteiro positivo com 11 dígitos Essa tabela hash usa um array de tamanho N 10000 a função hash hx últimos 4 dígitos de x 0 1 2 3 4 9997 9998 9999 29466150004 25740980002 24706429998 32576590001 Tabelas hash Ex hx x mod 5 Tabelas hash Normalmente uma função hash é especificada como a composição de duas funções código hash transforma a chave em um inteiro que possa ser convertido em um índice da tabela h1 chaves inteiros função de compressão transforma o int produzido pelo código hash em um índice da tabela h2 inteiros 0 N1 O código hash é aplicado primeiro e a função de compressão é então aplicada ao resultado hx h2h1x Tabelas hash Infelizmente a função hash não garante injetividade x y e hx hy Tabelas hash Se ao tentar inserir a chave x o compartimento de endereço hy estiver ocupado pelo chave y ocorrerá colisão Neste caso as chaves x e y são sinônimas em relação a h Tabelas hash Objetivo da função hash é espalhar ou dispersar as chaves adequadamente Produzir um número baixo de colisões Ser facilmente computável Ser uniforme Tabelas hash Produzir um número baixo de colisões É difícil pois depende da distribuição das chaves Ex A chave de um pedido de compra é composto pelo dia mês e ano do pedido O que acarreta em muitos elementos comuns nas chaves 25022015 27022015 Se a função h escolhida realçar estes elementos muitas colisões irão ocorrer Tabelas hash Ser facilmente computável Se a tabela é armazenada em memória secundária o tempo de cálculo não é um fator crítico A operação de IO dilui o tempo de cálculo É a condição mais fácil de ser atingida Tabelas hash Ser uniforme Significa que a função h deve ser tal que todos os compartimentos possuam a mesma chance de serem escolhidos Ou seja a probabilidade de que hx seja igual ao endereço base k deve ser 1n para todas as chaves x e todos os endereços k є 0 n1 Na prática é muito difícil de ser testada pois em geral a distribuição é desconhecida Tabelas hash Algumas funções são bastante empregadas na prática Método da divisão Método da Multiplicação Tabelas hash Método da divisão Uso da função mod hx x mod m m é a dimensão da tabela O resto da divisão de x por m é utilizado como endereço base Tabelas hash Método da divisão Alguns valores de m são melhores do que outros Se m for par hx será par quando x for par e ímpar quando x for ímpar O que é indesejável Estudos apontam bons resultados práticos para valores de m que Seja um número primo não próximo a potência de 2 Ou escolher m tal que não possua divisores primos menores que 20 Tabelas hash Método MAD Multiplique Adicione e Divida Fazer uso de outras operações para encontrar o índice hx ax b mod N a e b são inteiros 0 tais que a mod N 0 caso contrário todo inteiro mapearia para o mesmo valor b Tabelas hash Colisões Uma colisão ocorre quando objetos diferentes são mapeados para a mesma célula ou seja quando a função hash produz o mesmo resultado para duas ou mais chaves distintas no exemplo do mapa CPF NOME h29466150004 4 h31070380004 4 Tabelas hash Fator de carga Definese como fator de carga de uma tabela hash o valor α nm n é o número de registros armazenados na tabela m é tamanho da tabela Tabelas hash O número de colisões aumenta quando o fator de carga aumenta Diminuir o fator de carga leva a diminuição das colisões Ainda assim as colisões podem ocorrer Duas estratégias para lidar com colisões encadeamento separado endereçamento aberto Tabelas hash Encadeamento separado Consiste em manter m listas encadeadas uma para cada possível endereço base A tabela não possui nenhum registro apenas os ponteiros para as listas encadeadas Cada nó da lista encadeada contém Um registro Um ponteiro para o próximo nó Tabelas hash Encadeamento separado Ex Tabela de CPFs 31070380004 0 1 2 3 4 29466150004 25740980002 32576590001 Tabelas hash Encadeamento separado Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 31 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 36 36 mod 13 10 32 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 41 36 36 mod 13 10 41 mod 13 2 33 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 41 36 90 36 mod 13 10 41 mod 13 2 90 mod 13 12 34 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 18 41 36 90 36 mod 13 10 41 mod 13 2 90 mod 13 12 18 mod 13 5 35 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 18 36 90 28 mod 13 2 36 mod 13 10 41 mod 13 2 90 mod 13 12 18 mod 13 5 41 41 28 36 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 18 41 28 36 12 mod 13 12 28 mod 13 2 36 mod 13 10 41 mod 13 2 90 mod 13 12 18 mod 13 5 90 90 12 37 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 18 12 90 41 28 10 mod 13 10 12 mod 13 12 28 mod 13 2 36 mod 13 10 41 mod 13 2 90 mod 13 12 18 mod 13 5 36 36 10 38 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 18 36 10 12 90 54 mod 13 2 10 mod 13 10 12 mod 13 12 28 mod 13 2 36 mod 13 10 41 mod 13 2 90 mod 13 12 18 mod 13 5 41 28 41 28 54 39 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 41 18 36 28 54 10 38 mod 13 12 54 mod 13 2 10 mod 13 10 12 mod 13 12 28 mod 13 2 36 mod 13 10 41 mod 13 2 90 mod 13 12 18 mod 13 5 12 90 12 90 38 40 Tabelas hash Ex hk k mod N N13 insira as chaves 36 41 90 18 28 12 10 54 38 25 0 1 2 3 4 5 6 7 8 9 10 11 12 41 18 36 28 54 10 25 mod 13 12 38 mod 13 12 54 mod 13 2 10 mod 13 10 12 mod 13 12 28 mod 13 2 36 mod 13 10 41 mod 13 2 90 mod 13 12 18 mod 13 5 38 12 90 90 38 12 25 Tabelas hash Encadeamento separado Busca por um registro de chave x Calcular o endereço aplicando a função hx Percorrer a lista encadeada associada ao endereço Comparar a chave de cada nó da lista encadeada com a chave x até encontrar o nó desejado Se ao final da lista o valor não for encontrado o registro não está lá Tabelas hash Encadeamento separado Inserção de um registro de chave x Calcular o endereço aplicando a função hx Buscar o registro na lista associada ao endereço hx Se o registro for encontrado apresentar erro Se o registro não for encontrado inserir no final da lista Tabelas hash Encadeamento separado Exclusão de um registro de chave x Calcular o endereço aplicando a função hx Buscar o registro na lista associada ao endereço hx Se o registro for encontrado excluir Se o registro não for encontrado apresentar erro Tabelas hash Encadeamento separado Busca no pior caso É necessário percorrer a lista encadeada até o final para concluir que a chave não está na tabela Tabelas hash Encadeamento separado O gerenciamento das colisões é delegado a um mapa baseado em lista em cada célula Vantagens Implementação simples Execução rápida Desvantagem Consumo maior de memória devido às estruturas de dados auxiliares Tabelas hash Endereçamento Todos os itens são armazenados na própria tabela havendo ou não colisões Ao tentar inserir um item em uma posição já ocupada tentase em outras posições Tabelas hash Endereçamento Vantagem uso econômico de memória Desvantagens implementação mais complexa requer cuidados para evitar clustering agrupamento que prejudica a eficiência da tabela Tabelas hash Endereçamento por zona Neste método a tabela hash T é dividida em duas zonas Uma de endereço base de tamanho p E uma de sinônimos de tamanho s Assim m p s Sendo os valores de p e s fixos Tabelas hash Endereçamento por zona Nesse caso a função de dispersão deve obter endereços base na faixa 0 p1 E assim α nm 1 Tabelas hash Endereçamento Dois campos são necessariamente obrigatórios O primeiro armazena a chave O segundo contém o ponteiro que indica o próximo elemento na lista de sinônimos Tabelas hash Endereçamento por zona N 5 m 7 p 4 s 3 hx x mod 4 Tabelas hash Endereçamento por zona Num dado momento pode ocorrer de não haver mais espaços para inserir um novo registro na região reservada às colisões Um nova inclusão provocará a condição de overflow Aumentar a zona de colisões diminuindo a zona de endereços base diminui a possibilidade de overflow Tabelas hash Endereçamento aberto Outra solução é não utilizar zonas nesse caso qualquer endereço da tabela é de base ou colisão Neste caso pode ocorrer colisões secundárias Provenientes da coincidência de endereços para chaves que não são sinônimas Tabelas hash Endereçamento aberto Assim quando ocorre uma colisão a nova chave é inserida no primeiro espaço vazio A partir do compartimento onde ocorreu a colisão ou Do final da tabela Tabelas hash Endereçamento aberto Encontrar novos espaços não ocupados Quando ocorrer uma colisão calculase o novo endereço para o compartimento até que se encontre o compartimento vazio A busca terminará somente ao encontrar um endereço vazio ou até a exaustão da tabela Tabelas hash Endereçamento aberto Principais estratégias para resolver colisões com endereçamento aberto teste linear teste quadrático hash duplo Tabelas hash Endereçamento aberto Linear hkv hk i M Quadrático hkv hk i² M Duplo hkv hk ihk M Tabelas hash Endereçamento aberto Teste linear Colocamos o item que colide na próxima célula livre de maneira circular Ai Ai1 mod N Ai2 mod N onde i hk Cada inspeção de célula é chamada de teste Tabelas hash Endereçamento aberto Teste linear Suponha que o endereço base de uma chave x seja hx Suponha agora uma outra chave x ocupando o mesmo endereço de hx Assim tentamos armazenar x no endereço consecutivo a hx1 Caso esteja ocupado tentase o próximo hx2 e assim sucessivamente Tabelas hash Endereçamento aberto Teste linear Itens que colidem acabam agrupados Formação de clusters ou agrupamentos Colisões aumentam a sequência de testes Diminui o desempenho de todas as operações sobre a tabela hash Agrupamentos podem fundirse Perda de desempenho ainda mais severa 63 Tabelas hash Ex hk k mod N N13 insira as chaves 18 41 22 44 59 32 31 73 18 mod 13 5 Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø 41 mod 13 2 22 mod 13 9 44 mod 13 5 59 mod 13 7 32 mod 13 6 31 mod 13 5 73 mod 13 8 0 1 2 3 4 5 6 7 8 9 10 11 12 1 8 41 4 4 5 9 3 2 2 2 3 1 7 3 Total de testes 12345678910 11 12 13 14 15 16 17 18 19 Tabelas hash Endereçamento aberto Teste quadrático A proposta é reduzir os agrupamentos primários uma vez que aumentam o tempo de busca Assim deve ser obtido sequências de endereços para endereços base próximos porém diferentes Utilizase uma função de incremento quadrática Tabelas hash Endereçamento aberto Teste quadrático Colocamos o item que colide na primeira célula livre de uma série lista de possibilidades a distância entre as células nessa lista cresce em proporção geométrica Aif j mod N para j 0 1 2 onde f j j² ou seja Ai Ai1 mod N Ai4 mod N Ai9 mod N Ai16 mod N Tabelas hash Endereçamento aberto Teste quadrático Vantagem Minimiza o problema de agrupamento que ocorre no teste linear Desvantagens Cria seu próprio padrão de agrupamento Agrupamento secundário O conjunto de células ocupadas salta no array de maneira predeterminada Pode não achar célula livre mesmo que exista se N não for primo ou O array estiver com mais de 50 de ocupação Tabelas hash Endereçamento aberto Hash duplo Usa uma função de hash secundária hk e resolve colisões colocando um item na primeira célula livre na série i jhk mod N para j 0 1 N 1 a função de hash secundária hk não pode gerar zero Tabelas hash Endereçamento aberto Hash duplo Na dispersão dupla é utilizada duas funções de hash hk e hk Assim hk v hk ihk mod m O método distribui melhor as chaves do que os métodos anteriores Tabelas hash Endereçamento aberto Hash duplo Nos métodos anteriores se hk1 hk2 para k1 e k2 distintos ocorrerá as mesmas sequências de tentativas concentrando chaves em certas regiões da tabela Para isso ocorrer na dispersão dupla hk1 hk2 e hk1 hk2 Tabelas hash Endereçamento aberto Hash duplo hk v hk ihk mod m m 7 hk k mod m hk 1 k mod 5 Tabelas hash Endereçamento aberto Hash duplo hk v hk ihk mod m m 7 hk k mod m hk 1 k mod 5