Como tantas outras, uma Tabela Hash é mais uma estrutura de dados, e assim como toda estrutura de dados, possui um objetivo bem específico. O uso de uma tabela hash é indicado quando se sabe o tamanho do conjunto de dados e é necessário uma grande quantidade de busca que deve ser respondida rapidamente.
Em sua forma mais simples, uma tabela hash é um vetor maior que o tamanho do conjunto de dados que irá armazenar. Sua eficiência ou não no processo de busca está diretamente atrelado à função de espalhamento. É esta função que recebe uma chave (um nome, um cpf, uma matrícula por exemplo) e gera o índice no vetor onde o dado será salvo.
No processo de busca, a chave buscada passa pela mesma função de espalhamento, gerando assim o mesmo índice, tornando a busca localizada em uma região da tabela.
Toda função de espalhamento, por melhor que seja, pode gerar colisões, quando a função gera o mesmo índice para dados diferentes. Quando isso ocorre, há ao menos duas formas para seu tratamento.
A primeira, é inserir o novo elemento na próxima posição vazia na tabela, como apresentado na figura a seguir. Neste exemplo, o conjunto de dados possui 6 elementos. O tamanho M da tabela é 11 (primo mais próximo do dobro do tamanho do conjunto de dados) e a função de espalhamento utilizada é o resto da divisão do número a ser inserido pelo tamanho da tabela (chave % M).
Ao inserir o sexto elemento (40), a função de espalhamento gera o índice 7 (resto de 40 dividido por 11), que já está ocupado pelo elemento 73. Temos aí uma colisão. A próxima posição, 8, também está preenchida (8), fazendo com que o 40 seja inserido na posição 9.
A segunda forma para tratar uma colisão é criar um vetor de listas encadeadas. Assim, cada posição do vetor terá uma lista. Ao fazer uma busca, não é necessário buscar em toda a tabela, mas apenas na lista do índice gerado pela função de espalhamento, como apresentado a seguir.
No vídeo a seguir explico em mais detalhes como funciona uma Tabela Hash.
Neste próximo vídeo apresento uma possível implementação de uma Tabela Hash linear com a linguagem de programação C. O código encontra-se abaixo do vídeo.
Código Tabela Hash linear
#include <stdio.h>
#include <stdlib.h>
// constante repesenta o tamanho da tabela
#define M 19
// estrutura Pessoa com nome e uma matrícula
typedef struct{
int matricula;
char nome[50];
}Pessoa;
// nossa tabela hash do tipo Pessoa
Pessoa tabelaHash[M];
// inicializa nossa tabela com o valor de codigo -1
void inicializarTabela(){
int i;
for(i = 0; i < M; i++)
tabelaHash[i].matricula = -1;
}
// função de espalhamento (resto da divisão da chave por M)
int gerarCodigoHash(int chave){
return chave % M;
}
// função para ler e retornar uma pessoa
Pessoa lerPessoa(){
Pessoa p;
printf("Digite a matricula: ");
scanf("%d", &p.matricula);
scanf("%*c");
printf("Digite o nome: ");
fgets(p.nome, 50, stdin);
return p;
}
// inserir uma pessoa na tabela
void inserir(){
Pessoa pes = lerPessoa();
int indice = gerarCodigoHash(pes.matricula);
while(tabelaHash[indice].matricula != -1)
indice = gerarCodigoHash(indice + 1);
tabelaHash[indice] = pes;
}
Pessoa* buscar(int chave){
int indice = gerarCodigoHash(chave);
while(tabelaHash[indice].matricula != -1){
if(tabelaHash[indice].matricula == chave)
return &tabelaHash[indice];
else
indice = gerarCodigoHash(indice + 1);
}
return NULL;
}
void imprimir(){
int i;
printf("\n------------------------TABELA---------------------------\n");
for(i = 0; i < M; i++){
if(tabelaHash[i].matricula != -1)
printf("%2d = %3d \t %s", i, tabelaHash[i].matricula, tabelaHash[i].nome);
else
printf("%2d =\n", i);
}
printf("\n----------------------------------------------------------\n");
}
int main() {
int op, chave;
Pessoa *p;
inicializarTabela();
do{
printf("1 - Inserir\n2 - Buscar\n3 - Imprimir\n0 - Sair\n");
scanf("%d", &op);
switch(op){
case 0:
printf("Saindo...\n");
break;
case 1:
inserir();
break;
case 2:
printf("Digite a matricula a ser buscada: ");
scanf("%d", &chave);
p = buscar(chave);
if(p)
printf("\n\tMatricula: %d \tNome: %s\n", p->matricula, p->nome);
else
printf("\nMatricula nao encontrada!\n");
break;
case 3:
imprimir();
break;
default:
printf("Opcao invalida!\n");
}
}while(op != 0);
return 0;
}
Por fim, um exemplo de Tabela Hash com listas encadeadas, também com a linguagem de programação C. O código encontra-se após o vídeo.
Código Tabela Hash com listas encadeadas
#include <stdio.h>
#include <stdlib.h>
// tamanho da tabela
#define M 19
// tipo pessoa
typedef struct {
int matricula;
char nome[50];
} Pessoa;
// tipo nó usado na lista encadeada
typedef struct no {
Pessoa pessoa;
struct no *proximo;
} No;
// tipo lista com um ponteiro para o primeiro nó
typedef struct {
No *inicio;
int tam;
} Lista;
// nossa tabela (vetor de ponteiros para listas)
Lista *tabela[M];
//--------------------------------- fim definições variáveis --------------------
//--------------------------------- funções meus tipos --------------------------
// cria e retorna um tipo pessoa
Pessoa criarPessoa() {
Pessoa p;
printf("Digite o nome da pessoa: ");
scanf("%*c");
fgets(p.nome, 50, stdin);
printf("Digite a matricula: ");
scanf("%d", &p.matricula);
return p;
}
// imprime uma pessoa
void imprimirPessoa(Pessoa p) {
printf("\tNome: %s\tMatricula: %d\n", p.nome, p.matricula);
}
//-------------------------------- início funções lista -------------------------
// cria uma lista vazia e retorna seu endereço na memória
Lista* criarLista() {
Lista *l = malloc(sizeof(Lista));
l->inicio = NULL;
l->tam = 0;
return l;
}
/*
inserir no início da lista
PARÂMETROS
p - nova pessoa a ser inserida
*lista - endereço de uma lista encadeada.
*/
void inserirInicio(Pessoa p, Lista *lista) {
No *no = malloc(sizeof(No));
no->pessoa = p;
no->proximo = lista->inicio;
lista->inicio = no;
lista->tam++;
}
// busca um elemento na lista
No* buscarNo(int mat, No *inicio) {
while(inicio != NULL) {
if(inicio->pessoa.matricula == mat)
return inicio;
else
inicio = inicio->proximo;
}
return NULL;// matricula não encontrada
}
void imprimirLista(No *inicio) {
while(inicio != NULL) {
imprimirPessoa(inicio->pessoa);
inicio = inicio->proximo;
}
}
//---------------------------------- fim funções lista -------------------------
//--------------------------- início funções tabela hash -----------------------
// inicializa a tabela com uma lista vazia em cada posição do vetor
void inicializar(){
int i;
for(i = 0; i < M; i++)
tabela[i] = criarLista();
}
// função de espalhamento
int funcaoEspalhamento(int mat){
return mat % M;
}
// cria uma pessoa e a insere na tabela
void inserTabela(){
Pessoa pes = criarPessoa();
int indice = funcaoEspalhamento(pes.matricula);
inserirInicio(pes, tabela[indice]);
}
// busca uma pessoa. Seu retorno é um endereço ou NULL
Pessoa* buscarPessoaTabela(int mat){
int indice = funcaoEspalhamento(mat);
No *no = buscarNo(mat, tabela[indice]->inicio);
if(no)
return &no->pessoa;
else
return NULL;
}
// imprimir tabela
void imprimirTabela(){
int i;
printf("\n---------------------TABELA-------------------------\n");
for(i = 0; i < M; i++){
printf("%d Lista tamanho: %d\n", i, tabela[i]->tam);
imprimirLista(tabela[i]->inicio);
}
printf("---------------------FIM TABELA-----------------------\n");
}
int main() {
int op, mat;
Pessoa *p;
inicializar();
do {
printf("\n0 - Sair\n1 - Inserir\n2 - Buscar\n3 - Imprimir tabela\n");
scanf("%d", &op);
switch(op) {
case 0:
printf("saindo...\n");
break;
case 1:
inserTabela();
break;
case 2:
printf("Qual a matricula a ser buscada? ");
scanf("%d", &mat);
p = buscarPessoaTabela(mat);
if(p) {
printf("Pessoa encontrada: Matricula: %d\tNome: %s", p->matricula, p->nome);
} else
printf("Pessoa nao contrada!\n");
break;
case 3:
imprimirTabela();
break;
default:
printf("Opcao invalida!\n");
}
} while(op != 0);
return 0;
}
