ATPS CLASSIFICAÇÃO E PESQUISA

ABELA HASH ou TABELA DE DISPERSÃO

Tabela Hash consiste em um tipo de classificação de dados para o armazenamento de informações. Sua ideia central consiste na divisão de um universo de informações, em subconjuntos de dados mais estruturados, de forma que os subconjuntos da tabela sejam mais fáceis de serem gerenciados.

Esta forma de classificação prioriza a facilidade no armazenamento de informações e na sua busca seja em grande quantidade de dados ou não.

As tabela Hash são constituídas em 2 conceitos:

Tabela Hash ou Tabela de dispersão que consiste basicamente na estrutura que permite o acesso aos subconjuntos em um universo.

Função Hashing que consiste em um algoritmo responsável por fazer o mapeamento de grande quantidade de dados para pequenas quantidades de tamanho fixo. Funções hash também são responsáveis por verificar a integridade de dados em criptografia.

O funcionamento da tabela hash pode ser comparado à construção de um índice de livro, onde temos a divisão de assuntos por capítulos. Caso necessitarmos ir a algum assunto, procuramos o mesmo no índice e logo em seguida vamos à página onde se encontra o assunto.

Sendo a função hashing responsável por fazer o mapeamento ou o resumo das informações, os índices em hash funcionam a partir do resumo gerado pela função hash e a busca da “página do livro” é feito a partir deste resumo gerado e não pelo dado em si. Essa característica da tabela hash pode ser entendida como um grande na inserção e busca de dados estruturados, pois temos um resumo ou índice de onde a informação deveria ou deverá estar, e assim aperfeiçoamos nosso tempo de busca.

a função de hashing pode ser definida como o tradutor de um conjunto de chaves para um conjunto de destinos, ou seja, a função de hashing faz a transformação do valor da chave em uma posição para está chave onde será separado em um subconjunto.

Porém, é necessário ressaltar que uma função de hashing eficiente é capaz de minimizar as colisões e fazer a distribuição dos registros uniformemente pela tabela. Quanto maior a quantidade de registro para a função de hashing, menor a probabilidade de duas chaves apresentarem o mesmo valor na função.Se uma tabela hash for mantida em armazenamento externo num disco ou em outro dispositivo de acesso direto, o tempo, em vez do espaço, será o fator crítico.

A maioria dos sistemas dispõe de armazenamento externo suficiente para permitir-se ao luxo do espaço alocado sem uso para o crescimento, mas não pode suportar o tempo necessário para executar uma operação de E/S para todo elemento numa lista ligada.

Nessa situação, a tabela no armazenamento externo é dividida numa quantidade de blocos chamados buckets. Cada bucket consiste em um segmento físico útil de armazenamento externo, como uma página ou uma trilha de disco ou uma fração de trilha. Geralmente, os buckets são contíguos e podem ser acessados pelos deslocamentos, que servem como valores de espalhamento, quase como os índices de um vetor em armazenamento interno.

Um bucket consiste em um segmento físico útil de armazenamento externo, como uma página ou uma trilha de disco ou uma fração de trilha. Cada bucket da memória externa possui espaço para um número moderado de registros, sendo que um bucket inteiro é lido na memória de imediato e é sequencialmente pesquisado quanto ao registro apropriado. A partir deste conceito podemos analisar a diferença entre uma tabela de espalhamento estática e dinâmica.

TABELA HASH ESTÁTICA

Inicialmente é definido o número de buckets do arquivo, sendo cada um do tamanho de uma página. Os registros são inseridos no bucket determinado pela função de hashing. Se um bucket fica cheio, uma ou mais páginas adicionais podem ser ligadas a ele. Assim páginas adicionais são mantidas em uma lista ligada

Nas tabelas estáticas arquivo pode crescer por excesso ou crescimento regular e é usado um mecanismo para conter os registros em excesso de determinado bucket.

A pesquisa a um registro é feita aplicando a função de hasingh ao valor da chave de pesquisa daquele registro para identificar o bucket onde o registro se encontra. A localização do registro desejado é feita percorrendo todas as páginas do bucket.

A remoção de um registro é feito usando a função de hashing para localizar o bucket onde o registro se encontra. Uma vez localizado, o registro é removido de acordo com a estratégia de remoção sendo adotada.A principal desvantagem desta estratégia é que podem ocorrer páginas adicionais muito grandes nos buckets, o que pode afetar o desempenho do sistema na medida que todas as páginas de um bucket precisam ser pesquisadas.

TABELA HASH DINÂMICA

Um dos grandes problemas no espalhamento para armazenamento em tabela é consiste na sua rigidez. O conteúdo de uma estrutura de armazenamento externo tende a aumentar e diminuir de maneira imprevisível. Ou a tabela usa uma grande quantidade de espaço para acesso eficiente, resultando em muito espaço desperdiçado quando a estrutura encolhe, ou ela usa uma pequena quantidade de espaço e acomoda o crescimento com deficiência, aumentando substancialmente o tempo de acesso para elementos em excesso.

No espalhamento dinâmico caso o índice inteiro for mantido em armazenamento interno, só será necessária uma operação de E/S para localizar um registro, independentemente do crescimento do arquivo. Quando um arquivo diminuir, os buckets poderão ser combinados e liberados, e o tamanho do índice poderá ser reduzido. Sendo assim, esses métodos atingem duas metas simultaneamente: utilização de espaço e acesso eficiente. Ambos os esquemas permitem também o percurso sequencial efetivo dos registros pela ordem das chaves de espalhamento.

Embora o índice possa ser mantido no armazenamento interno assim que o arquivo for aberto, nem sempre isso será possível se o índice se tornar muito grande. Além disso, o índice requer armazenamento externo quando o arquivo não está em uso. Adicionalmente, talvez a cópia externa do índice precise ser sempre atualizada para se proteger contra a falta de energia ou outro tipo de interrupção que impeça a regravação do índice quando o arquivo for fechado.

A tabela hash extensível ou dinâmica usa um arquivo dinâmico de registros que armazena uma tabela, onde cada registro contém um ponteiro para o arquivo. Quando aplicamos a função de hashing nas chaves obtemos um número binário e a partir deste número devemos escolher