Tabela hash

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (510 palavras )
  • Download(s) : 0
  • Publicado : 28 de maio de 2012
Ler documento completo
Amostra do texto
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 1956numa 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 é comumenteusada 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 deum 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.
AFunçã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 deHashing é 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...
tracking img