Índices Hash
Arquivo: Mídia:tabelasHash.pdf
O que são índices hash?
Um índice corresponde a um identificador, utilizado para agilizar o processo de busca de informações, reduzindo o custo de acesso a uma informação qualquer. A característica essencial de um índice é seu caráter único, que diz que sua escolha deve corresponder a uma informação única, dentro do conjunto de dados armazenados, que possa servir como referência a esse conjunto.Um exemplo muito comum, quando se trata da ilustração de índices é o CPF, que se trata um número com 11 dígitos, capaz de identificar pessoas físicas maiores de 16 anos. “A ideia central do hash é utilizar uma função aplicada sobre a parte da informação (chave), para retornar o índice onde a informação deve ou deveria estar armazenada”. Sendo assim, uma tabela hash armazenainformações, associando a estas uma chave de pesquisa, podendo ser representada, por exemplo, por vetores e/ou vetores+listas encadeadas. Uma função hash se encarrega por gerar índices e tratar possíveis colisões (endereços de pesquisa iguais, ou já ocupados), distribuindo as informações ao longo da tabela.
Os índices são usados como pontos de entrada para tabelas com otimização de memória. A leitura das linhas de uma tabela requer um índice para localizar os dados na memória. Um índice de hash consiste em uma coleção de buckets organizados em uma matriz. Uma função de hash mapeia chaves de índice para buckets correspondentes no índice de hash.
Indices Hash, são valores de identificação produzidos através da execução de uma operação numérica, denominada função de hashing, em um item de dado. O valor identifica de forma exclusiva o item de dado, mas exige um espaço de armazenamento bem menor. Por isso, o computador pode localizar mais rapidamente os valores de hashing que os itens de dado, que são mais extensos. Uma tabela de hashing associa cada valor a um item de dado exclusivo.
O que são buckets?
Buckets são unidadee de armazenamento que contém um ou mais registros (tipicamente é um bloco do disco).
O que são colisões?
A função de hash é determinística. A mesma chave de índice sempre é mapeada para o mesmo bucket no índice de hash. Várias chaves de índice podem ser mapeadas para o mesmo bucket de hash. Se duas chaves de índice forem mapeadas para o mesmo bucket de hash, haverá uma colisão de hash. Um número grande de colisões
de hash pode afetar o desempenho das operações de leitura. Colisões não são admitidas em sistemas de criptografias, a solução para estas se dá por meio da utilização de funções hash em conjunto com outras estruturas de dados, como as árvores e as listas.
Vantagens
Algoritmos simples e eficientes para inserção, retirada e busca. É muito útil na implementação do operador Junção, que inclu diversas seleções por igualdade. Podemos adequar o tamanho da tabela de hashing ao n esperado em nossa aplicação. Os métodos de hashing, tanto de endereçamento aberto como fechado, podem ser utilizados praticamente sem nenhuma alteração em um ambiente de dados persistentes utilizando arquivos em disco.
Desvantagens
Dependência da escolha de função de hashing. Tempo médio de acesso é ótimo somente em uma faixa. Consumo de espaço em disco, tempo para manutenção e pesquisa. Nenhuma garantia de balanceamento Espaço sub-utilizado nas tabelas. O grau de espalhamento é sensível à função de hashing utilizada e ao tipo de informação usada como chave. Necessita um projeto cuidadoso, pois uma má função pode retornar o mesmo endereço para duas chaves diferentes. Não suporta seleção range (>, <).
Exemplo com Imagem
A estrutura de índice de hash na memória consiste em uma matriz de ponteiros de memória. Cada bucket é mapeado para um deslocamento nesta matriz. Cada bucket na matriz aponta para a primeira linha desse bucket de hash. Cada linha no bucket aponta para a próxima linha, resultando em uma cadeia de linhas para cada bucket de hash, conforme ilustrado na figura a seguir.
Referências bibliográficas