Hash

Disponível somente no TrabalhosFeitos
  • Páginas : 9 (2159 palavras )
  • Download(s) : 0
  • Publicado : 4 de outubro de 2011
Ler documento completo
Amostra do texto
Estruturas de Dados Capítulo 13: Tabelas Hash
13.1. Introdução Uma maneira de organizar dados, que apresenta bons resultados na prática, é conhecida como hashing1, e se baseia na idéia de distribuir os dados em posições aleatórias de uma tabela. Podemos apresentar esta idéia através de um exemplo. Suponhamos que desejamos organizar o cadastro de aproximadamente 500 empregados de uma empresausando para identificar cada empregado o seu CPF2. Por exemplo, a informação sobre cada empregado pode ser guardada em um registro INFO:
typedef struct info INFO, *PT; struct info{ int cpf; char nome[80]; char ender[120]; ... };

Como os CPFs variam entre 000 000 000 e 999 999 999, ignorando-se os “dígitos verificadores”, podemos guardar toda a informação em um vetor
INFO vet[1000000000];

oupara economizar algum espaço, em posições apontadas por componentes do vetor
PT vet[1000000000];

(A economia de espaço viria do fato de que INFO* ocupa menos espaço do que INFO, e do fato de que só precisariam ser representadas em estruturas INFO as informações associadas aos 500 empregados.) Estas duas maneiras tornariam o acesso muito simples: no primeiro caso, a informação sobre o empregadode CPF c estaria em vet[c], e, no segundo caso, em *vet[c]. Em qualquer dos dois casos, entretanto, a idéia é absurda, por causa do espaço total requerido. Uma variante desta idéia procura reduzir o espaço usando um “CPF parcial”, por exemplo, os três últimos dígitos. Neste caso, poderíamos ter um vetor
PT vet[1000];

e a informação sobre o mesmo empregado estaria em *vet[c%1000], usando-se aquio operador % de C, que representa “módulo”, ou “resto da divisão”. O espaço foi reduzido a um total aceitável, o acesso continua simples, mas um problema adicional surgiu: dois empregados que tem CPFs com os mesmos três últimos dígitos passam a ter as informações guardadas na mesma posição do vetor. Esta situação é chamada de “colisão”, e deve ser resolvida encontrando-se uma posição alternativapara os dados de um dos empregados.

1 2

to hash significa cortar em pedacinhos, picar; falando de comida, hash pode ser picadinho. ou, mais precisamente, seu número de inscrição no cadastro de pessoas físicas da receita federal Estruturas de Dados, J. L. Rangel, 13-1

No contexto da nossa discussão neste capítulo, a função “tomar os três últimos dígitos do CPF” é a função de hash, vet éuma tabela hash. Naturalmente este sistema só pode ser utilizado se tivermos uma boa solução para o problema da colisão. Em particular, a probabilidade de colisão pode ser reduzida usando uma tabela suficiente para várias vezes o número total de entradas. Por exemplo, uma tabela com 1000 entradas (como acima), no caso de uma empresa com 500 empregados (500 posições ocupadas) teria uma probabilidadede 50% de colisão, se fosse feita a inserção de um novo empregado. A propriedade fundamental da função de hash é a de espalhar bem as chaves de busca (os valores pelos quais se faz a busca na tabela), para que o número de colisões seja o menor possível, e é neste sentido que dissemos, no início desta Introdução, que seria bom usar posições aleatórias da tabela para guardar as informações. 13.2.Formas possíveis de tratamento de colisões Há várias formas possíveis de tratar colisões. A mais simples é usar a próxima posição vazia, em caso de colisão. Por exemplo, para inserir um elemento x numa tabela, usando a função de hash h, podemos usar a primeira das posições h(x), h(x)+1, h(x)+2, … que estiver vazia. (Se o final da tabela for atingido, continuamos, circularmente, a partir do início.)Esta forma de tratamento de colisões tem uma desvantagem fundamental, que é a tendência de formação de grupos de posições ocupadas consecutivas, fazendo com que a primeira posição vazia, na prática, possa ficar muito longe da posição original, dada pela função de hash. Para inserir um determinado valor x na tabela, ou para concluir que o valor não se encontra na tabela, é necessário encontrar a...
tracking img