Dando continuidade ao nosso Curso de Programação C e ao módulo sobre a estrutura de busca tabela hash, vamos ver nesta aula como implementar uma TABELA HASH com vetor na prática.
O primeiro passo é definir o tamanho da nossa tabela. Como vimos na aula anterior, o tamanho da tabela deve ser definido em função da quantidade de elementos que serão inseridos na tabela. Assim, estou assumindo que nosso conjunto de dados possui tamanho 15.
Ainda orientado pela teoria da aula anterior, os números primos ideais para serem o tamanho da nossa tabela é 29 e 31, o primo mais próximo do dobro da quantidade de elementos a serem armazenados na tabela. Vou escolher o 31. Esse valor será definido como a constante global TAM.
Como vamos inserir 15 elementos em um vetor que possui tamanho 31, precisamos ser capazes de identificar corretamente uma posição vazia do vetor. Para isso estou assumindo que o elemento zero não pertence ao conjunto dos 15 elementos que serão armazenados na tabela. Assim, a posição que possuir o valor zero será considerada uma posição vazia.
Agora, antes de fazer qualquer operação, precisamos limpar nossa tabela, ou seja, inicializar o vetor com zero, indicando que todas as posições estão vazia. Isso será feito com o procedimento a seguir.
/*
Inicializa o vetor com zero em todas as posições
*/
void inicializarTabela(int t[]){
int i;
for(i = 0; i < TAM; i++)
t[i] = 0;
}
Para inserir qualquer valor na tabela hash precisamo da função hash ou função de espalhamento. Como vimos na aula anterior, é esta função que irá distribuir, espalhar os elementos pela tabela durante o processo de inserção. Uma boa função hash fará uma boa distribuição dos elementos na tabela enquanto uma função hash ruim irá produzir muitas colisões, podendo prejudicar o processo de busca.
Aqui neste exemplo usaremos o resto da divisão do valor a ser inserido pelo tamanho da tabela, como escrito a seguir.
/*
Função hash ou função de espalhamento
Retorna o resto da divisão do valor a ser inserido pelo tamanho da tabela, que é o índice onde o elemento será inserido
*/
int funcaoHash(int chave){
return chave % TAM;
}
Agora que temos a função hash podemos escrever um procedimento para realizar o processo de inserção de um elemento na tabela. Este procedimento precisa receber a tabela e o valor a ser inserido (ou o valor pode ser lido dentro do procedimento). Tendo o valor a ser inserido, usamos a função hash vista acima para descobrir onde o elemento será inserido e fazemos a inserção.
Observe que, como vimos na aula teórica, pode ocorrer colisão ao fazer uma inserção, quando a função hash gera o mesmo índice para elementos diferentes. Neste caso, precisamos procurar a próxima posição vazia para inserir este elemento. Isso pode ser feito com uma repetição do tipo enquanto. Enquanto a posição do índice gerado for diferente de zero, geramos um novo índice, mas agora passamos para a função hash não o elemento a ser inserido, mas o índice gerado mais 1. Assim, se foi gerado por exemplo o índice 15 e esta posição já está ocupada, passamos para a função hash 15 + 1.
O interessante deste método é que não precisamos nos preocupar com o fim do vetor pois, como a função retorna o resto da divisão pelo tamanho da tabela, quando o fim do vetor for atingido o resto será zero e automaticamente iremos para o início do vetor.
/*
Procedimento para inserir um elemento na tabela hash
*/
void inserir(int t[], int valor){
int id = funcaoHash(valor);
while(t[id] != 0){
id = funcaoHash(id + 1);
}
t[id] = valor;
}
A função de busca segui os mesmos passos da inserção. Recebemos a tabela e o valor a ser procurado. Com a função hash descobrimos o índice onde o elemento deve estar caso ele exista na tabela. Com o índice gerado pela função hash, basta verificar se o valor procurado está naquela posição.
Novamente precisamos lembrar que pode ter ocorrido colisão no momento da inserção. Assim, caso a posição indicada pela função hash não esteja vazia (diferente de zero) precisamos verificar as posições seguintes até encontrar o elemento ou uma posição vazia.
/*
Função para buscar na tabela hash
*/
int busca(int t[], int chave){
int id = funcaoHash(chave);
printf("\nIndice gerada: %d\n", id);
while(t[id] != 0){
if(t[id] == chave)
return t[id];
else
id = funcaoHash(id + 1);
}
return 0;
}
Para imprimir toda a tabela, basta fazer uma repetição para imprimir um vetor de inteiros, como apresentado abaixo.
/*
Procedimento para imprimir a tabela
*/
void imprimir(int t[]){
int i;
for(i = 0; i < TAM; i++){
printf("%d = %d\n", i, t[i]);
}
}
Código completo em C para a Tabela Hash com Vetor
/*
Aula 260: Tabela Hash linear com vetor
Código escrito por Wagner Gaspar
Setembro de 2021
*/
// 2 * 15 = 31
#define TAM 31
void inicializarTabela(int t[]){
int i;
for(i = 0; i < TAM; i++)
t[i] = 0;
}
int funcaoHash(int chave){
return chave % TAM;
}
void inserir(int t[], int valor){
int id = funcaoHash(valor);
while(t[id] != 0){
id = funcaoHash(id + 1);
}
t[id] = valor;
}
int busca(int t[], int chave){
int id = funcaoHash(chave);
printf("\nIndice gerada: %d\n", id);
while(t[id] != 0){
if(t[id] == chave)
return t[id];
else
id = funcaoHash(id + 1);
}
return 0;
}
void imprimir(int t[]){
int i;
for(i = 0; i < TAM; i++){
printf("%d = %d\n", i, t[i]);
}
}
int main(){
int opcao, valor, retorno, tabela[TAM];
inicializarTabela(tabela);
do{
printf("\n\t0 - Sair\n\t1 - Inserir\n\t2 - Buscar\n\t3 -Imprimir\n");
scanf("%d", &opcao);
switch(opcao){
case 1:
printf("\tQual valor desseja inserir? ");
scanf("%d", &valor);
inserir(tabela, valor);
break;
case 2:
printf("\tQual valor desseja buscar? ");
scanf("%d", &valor);
retorno = busca(tabela, valor);
if(retorno != 0)
printf("\tValor encontrado: %d\n", retorno);
else
printf("\tValor nao encontrado!\n");
break;
case 3:
imprimir(tabela);
break;
default:
printf("Opcao invalida!\n");
}
}while(opcao != 0);
return 0;
}
