TÉCNICAS DE PROGRAMAÇÃO Pratique e Compartilhe 3

Prévia do material em texto

TÉCNICAS DE PROGRAMAÇÃO – Pratique e Compartilhe 3
ALOCAÇÃO DINÂMICA – TABELA HASH
Nesta unidade, conversamos sobre o processo de alocação dinâmica de memória. Através desta técnica, é possível desenvolver um programa mais eficiente em relação ao gerenciamento de memória, de modo a torná-lo escalável. Com a escalabilidade, consegue-se adaptar o programa a real demanda, inerente ao volume de dados a ser manipulado.
A utilização da alocação dinâmica permite a implementação de sistemas computacionais mais complexos e mais eficientes, no que se refere a manipulação das informações. Existem várias estratégias para o armazenamento das informações usando alocação dinâmica, que facilitam, por exemplo, o processo de inserção e busca de dados. Uma das técnicas é a chamada tabela hash, também chamada de tabela de dispersão.
O uso da hash pode ser encontrado em diversas áreas, tais como: memória cache, memória virtual dos sistemas operacionais, protocolos DHCP em redes de computadores e sistema de bancos de dados. Caso queira saber mais sobre a tabela hash, você poderá encontrar neste link uma descrição sumária desta.
Referências
ASCENCIO, A. F. G. Fundamentos de Programação de Computadores: Algoritmos, PASCAL, C/C++ (Padrão ANSI) e Java. 3. ed. São Paulo: Pearson Education do Brasil, 2012. Disponível em: <https://laureatebrasil.blackboard.com/>. Acesso em: 29/06/2019.
DEITEL, P. J.; DEITEL, H. C: Como Programar. 6. ed. São Paulo: Pearson Prentice Hall, 2011. Disponível em: <https://laureatebrasil.blackboard.com/>. Acesso em: 29/06/2019.
PISA, P. O que é Hash? Techtudo, 2012. Disponível em: <https://www.techtudo.com.br/artigos/noticia/2012/07/o-que-e-hash.html>. Acesso em: 09/07/2019.
PUGA, S.; RISSETTI, G. Lógica de Programação e Estruturas de Dados – com Aplicações em Java. 3 ed. São Paulo: Pearson Education do Brasil, 2016. Disponível em: <https://laureatebrasil.blackboard.com/>. Acesso em: 29/06/2019.
Vamos praticar
Após ler o texto a respeito da tabela hash, faça uma reflexão sobre o emprego de alocação dinâmica, respondendo as questões a seguir:
1. Aonde poderemos adotar a alocação dinâmica na tabela hash?
2. Pense em um caso no qual poderíamos utilizar a tabela hash e descreva as estruturas de dados a serem utilizadas.
3. Com base na questão 2, usando uma linha de código, como poderemos acessar um campo de uma informação armazenada na tabela hash, sabendo que já temos, em mãos, o resultado da função hash aplicado sobre o identificador da informação? Para essa questão, indique apenas o caminho dos campos do vetor e registro até se chegar à informação requerida.
Tomando por base essas três questões, com o objetivo de visualizarmos diferentes exemplos de uso de alocação dinâmica, assim como identificarmos outras formas de manipular as estruturas alocadas dinamicamente; faça comentários, interagindo nas postagens de seus colegas. Não se esqueça de disponibilizar suas conclusões no fórum da seção “Compartilhe”.
Uma tabela de dispersão (também conhecida por tabela de espalhamento ou tabela hash) é uma estrutura de dados especial, que associa chaves de pesquisa a valores. Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado.
Tabelas de dispersão são tipicamente utilizadas para implementar vetores associativos, conjuntos e caches. São tipicamente usadas para indexação de grandes volumes de informação (como bases de dados). A implementação típica busca uma função de dispersão que seja de complexidade O(1), não importando o número de registros na tabela (desconsiderando colisões). O ganho com relação a outras estruturas associativas (como um vetor simples) passa a ser maior conforme a quantidade de dados aumenta. Outros exemplos de uso das tabelas de dispersão são as tabelas de transposição em jogos de xadrez para computador até mesmo em serviços de DHCP.
A função de espalhamento ou função de dispersão é a responsável por gerar um índice a partir de determinada chave. Caso a função seja mal escolhida, toda a tabela terá um mau desempenho.
O ideal para a função de espalhamento é que sejam sempre fornecidos índices únicos para as chaves de entrada. A função perfeita seria a que, para quaisquer entradas A e B, sendo A diferente de B, fornecesse saídas diferentes. Quando as entradas A e B são diferentes e, passando pela função de espalhamento, geram a mesma saída, acontece o que chamamos de colisão.
Na prática, funções de espalhamento perfeitas ou quase perfeitas são encontradas apenas onde a colisão é intolerável (por exemplo, nas funções de dispersão da criptografia), ou quando conhecemos previamente o conteúdo da tabela armazenada. Nas tabelas de dispersão comuns a colisão é apenas indesejável, diminuindo o desempenho do sistema. Muitos programas funcionam sem que seu responsável suspeite que a função de espalhamento seja ruim e esteja atrapalhando o desempenho.
Por causa das colisões, muitas tabelas de dispersão são aliadas com alguma outra estrutura de dados, tal como uma lista encadeada ou até mesmo com árvores balanceadas. Em outras oportunidades a colisão é solucionada dentro da própria tabela.
Tipos
Método da divisão (método da congruência linear)
· Potências de dois devem ser evitadas para valores de m.
· m deve ser um número primo distante de pequenas potências de dois (m grande).
Exemplo:
(m é o tamanho da tabela)
Método da multiplicação (método da congruência linear multiplicativo)
· m normalmente é uma potência de dois.
· A é uma constante, tal que 0 < A < 1.
· Extrair a parte fracionária de kA, ou seja, kA (mod 1).
· Utilizar o piso do resultado.
Exemplo:
Exemplo de função de espalhamento e colisão
Imagine que seja necessário utilizar uma tabela de dispersão para otimizarmos uma busca de nomes de uma lista telefônica (dado o nome, temos que obter o endereço e o telefone). Nesse caso, poderíamos armazenar toda a lista telefônica em um vetor e criar uma função de espalhamento que funcionasse de acordo com o seguinte critério. Para cada nome começado com a letra A, devolver 0. Para cada nome começado com a letra B, devolver 1, e assim por diante. Por fim, para cada nome começado com a letra Z, devolver 25 (Alfabeto com 26 letras).
O exemplo anterior poderia ser implementado, em C, da seguinte forma:
Agora inserimos alguns nomes em nossa lista telefônica:
José da Silva; Rua das Almas, 35; Telefone (31) 3888-9999
Ricardo Souza; Rua dos Coqueiros, 54; Telefone (31) 3222-4444
Orlando Nogueira; Rua das Oliveiras, 125; Telefone (31) 3444-5555
Nossa função distribuiria os nomes assim:
Agora inserimos mais um nome:
Renato Porto; Rua dos Elefantes, 687; Telefone (31) 3333-5555
E temos uma colisão:
Verifica-se que, com a função hashExemplo, a ocorrência de colisões ocorre assim que uma nova entrada na lista telefônica, com um nome iniciando-se pela letra R, for adicionada. Tem-se então uma colisão com a letra R. Outro exemplo, se for adicionado "João Siqueira", a entrada estaria em conflito com o "José da Silva".