Tabela Hash(problema no tratamento)

Bruxo2 · 20 de julho de 2013

Estou implementando uma tabela hash, mas não consigo salvar ou imprimir um dado utilizando o tratamento de colisão por lista de encadeamento.

Quando compilo dar os seguintes warnings:

funcoes.c: In function ‘imprimeVetor’:

funcoes.c:60:7: warning: assignment from incompatible pointer type [enabled by default]

Só que eu não sei se meu erro é ao imprimir, ou ao salvar o dado no ponteiro, quando eu imprimo ao invés de aparecer os numeros certinhos, aparece lixos, por exemplo:

Pos - Numero - > encadeamento
0      8220
1      1929    ->  -1075001952(deveria ser 2320)
2      3050

E por ae vai.

Eis o código:

funcoes.c

#include "hash.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define FUNCAOHASH 2
//1 = hashmodelo
//2 = hashfracionaria
//3 = hashmultiplicativa
#define COLISAO 2
//1 = buscalinear
//2 = encadeamento

#define CARGAMAXIMA 0.6
static int numeroElementos=0;
int hashModelo(char *chav, int modulo){
	int h = 0;
	int n,i;
	n = strlen(chav);
	for(i=0;i<n;i++){
		h += chav[i]*31*n;
	}
	return h%modulo;
}

//funcao hash que utiliza as strings para formar uma, adicionado o modulo para se adaptar ao tamanho da tabela.

int hashFracionaria(int numero, int modulo){
	float a, s;
	int saida;
	a = (sqrt(5)-1)/2;

	s = numero*a;

	s =  ((s - floor(s))*numero);
	saida = (int) s;

	return saida%modulo;

}

//funcao hash fracionaria, utiliza a parte int da chave de entrada para calcular a posição.

int hashMultiplicativa(int numero, int modulo){
	return (numero*2654435761)%modulo;
}
//hash multiplicativa de knuth


void imprimeVetor(int maximo, Chave vet[]){
	int i =0;
	Chave *n;
	for(i=0;i<maximo;i++){
		n = &vet[i];
		printf("\n%d - %d", i, n->numero);

		if(COLISAO==2){
			while(n->prox!=NULL){
				n = &n->prox;
				printf("-> %d", n->numero);
			}

		}

	}

}



//funcao pra imprimir o valor com um maximo pré-determinado, para testes apenas.

int escolheHash(int modulo, Chave c){

	switch(FUNCAOHASH){
		case 1:
			return hashModelo(c.string, modulo);
		break;

		case 2:
			return hashFracionaria(c.numero,modulo);
		break;

		case 3:
			return hashMultiplicativa(c.numero,modulo);
		break;
	}
}

//funcao para escolhe qual funcao hash usará

int insere(Chave c, int modulo, Chave* vet){
	numeroElementos++;
	float fatorCarga = (float) numeroElementos/modulo;
	if(fatorCarga>CARGAMAXIMA){
		//printf("REHASH");
	}
	if(vet[escolheHash(10,c)].numero==0){
		vet[escolheHash(10, c)] = c;
	}else{
		//printf("HASH: %d %d\n", escolheHash(10,c), c.numero);

		tratarColisao(c, escolheHash(10,c), vet, modulo);
	}






	return numeroElementos;

}

//funcao paraFunção que encadeia:
 inserir

int inicializaVetor(Chave *vet, int posições){
	int i;
	Chave c;
	c.numero = 0;
	c.string = '\0';
	c.prox = NULL;
	for(i=0; i<posições;i++) vet[i] = c;
}
//inicializarVetor

void tratarColisao(Chave c, int pos, Chave *vet, int tamanho){
	switch(COLISAO){
		case 1:
			buscaLinear(c, pos, vet,tamanho);
		break;

		case 2: 
			encadeamento(c, pos, vet);
		break;
	}

}

void buscaLinear(Chave c, int pos, Chave *vet, int tamanho){
	Chave n;
	n.numero = 10;
	while(n.numero!=0){
		pos++;
		if(pos==tamanho) pos = 0;
		//printf("%d %d\n", pos, tamanho);

		n = vet[pos];

	}
	vet[pos] = c;
}

void encadeamento(Chave c, int pos, Chave * vet){
	Chave *n;
	n = &vet[pos];
	while(n->prox!=NULL){
		n = n->prox;

	}
	n->prox = (Chave *) malloc (sizeof(Chave));
	n->prox = &c;
	n = &vet[pos];
	//printf("%d, %d",  n->numero, n->prox->numero);


}

hash.h

#ifndef HASH_H
#define HASH_H


typedef struct chave {
int numero;
char *string;
struct chave *prox; // será usado para o tratamento de colisão encadeado
} Chave;




void imprimeVetor(int maximo, Chave *vet);

int hashModelo(char *chav, int modulo);

int escolheHash(int modulo, Chave c);

int hashFracionaria(int numero, int modulo);

int hashMultiplicativa(int numero, int modulo);

int insere(Chave c, int modulo,Chave* vet);

int inicializaVetor(Chave *vet, int posições);

void tratarColisao(Chave c, int pos, Chave *vet, int tamanho);

void buscaLinear(Chave c, int pos, Chave *vet, int tamanho);

void encadeamento(Chave c, int pos, Chave * vet);
#endif

hash.c

#include "hash.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int main(int argc, char** argv) {
	int posições = 10, numeroElementos = 0, i=0, aux2;
	char aux[150], *aux1;
	Chave vet1[posições];
	FILE *fp;
	inicializaVetor(vet1, posições);


	if((fp = fopen( "chaves2M.txt", "r")) == NULL ) {
		printf("Arquivo não encontrado\n");
		exit(1);
	}




	while(!feof(fp) && i<10){
		Chave novo;
		fgets(aux,150, fp);
		aux1 = strtok(aux, " ");
		aux2 = atoi(strtok(NULL, " "));
		novo.numero = aux2;	
		novo.string = (char*) malloc (150*sizeof(char));
		strcpy(novo.string,aux1);
		novo.prox = NULL;	
		insere(novo, posições, vet1);


		i++;

	}
	imprimeVetor(10, vet1);









}

ScreenBlack · 23 de julho de 2013

Não testei seu código. Mas, pela mensagem do compilador acusada na linha 60, é possível encontrar um erro:


n = &n->prox;

"n" e "prox" são do mesmo tipo, logo, não há necessidade do "&" para essa atribuição.

Bruxo2 · 23 de julho de 2013

Não testei seu código. Mas, pela mensagem do compilador acusada na linha 60, é possível encontrar um erro:
n = &n->prox;
"n" e "prox" são do mesmo tipo, logo, não há necessidade do "&" para essa atribuição.

O problema é que se eu tiro dar Segmentation fault (core dumped)

ScreenBlack · 27 de julho de 2013

Pelo que percebi, na função "insere()" tem uma verificação do vetor com busca de posição usando a função "escolheHash()".

O valor retornado, raramente, vai bater com uma posição real do vetor.

O vetor é de tamanho 10, portanto, ele começa na posição 0 e vai até 9. A função "escolheHash()", retorna números bem maiores que esse.

Declaração da variável "vet":


int posições = 10;
Chave vet1[posições];

Função "insere()" com linha de DEBUG, mostrando o valor de retorno da função "escolheHash()":


int insere(Chave c, int modulo, Chave* vet){
	numeroElementos++;
	float fatorCarga = (float) numeroElementos/modulo;
	if(fatorCarga>CARGAMAXIMA){
		//printf("REHASH");
	}
	printf("[DEBUG] escolheHash(10,c): %d\n");
	if(vet[escolheHash(10,c)].numero==0){
		vet[escolheHash(10, c)] = c;
	}else{
		//printf("HASH: %d %d\n", escolheHash(10,c), c.numero);

		tratarColisao(c, escolheHash(10,c), vet, modulo);
	}
	return numeroElementos;
}

Acredito que esse seja o problema todo.

EDIT:

Sobre o meu post anterior, realmente deve-se tirar o "&", caso contrário, virá ponteiro errado.

Bruxo2 · 27 de julho de 2013

Pelo que percebi, na função "insere()" tem uma verificação do vetor com busca de posição usando a função "escolheHash()".
O valor retornado, raramente, vai bater com uma posição real do vetor.

O vetor é de tamanho 10, portanto, ele começa na posição 0 e vai até 9. A função "escolheHash()", retorna números bem maiores que esse.

Declaração da variável "vet":
int posições = 10;
Chave vet1[posições];
Função "insere()" com linha de DEBUG, mostrando o valor de retorno da função "escolheHash()":
int insere(Chave c, int modulo, Chave* vet){
	numeroElementos++;
	float fatorCarga = (float) numeroElementos/modulo;
	if(fatorCarga>CARGAMAXIMA){
		//printf("REHASH");
	}
	printf("[DEBUG] escolheHash(10,c): %d\n");
	if(vet[escolheHash(10,c)].numero==0){
		vet[escolheHash(10, c)] = c;
	}else{
		//printf("HASH: %d %d\n", escolheHash(10,c), c.numero);

		tratarColisao(c, escolheHash(10,c), vet, modulo);
	}
	return numeroElementos;
}
Acredito que esse seja o problema todo.

EDIT:

Sobre o meu post anterior, realmente deve-se tirar o "&", caso contrário, virá ponteiro errado.

Mas é por isso que eu uso o modulo, no final de cada funcao hash ele faz o modulo com o tamanho do vetor, nesse caso 10, garantindo que o numero sempre fique entre 0 e 9

ScreenBlack · 27 de julho de 2013

Realmente eu havia me confundido.

O seu código está usando muita estrutura estática, para armazenar o conteúdo e atribuir em um vetor dinâmico, fazendo com que, referencias erradas usadas.

Dei uma modificada em seu código:

1) Vetor agora está totalmente alocado dinamicamente.

2) Modifiquei as chamadas das funções para usarem referencias, tanto para o elemento 'novo', quanto para o vetor.

3) Modifiquei as chamadas das funções, para usarem chamadas dinâmicas.

4) Comentei a função "buscaLinear", pois não entendi exatamente o que era pretendido.

Pelos testes, funcionou.

Segue:

funções.c

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

#include "hash.h"

#define FUNCAOHASH 2
//1 = hashmodelo
//2 = hashfracionaria
//3 = hashmultiplicativa
#define COLISAO 2
//1 = buscalinear
//2 = encadeamento

#define CARGAMAXIMA 0.6
static int numeroElementos=0;

unsigned hashModelo(char *chav, int modulo){
int h = 0;
int n,i;
n = strlen(chav);
for(i=0;i<n;i++){
h += chav[i]*31*n;
}
return h%modulo;
}

//funcao hash que utiliza as strings para formar uma, adicionado o modulo para se adaptar ao tamanho da tabela.

unsigned int hashFracionaria(int numero, int modulo){
float a, saida;
a = (sqrt(5)-1)/2;
saida = numero*a;

saida = ((saida - floor(saida))*numero);
printf("RESULTADO DE S: %f\n", saida);

return ( (int) saida % modulo);
}

//funcao hash fracionaria, utiliza a parte int da chave de entrada para calcular a posição.

unsigned hashMultiplicativa(int numero, int modulo){
return (numero * 2654435761) % modulo;
}
//hash multiplicativa de knuth

/// MODIFICADO
void imprimeVetor(int maximo, Chave **vet) // O valor 'maximo' já é a posição máxima do vetor
{
int i = 0;
Chave *n = NULL;
for( i = 0; i <= maximo; i++ )
{
n = vet[i]; // Inicializa o 'n'

if( n == NULL )
printf("%d -> vazio\n", i);
else
{
printf("%d -> %d\n", i, n->numero);

if ( COLISAO == 2 )
{
while( n->prox != NULL)
{
n = n->prox;
printf(" -> %d\n", n->numero);
}
}
}
}
}

//funcao pra imprimir o valor com um maximo pré-determinado, para testes apenas.

unsigned int escolheHash(int modulo, Chave *c){

switch(FUNCAOHASH){
case 1:
return hashModelo(c->string, modulo);
break;

case 2:
return hashFracionaria(c->numero,modulo);
break;

case 3:
return hashMultiplicativa(c->numero,modulo);
break;
}
}

//funcao para escolhe qual funcao hash usará

int insere(Chave *c, int modulo, Chave **vet)
{
numeroElementos++;
float fatorCarga = (float) numeroElementos/modulo;
if(fatorCarga>CARGAMAXIMA){
//printf("REHASH");
}
printf("[DEBUG] escolheHash(10,c): %d\n", escolheHash(10,c));
if( vet[escolheHash(10,c)] == NULL )
vet[escolheHash(10, c)] = c;
else
{
//printf("HASH: %d %d\n", escolheHash(10,c), c.numero);

tratarColisao(c, escolheHash(10,c), vet, modulo);
}

return numeroElementos;
}

//funcao paraFunção que encadeia:
//
// inserir

/// MODIFICADO
void inicializaVetor(Chave **vet, int posições){
int i;
for( i = 0; i < posições; i++ )
vet[i] = NULL;
}
//inicializarVetor

void tratarColisao(Chave *c, int pos, Chave **vet, int tamanho){
switch(COLISAO){
case 1:
buscaLinear(c, pos, vet,tamanho);
break;

case 2:
encadeamento(c, pos, vet);
break;
}

}

/// COMENTADO
//void buscaLinear(Chave c, int pos, Chave **vet, int tamanho){
// Chave n;
// n.numero = 10;
// while(n.numero!=0){
// pos++;
// if(pos==tamanho) pos = 0;
// //printf("%d %d\n", pos, tamanho);
//
// n = vet[pos];
//
// }
// vet[pos] = c;
//}

void encadeamento(Chave *c, int pos, Chave **vet){
Chave *n;
n = vet[pos];
printf("[DEBUG 1] n->prox: %p\n", n->prox);
while(n->prox!=NULL){
printf("[DEBUG 2] n->prox: %p\n", n->prox);
n = n->prox;
}
n->prox = (Chave *) malloc (sizeof(Chave));
n->prox = c;
n = vet[pos];
//printf("%d, %d", n->numero, n->prox->numero);

}

hash.h

#ifndef HASH_H
#define HASH_H

typedef struct chave {
int numero;
char *string;
struct chave *prox; // será usado para o tratamento de colisão encadeado
} Chave;

void imprimeVetor(int maximo, Chave **vet);

unsigned hashModelo(char *chav, int modulo);

unsigned escolheHash(int modulo, Chave *c);

unsigned hashFracionaria(int numero, int modulo);

unsigned hashMultiplicativa(int numero, int modulo);

int insere(Chave *c, int modulo,Chave **vet);

void inicializaVetor(Chave **vet, int posições);

void tratarColisao(Chave *c, int pos, Chave **vet, int tamanho);

void buscaLinear(Chave *c, int pos, Chave **vet, int tamanho);

void encadeamento(Chave *c, int pos, Chave **vet);
#endif

hash.c

#include "hash.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
int posições = 10, numeroElementos = 0, i=0, aux2;
char aux[150], *aux1;
Chave **vet1 = NULL;
Chave *novo = NULL;
FILE *fp;

vet1 = malloc( sizeof(Chave *) * 10 );

inicializaVetor(vet1, posições);

if((fp = fopen( "arq.txt", "r")) == NULL ) {
printf("Arquivo não encontrado\n");
exit(1);
}

while(!feof(fp) && i<10)
{
novo = malloc( sizeof(Chave) );

fgets(aux,150, fp);
aux1 = strtok(aux, " ");
aux2 = atoi(strtok(NULL, " "));
novo->numero = aux2;
novo->string = (char*) malloc (150*sizeof(char));
strcpy(novo->string,aux1);
novo->prox = NULL;
insere(novo, posições, vet1);

i++;

}
imprimeVetor( i, vet1);

return 0;
}

Bruxo2 · 28 de julho de 2013

Realmente eu havia me confundido.
O seu código está usando muita estrutura estática, para armazenar o conteúdo e atribuir em um vetor dinâmico, fazendo com que, referencias erradas usadas.

Dei uma modificada em seu código:

1) Vetor agora está totalmente alocado dinamicamente.

2) Modifiquei as chamadas das funções para usarem referencias, tanto para o elemento 'novo', quanto para o vetor.

3) Modifiquei as chamadas das funções, para usarem chamadas dinâmicas.

4) Comentei a função "buscaLinear", pois não entendi exatamente o que era pretendido.

Pelos testes, funcionou.

Segue:

funções.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#include "hash.h"

#define FUNCAOHASH 2
//1 = hashmodelo
//2 = hashfracionaria
//3 = hashmultiplicativa
#define COLISAO 2
//1 = buscalinear
//2 = encadeamento

#define CARGAMAXIMA 0.6
static int numeroElementos=0;

unsigned hashModelo(char *chav, int modulo){
int h = 0;
int n,i;
n = strlen(chav);
for(i=0;i<n;i++){
h += chav[i]*31*n;
}
return h%modulo;
}

//funcao hash que utiliza as strings para formar uma, adicionado o modulo para se adaptar ao tamanho da tabela.

unsigned int hashFracionaria(int numero, int modulo){
float a, saida;
a = (sqrt(5)-1)/2;
saida = numero*a;

saida = ((saida - floor(saida))*numero);
printf("RESULTADO DE S: %f\n", saida);

return ( (int) saida % modulo);
}

//funcao hash fracionaria, utiliza a parte int da chave de entrada para calcular a posição.

unsigned hashMultiplicativa(int numero, int modulo){
return (numero * 2654435761) % modulo;
}
//hash multiplicativa de knuth

/// MODIFICADO
void imprimeVetor(int maximo, Chave **vet) // O valor 'maximo' já é a posição máxima do vetor
{
int i = 0;
Chave *n = NULL;
for( i = 0; i <= maximo; i++ )
{
n = vet[i]; // Inicializa o 'n'

if( n == NULL )
printf("%d -> vazio\n", i);
else
{
printf("%d -> %d\n", i, n->numero);

if ( COLISAO == 2 )
{
while( n->prox != NULL)
{
n = n->prox;
printf(" -> %d\n", n->numero);
}
}
}
}
}

//funcao pra imprimir o valor com um maximo pré-determinado, para testes apenas.

unsigned int escolheHash(int modulo, Chave *c){

switch(FUNCAOHASH){
case 1:
return hashModelo(c->string, modulo);
break;

case 2:
return hashFracionaria(c->numero,modulo);
break;

case 3:
return hashMultiplicativa(c->numero,modulo);
break;
}
}

//funcao para escolhe qual funcao hash usará

int insere(Chave *c, int modulo, Chave **vet)
{
numeroElementos++;
float fatorCarga = (float) numeroElementos/modulo;
if(fatorCarga>CARGAMAXIMA){
//printf("REHASH");
}
printf("[DEBUG] escolheHash(10,c): %d\n", escolheHash(10,c));
if( vet[escolheHash(10,c)] == NULL )
vet[escolheHash(10, c)] = c;
else
{
//printf("HASH: %d %d\n", escolheHash(10,c), c.numero);

tratarColisao(c, escolheHash(10,c), vet, modulo);
}

return numeroElementos;
}

//funcao paraFunção que encadeia:
//
// inserir

/// MODIFICADO
void inicializaVetor(Chave **vet, int posições){
int i;
for( i = 0; i < posições; i++ )
vet[i] = NULL;
}
//inicializarVetor

void tratarColisao(Chave *c, int pos, Chave **vet, int tamanho){
switch(COLISAO){
case 1:
buscaLinear(c, pos, vet,tamanho);
break;

case 2:
encadeamento(c, pos, vet);
break;
}

}

/// COMENTADO
//void buscaLinear(Chave c, int pos, Chave **vet, int tamanho){
// Chave n;
// n.numero = 10;
// while(n.numero!=0){
// pos++;
// if(pos==tamanho) pos = 0;
// //printf("%d %d\n", pos, tamanho);
//
// n = vet[pos];
//
// }
// vet[pos] = c;
//}

void encadeamento(Chave *c, int pos, Chave **vet){
Chave *n;
n = vet[pos];
printf("[DEBUG 1] n->prox: %p\n", n->prox);
while(n->prox!=NULL){
printf("[DEBUG 2] n->prox: %p\n", n->prox);
n = n->prox;
}
n->prox = (Chave *) malloc (sizeof(Chave));
n->prox = c;
n = vet[pos];
//printf("%d, %d", n->numero, n->prox->numero);

}
hash.h
#ifndef HASH_H
#define HASH_H

typedef struct chave {
int numero;
char *string;
struct chave *prox; // será usado para o tratamento de colisão encadeado
} Chave;

void imprimeVetor(int maximo, Chave **vet);

unsigned hashModelo(char *chav, int modulo);

unsigned escolheHash(int modulo, Chave *c);

unsigned hashFracionaria(int numero, int modulo);

unsigned hashMultiplicativa(int numero, int modulo);

int insere(Chave *c, int modulo,Chave **vet);

void inicializaVetor(Chave **vet, int posições);

void tratarColisao(Chave *c, int pos, Chave **vet, int tamanho);

void buscaLinear(Chave *c, int pos, Chave **vet, int tamanho);

void encadeamento(Chave *c, int pos, Chave **vet);
#endif
hash.c
#include "hash.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
int posições = 10, numeroElementos = 0, i=0, aux2;
char aux[150], *aux1;
Chave **vet1 = NULL;
Chave *novo = NULL;
FILE *fp;

vet1 = malloc( sizeof(Chave *) * 10 );

inicializaVetor(vet1, posições);

if((fp = fopen( "arq.txt", "r")) == NULL ) {
printf("Arquivo não encontrado\n");
exit(1);
}

while(!feof(fp) && i<10)
{
novo = malloc( sizeof(Chave) );

fgets(aux,150, fp);
aux1 = strtok(aux, " ");
aux2 = atoi(strtok(NULL, " "));
novo->numero = aux2;
novo->string = (char*) malloc (150*sizeof(char));
strcpy(novo->string,aux1);
novo->prox = NULL;
insere(novo, posições, vet1);

i++;

}
imprimeVetor( i, vet1);

return 0;
}

a)Eu to numa duvida conceitual agora, fazendo o vetor ser alocado dinamicamente não acaba com o conceito de tabela hash? Sempre pensei que o vetor tinha que ser estático, para aumentar a velocidade de acesso a uma chave, ao invés de procurar o numero da chave, só colocar vet[chave], entendeu? E também com ela dinamica eu não preciso da função rehash(que não implementei ainda).

d) A buscaLinear é um tratamento de exceção que funciona assim, caso a função hash mapeie um elemento para uma chave já usada no vetor, ele coloca ela do lado.

ScreenBlack · 29 de julho de 2013

Em C, acredito que não dê pra usar uma chave qualquer diretamente na posição do vetor.

Terá de fazer a conversão da chave pra a posição do índice.

O que dá pra fazer, seria mascarar o número, por uma expressão, usando o "#define", porém, a execução em sí não mudará.

Modifiquei o código pra alocar dinamicamente o índice, mas, dá pra deixar estático. Sem problema algum.

Modificações para usar índice estático:

hash.h

//Inserir depois da "struct Chave"
typedef struct
{
Chave *inicio;
} Indice;

//Mudar os parâmetros das funções de "Chave **vet" para "Indice *vet".
//Exemplo:
int insere(Chave *c, int modulo, Indice *vet);

funcoes.c

//Trocar as chamadas "n = vet[i];" para "n = vet[i].inicio;"

//Na função "insere()", modoficar o segundo "if" para:
if( vet[escolheHash(10,c)].inicio == NULL )
vet[escolheHash(10, c)].inicio = c;

//Na função "inicializaVetor()", modificar a atribuição dentro do "for", para:
vet[i].inicio = NULL;

hash.c

//Adicionar a variável:
//Indice vet1[10] = { {.inicio = NULL} }; // Assim não precisa usar a função "inicializaVetor()".
Indice vet1[10];

Espero não ter esquecido de algo. Mas, é bem tranquilo fazer.

Bruxo2 · 30 de julho de 2013

Opa Screen, obrigado pela ajuda, mas no final eu consegui de um jeito mais simples.

Ficou assim o encadeamento:

void encadeamento(Chave c, int pos, Chave vet[]){
Chave *n;

n = &vet[pos];

while(n->prox!=NULL){

n = n->prox;

}

n->prox = (Chave *) malloc(sizeof(Chave));

n->prox->numero = c.numero;

n->prox->string = c.string;

n->prox->prox = NULL;

}

A lógica tava certa antes, o problema é colocar a lógica no papel hehe.