AED1 - Tabelas de Espalhamento (Hash tables)

aed1-hash-apresentacao.txt

https://drive.google.com/file/d/17qgLRxUEGWaEVhRaNbtrj3CoZVGCAfLH/view?usp=sharing

aed1-hash-implementacao.c

// Implementação da tabela de espalhamento (hash table) usando encadeamento.

// XXX: Exemplo de compilação e execução:
//   $ gcc -o hash aed1-hash-implementacao.c
//   $ ./hash < pessoas.txt

// Verificações de erro de entrada/saída ou de alocação de memória foram
// omitidas para manter a simplicidade e focar na implementação da tabela de
// espalhamento.

#include <stdio.h>
#include <stdlib.h>

typedef struct Pessoa Pessoa;

// 'Pessoa' é um registro da tabela.
// A chave é o 'nome' e é usada para buscar a 'idade'.
// Cada pessoa também tem o endereço da próxima pessoa ou NULL em 'prox'.
struct Pessoa {
	char *nome;
	int idade;
	Pessoa *prox;
};

// 'M' é o tamanho do vetor 'tabela' e pode ser entendido como um parâmetro
// chamado de módulo.
#define M 41 // Números primos funcionam melhor pois distribuem os dados mais
             // uniformemente e reduzem colisões.

// 'tabela' é o vetor da tabela de espalhamento.
// Como será usado o encadeamento, cada posição ou bucket da 'tabela' é uma
// lista encadeada do registro 'Pessoa'. Assim, 'tabela' é um vetor para
// ponteiros de pessoas.
Pessoa *tabela[M]; // Como tabela é uma variável estaticamente alocada, todos os
                   // buckets são NULL por padrão.

// 'hash' é a função de espalhamento.
// Sua função é levar o universo das chaves (nomes das pessoas nesse caso) aos
// índices 0..M-1.
int
hash(char *s)
{
	// Para evitar que essa conversão de string para inteiro produza
	// números maiores que INT_MAX, causando um overflow (undefined
	// behavior), é usado um inteiro sem sinal (unsigned) que permite um
	// "wrap around", fazendo o valor ficar entre 0 e UINT_MAX (que depois é
	// truncado com M).
	unsigned int h = 0; // 'h' é a "soma" dos caracteres.
	while (s[0]) {
		// O uso de 256 não é obrigatório, é possível usar outra base.
		// Citando o professor Paulo Feofiloff:
		//   "Em geral, encontrar uma boa função de espalhamento é mais
		//   uma arte que uma ciência."
		h = (h * 256 + s[0]) % M;
		++s;
	}
	return h;
}

// Retorna 1 se as strings forem iguais, 0 caso contrário.
int
string_igual(char *a, char *b)
{
	while (a[0] && b[0]) {
		if (a[0] != b[0])
			return 0;
		++a;
		++b;
	}
	return a[0] == b[0];
}

// 'tabela_insira' insere uma nova pessoa e realiza o encadeamento quando
// necessário. Retorna 1 se foi inserida e 0 caso já exista.
int
tabela_insira(Pessoa *nova)
{
	Pessoa *pe;
	int h;
	h = hash(nova->nome);
	printf("Inserindo '%s':\t{idade: %3d, hash: %3d}\n", nova->nome, nova->idade, h);

	// Percorre a lista caso não esteja vazia.
	for (pe = tabela[h]; pe; pe = pe->prox) {
		// Se a string for igual, 0 é retornado pois a pessoa já existe
		// na tabela.
		if (string_igual(nova->nome, pe->nome))
			return 0;
	}

	// Insere a nova pessoa pelo início da lista, que é o contrário do que
	// foi ilustrado na apresentação com os registros inseridos no final.
	nova->prox = tabela[h];
	tabela[h] = nova;
	return 1;
}

// 'tabela_busque' retorna alguma pessoa pelo 'nome' ou NULL se não é encontrada.
Pessoa *
tabela_busque(char *nome)
{
	Pessoa *pe;
	int h;
	h = hash(nome);
	printf("Buscando '%s':\t{hash: %3d, ", nome, h);
	for (pe = tabela[h]; pe; pe = pe->prox)
		if (string_igual(nome, pe->nome))
			break;
	printf("encontrada: %s}\n", pe ? "sim" : "não");
	return pe;
}

void
tabela_imprima(void)
{
	Pessoa *pe;
	int i;
	for (i = 0; i < M; ++i) {
		printf("tabela[%d]\t=", i);
		for (pe = tabela[i]; pe; pe = pe->prox)
			printf(" (%s:%d)\t->", pe->nome, pe->idade);
		printf(" (NULL)\n");
	}
}

Pessoa *
nova_pessoa(char *nome, size_t nome_n, int idade)
{
	Pessoa *pe;
	int i;
	pe = malloc(sizeof(Pessoa));
	pe->nome = malloc(nome_n+1);
	for (i = 0; i < nome_n; ++i)
		pe->nome[i] = nome[i];
	pe->nome[nome_n] = '\0';
	pe->idade = idade;
	pe->prox = NULL;
	return pe;
}

// A função 'main' lê da entrada padrão (stdin) registros de nomes e idades e os
// insere na tabela. Cada registro é separado por nova linha (newline) e cada
// registro contém o nome como uma string (sequência de caracteres) e a idade
// como um inteiro separados por uma tabulação ('\t'). O arquivo pessoas.txt
// contém registros de exemplo.
int
main(void)
{
	char lin[64];
	int i;
	Pessoa *pessoa, *tmp;

	// Leitura e inserção dos registros na tabela.
	while (fgets(lin, sizeof(lin), stdin)) {
		for (i = 0; lin[i]; ++i) {
			if (lin[i] == '\t') {
				lin[i] = '\0';
				pessoa = nova_pessoa(lin, i, atoi(lin+i+1));
				tabela_insira(pessoa);
			}
		}
	}

	// Imprima a tabela inteira.
	putchar('\n');
	tabela_imprima();
	putchar('\n');

	// Busca de pessoas por nome.
	tabela_busque("Lara");
	tabela_busque("Oscar");
	tabela_busque("Quésia");
	tabela_busque("Sofia");
	tabela_busque("Daniel");
	tabela_busque("Diana");

	// Libera a memória da tabela.
	for (i = 0; i < M; ++i) {
		for (pessoa = tabela[i]; pessoa; pessoa = tmp) {
			tmp = pessoa->prox;
			free(pessoa->nome);
			free(pessoa);
		}
	}

	return 0;
}

// vim:set tw=80 spell spelllang=pt_br,en:

build.sh

#!/bin/sh

gcc -g -Wall -Werror -Wpedantic -fsanitize=address,leak,undefined \
	-o hash \
	aed1-hash-implementacao.c

pessoas.txt

Abel	2
Alice	18
Bruno	32
Carlos	45
Eduardo	51
Helena	19
Igor	19
Júlia	29
Kleber	41
Lara	34
Marcos	22
Nina	6
Otávio	39
Paula	28
Quésia	33
Rafael	55
Sofia	20
Tiago	47
Úrsula	25
Vitor	31
Wesley	44
Xênia	10
Yuri	26
Zilda	62
Alan	24
Beatriz	36
Débora	27
Elias	33
Fabiana	52
Gabriel	19
Heloísa	21
Ismael	42
Janaina	7
Kevin	29
Lorena	38
Mateus	20
Natália	18
Oscar	35
Raul	50
Tobias	60
Valéria	44