Tabela hash

TABELA HASH
Idéia Geral: A primeira referência a Hash foi feita em 1953 por pesquisadores da IBM que estavam construindo um compilador. O primeiro artigo sobre hashing foi publicado em 1956 numa revista Americana. É uma estrutura de dados onde as posições de inserção e busca são calculadas através de uma função que visa distribuir os elementos aleatoriamente ao longo de um vetor. O universo contém muitos elementos e muitas vezes o número de chaves a serem inseridas é muito menor que o universo, nestes casos não faz sentido ter uma posição para cada elemento do universo.

• Exemplo:

Tabelas de Endereçamento Direto (lookup-tables) Tabelas de HASH

O tempo esperado de para a inserção, remoção e pesquisa é O(1). Esta tabela é comumente usada em situações onde precisa-se apenas de operações inserir, buscar e remover. Não se pode, por exemplo, fazer caminhamento ordenado.

Funcionamento: Uma tabela hash é construída através de um vetor de tamanho n, no qual se armazenam as informações. Nele, a localização de cada informação é dada a partir do cálculo de um índice através de uma função de indexação, a função hash. A Função de Hashing é a responsável por gerar um índice a partir de uma determinada chave. O ideal é que a função forneça índices únicos para o conjunto das chaves de entrada possíveis. A função de Hashing é extremamente importante, pois ela é responsável por distribuir as informações pela Tabela Hash. A implementação da função de Hashing tem influência direta na eficiência das operações sobre o Hash.

O elemento com chave k é armazenado na posição h(k), onde h é a função de espalhamento. Se a função h der o mesmo resultado, para duas chaves então temos uma colisão. • Exemplo: [pic]
Escolha da Função Hash:

1. Transformamos qualquer chave em um número natural 2. Depois calculamos a posição a ser inserida transformando o número natural em uma das posições