Can't find problem with Search function in Hash List

[HottoDogu]

Hello,
i made a List registry to store contacts, with name, city and cpf(id number), and search them by their cpf. However, the search function doesn't find the contact with given id number, and i've been unable to identify the problem so far (except that it's in either the storing of the contact, or the search itself, wich is more likely.

[.cpp for contact list]
#include "lista.hpp"
#include <bits/stdc++.h>
using namespace std;

void criaHash(Hash *hash,int num1,int num2) {
int i;
hash->n = 0;
hash->num_listas = num1;
hash->num_pesos = num2;
hash->vetor_listas = new Lista[num1];
for(i=0; i<num1; i++) {
iniciaLista(&hash->vetor_listas[i]);
}
hash->vetor_pesos = new int [num2];
for(i=0; i<num2; i++) {
hash->vetor_pesos[i] = rand() % 1000;
}
}

bool insereHash(Hash *hash,Item *x) {
if(Hash_PesquisaCelula(hash,x->chave)==NULL) {
insereLista(&hash->vetor_listas[Hash_H(hash,x->chave)],x);
hash->n++;
return true;
}
return false;
}

bool listaVazia(Lista* lista) {
if(lista->primeiro == NULL) return true;
else return false;
}

void iniciaLista(Lista* lista) {
lista -> primeiro = new Celula;
lista -> ultimo = lista -> primeiro;
lista -> primeiro -> prox = NULL;
}

void insereLista(Lista* lista,Item* x) {
lista -> ultimo->prox = new Celula;
lista -> ultimo = lista -> ultimo->prox;
lista -> ultimo->item.registro_hash.nome = x->registro_hash.nome;
lista -> ultimo->item.registro_hash.cpf = x->registro_hash.cpf;
lista -> ultimo->item.registro_hash.cidade = x->registro_hash.cidade;
lista -> ultimo->prox = NULL;
}

int Hash_H(Hash *hash,int *chave) {
int soma=0;
for(int i=0; i<11; i++) {
soma += chave[i] * hash->vetor_pesos[i%hash->num_pesos];
}

return (soma % hash->num_listas);
}

void Hash_Pesquisa(Hash *hash,int *chave,Item *x) {
Celula *aux = Hash_PesquisaCelula(hash,chave);
if(aux == NULL) {
cout <<"CPF: ";
for(int i=0; i<11; i++) {
cout<<chave[i];
}
cout<<" Nao encontrado"<<endl;
}
else {
*x = aux->prox->item;
cout<<"Nome: "<<aux->prox->item.registro_hash.nome<<endl;
cout <<"CPF: "<<aux->prox->item.registro_hash.cpf<<endl;
cout <<"Cidade: "<<aux->prox->item.registro_hash.cidade<<endl;
}
}

Celula* Hash_PesquisaCelula(Hash *hash,int *chave) {
int i = Hash_H(hash,chave);
Celula *aux = hash->vetor_listas[i].primeiro;

if(listaVazia(&hash->vetor_listas[i])) {
return NULL;
}
while (aux->prox != NULL) {
if(chave==aux->item.chave) return aux;
aux = aux->prox;
}
if(chave==aux->item.chave) return aux;
else return NULL;
}
[/code]

[jonnin]

lets start simple.
show me a main program that can insert 1 item into your hash table. Nothing else, just 4 or 5 lines to set up and insert a constant value.

[ne555]

you are asking about a logic error on your program.
to diagnose it, I want to be able to run it through a debugger, but you haven't post enough code

[dhayden]

This looks like C, not C++. If you're using C++ then this code could benefit from some object orientation.

Here is your code with indentation, names converted to English as best I could, and my guess at the contents of list.hpp. This compiles to a .o file, but I haven't added a main() function:

// #include "list.hpp"
#include <bits/stdc++.h>
using namespace std;

struct X
{
    int nome;
    int cpf;
    int cidade;
};

struct Item
{
    X registro_hash;
    int chave[11];
};

struct Node
{
    Node *next;
    Item item;
};

struct List
{
    Node *head, *tail;
};

struct Hash
{
    int n;
    int num_lists;
    int num_pesos;
    List *vector_lists;
    int *vector_pesos;
};

void initList(List * list);
void Hash_Search(Hash * hash, int *chave, Item * x);
Node *Hash_SearchNode(Hash * hash, int *chave);
void insertList(List * list, Item * x);
int Hash_H(Hash * hash, int *chave);

// Construct a hash object
void
createHash(Hash * hash, int num1, int num2)
{
    int i;
    hash->n = 0;
    hash->num_lists = num1;
    hash->num_pesos = num2;
    hash->vector_lists = new List[num1];
    for (i = 0; i < num1; i++) {
	initList(&hash->vector_lists[i]);
    }
    hash->vector_pesos = new int[num2];
    for (i = 0; i < num2; i++) {
	hash->vector_pesos[i] = rand() % 1000;
    }
}

// Insert a copy of x into the hash.
bool
insertHash(Hash * hash, Item * x)
{
    if (Hash_SearchNode(hash, x->chave) == NULL) {
	insertList(&hash->vector_lists[Hash_H(hash, x->chave)], x);
	hash->n++;
	return true;
    }
    return false;
}

// Is the list empty?
bool
listEmpty(List * list)
{
    if (list->head == NULL)
	return true;
    else
	return false;
}

// Construct a list
void
initList(List * list)
{
    list->head = new Node;
    list->tail = list->head;
    list->head->next = NULL;
}

// insert a copy of x into the list
void
insertList(List * list, Item * x)
{
    list->tail->next = new Node;
    list->tail = list->tail->next;
    list->tail->item.registro_hash.nome = x->registro_hash.nome;
    list->tail->item.registro_hash.cpf = x->registro_hash.cpf;
    list->tail->item.registro_hash.cidade = x->registro_hash.cidade;
    list->tail->next = NULL;
}

// Hash chave and return the bucket number in hash
int
Hash_H(Hash * hash, int *chave)
{
    int soma = 0;
    for (int i = 0; i < 11; i++) {
	soma += chave[i] * hash->vector_pesos[i % hash->num_pesos];
    }

    return (soma % hash->num_lists);
}

// Search hash for an item with chave.  If found, copy it to *x and print it
// out. If not found, print chave.
void
Hash_Search(Hash * hash, int *chave, Item * x)
{
    Node *aux = Hash_SearchNode(hash, chave);
    if (aux == NULL) {
	cout << "CPF: ";
	for (int i = 0; i < 11; i++) {
	    cout << chave[i];
	}
	cout << " Not found" << endl;
    } else {
	*x = aux->next->item;
	cout << "Nome: " << aux->next->item.registro_hash.nome << endl;
	cout << "CPF: " << aux->next->item.registro_hash.cpf << endl;
	cout << "Cidade: " << aux->next->item.registro_hash.cidade << endl;
    }
}

// Seach for a Node with chave in the hash. Return a pointer to the node
// or NULL if not found.
Node *
Hash_SearchNode(Hash * hash, int *chave)
{
    int i = Hash_H(hash, chave);
    Node *aux = hash->vector_lists[i].head;

    if (listEmpty(&hash->vector_lists[i])) {
	return NULL;
    }
    while (aux->next != NULL) {
	if (chave == aux->item.chave)
	    return aux;				 // bug
	aux = aux->next;
    }
    if (chave == aux->item.chave)
	return aux;
    else
	return NULL;
}

- listEmpty has a bug. list->head is never null in an initialized list. My advice is to fix the way you represent lists. There's no need for a tail pointer. Represent an empty list by head==NULL instead of dealing with a dummy node. Just insert at the head, the way god intended. :)

Your could would be more flexible if Hash_Search() just returned a pointer to the Item, or NULL if not found. The calling code could then decide what to do with it (like print it).

Your bugs are in HashSearchNode(). First, you're trying to compare chave with chave == aux->item.chave Since the parameter chave is a pointer and aux->item.chave is an array (or another pointer), this compares the pointers, not the contents that they point to. You want to compare the 11 numbers that they point to.

You could write a little function to compare them:

// Return true if the contents of chave1 and chave2 are equal
bool chaveEqual(int *chave1, int *chave2)
{
    for (int i=0; i<11; ++i) {
        if (chave1[i] != chave2[i]) {
            return false;
        }
    }
    // If you get here then they were all equal
    return true;
}

A more subtle bug is that you're checking the head of the list, which contains a dummy item. Here's a simpler version that also uses chaveEqual above:

Node *
Hash_SearchNode(Hash * hash, int *chave)
{
    int i = Hash_H(hash, chave);
    if (listEmpty(&hash->vector_lists[i])) {
        return NULL;
    }
    for (Node *aux = hash->vector_lists[i].head->next; aux != NULL; aux = aux->\
next) {
        if (chaveEqual(chave,aux->item.chave))
            return aux;
    }
    return NULL;
}