Trabalho Prático n^o 2

Tabelas de Hash

Métodos de Programação II
LESI/LMCC, 1998/99

Introdução

Este trabalho deve ser realizado por grupos com um máximo de três alunos. O trabalho deve ser entregue até ao dia 30 de Abril na recepção do Departamento de Informática e nele deve constar a listagem do código escrito assim como um pequeno relatório em cuja primeira página deverá constar a identificação dos membros do grupo (número; nome e curso).

Enunciado

Pretende-se que neste trabalho os alunos estudem o comportamento de algumas funções de hash e de diferentes formas de lidar com colisões. Considere que a tabela tem 257 posições. Como exemplo de uma destas funções de hash, use a função

#define p 257

int hash1 (char *chave) {

   int r = 0;
   while (*chave) {
      r = (r >> 3) + *(chave++);
   }
   return (r % p) ;
}

1.

Escrever pelo menos mais uma função de hash para chaves do tipo string (i.e., char *).

2.

Escrever pelo menos duas formas de tratar colisões.

3.

Para cada uma das funções de hash e cada uma das formas de tratamento de colisões, faça uma tabela com a seguinte informação:

N. Chaves	N. Colisões	Colisões secundárias
20
40
60
80
100
120
140
160
180
200
220
240

Para isso pode usar os nomes dos alunos inscritos a Paradigmas de Programação I que pode encontrar aqui .