ccna

17. Tabelas de dispersão
W. Celes e J. L. Rangel
No capítulo anterior, discutimos diferentes estruturas e algoritmos para buscar um determinado elemento num conjunto de dados. Para obtermos algoritmos eficientes, armazenamos os elementos ordenados e tiramos proveito dessa ordenação para alcançar eficientemente o elemento procurado. Chegamos a conclusão que os algoritmos eficientes de busca demandam um esforço computacional de O(log n). Neste capítulo, vamos estudar as estruturas de dados conhecidas como tabelas de dispersão (hash tables), que, se bem projetadas, podem ser usadas para buscar um elemento da tabela em ordem constante: O(1). O preço pago por essa eficiência será um uso maior de memória, mas, como veremos, esse uso excedente não precisa ser tão grande, e é proporcional ao número de elementos armazenados.
Para apresentar a idéia das tabelas de dispersão, vamos considerar um exemplo onde desejamos armazenar os dados referentes aos alunos de uma disciplina. Cada aluno é individualmente identificado pelo seu número de matrícula. Podemos então usar o número de matrícula como chave de busca do conjunto de alunos armazenados. Na
PUC-Rio, o número de matrícula dos alunos é dado por uma seqüência de oito dígitos, sendo que o último representa um dígito de controle, não sendo portanto parte efetiva do número de matrícula. Por exemplo, na matricula 9711234-4, o ultimo dígito 4, após o hífen, representa o dígito de controle. O número de matrícula efetivo nesse caso é composto pelos primeiros sete dígitos: 9711234.
Para permitir um acesso a qualquer aluno em ordem constante, podemos usar o número de matrícula do aluno como índice de um vetor – vet. Se isso for possível, acessamos os dados do aluno cuja matrícula é dado por mat indexando o vetor – vet[mat]. Dessa forma, o acesso ao elemento se dá em ordem constante, imediata. O problema que encontramos é que, nesse caso, o preço pago para se ter esse acesso rápido é muito grande. Vamos