• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

D7Sousa

Duvida - HashTable

11 mensagens neste tópico

Boas, eu tenho um exercício para fazer onde diz para implementar uma HashTable mas não estou a conseguir resolver o problemas das colisões. Por acaso ninguém tem ai um programa que implemente uma HashTable para eu ver como se faz?

Cumprimentos.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não.

Ninguém te vai mostrar código já pronto. Se perguntares como se trata uma colisão, ou colocares a tua função de inserção, teremos todo o gosto em ajudar. Até lá, temos pena.

2.4) Não é permitido a criação de tópicos a pedir para que se façam trabalhos. Pedir ajuda é diferente de pedir trabalhos feitos. Tópicos com este tipo de conteúdos estão sujeitos a serem bloqueados e o autor do mesmo avisado por mensagem privada.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Peço desculpa não sabia que existia essa regra. Então eu a baixo vou deixar o código que fiz, e uma coisa, o problema esta no ciclo while que esta dentro do procedimento Adicionar.

#include <stdio.h>
#define TAMANHO 20

int Hash(int chave){
    int i, resultado = 0;
    
    for(i = 0; i <= 7; i++){
        resultado = i + chave * 7;    
    }
    return resultado % TAMANHO;
}

void Adicionar(int tabelaHash[]){
    int numero, numeroAux;
     
    printf("Numero: ");
    scanf("%d", &numero);
        
    numeroAux = Hash(numero);

    if(tabelaHash[numeroAux] == 0){
        tabelaHash[numeroAux] = numero;
    }
    else{     
        while(tabelaHash[numeroAux] != 0){
            numeroAux++;
            numeroAux = Hash(numeroAux);
                
                if(tabelaHash[numeroAux] == 0){
                    tabelaHash[numeroAux] = numero;
                }
        }
    }
    printf("*** NumeroAux = %d\n", numeroAux);
}

void Menu(int tabelaHash[]){
    int op;
    
    do
    {
        printf("1- Adicionar\n");
        printf("0- Sair\n");
        do
        {
            scanf("%d", &op);
            switch(op){
                case 1:
                    Adicionar(tabelaHash);
                break;
            }
        }while(op != 0 && op != 1);
    }while(op != 0);
}

void Inicializar(int tabelaHash[]){
    int i;
    
    for(i = 0; i <= TAMANHO; i++){
        tabelaHash[i] = 0;
    }
}

main()
{
    int tabelaHash[TAMANHO];
    Inicializar(tabelaHash);
    Menu(tabelaHash);
    system("PAUSE");
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

void Adicionar(int tabelaHash[]){
    int numero, numeroAux;
     
    printf("Numero: ");
    scanf("%d", &numero);
       
    numeroAux = Hash(numero);

    if(tabelaHash[numeroAux] == 0){
        tabelaHash[numeroAux] = numero;
    }
    else{    
        while(tabelaHash[numeroAux] != 0){
            numeroAux++;
            numeroAux = Hash(numeroAux);
               
                if(tabelaHash[numeroAux] == 0){
                    tabelaHash[numeroAux] = numero;
                }
        }
    }
    printf("*** NumeroAux = %d\n", numeroAux);
} 

O teu problema está, de facto no while.

O que se passa é que tu quando tas no while e entras no if, preenches a posição "numeroAux" e esta deixa de ser 0. Mas depois vais para o while, e como a posição não é zero, procuras de novo por uma posição que esteja a zero, e aqui entras em ciclo procurando sempre por uma nova posição para guardar o valor que já guardaste.

O que tu queres é, quando executas o corpo do if sair do while. Podes usar um break (acho que é essa a keyword) para isso. Outra alternativa seria fazer o while sem if lá dentro, e quando o while parasse é porque a posição estava livre e ai fazias o if.

Alguma dúvida diz

Edit: Outra coisa, essa forma de resolver as colisões não é a mais robusta, porque é que não consideras usar listas? A ideia é teres uma hashtable que indexa listas. Cada vez que há um elemento para a posição X, colocas esse elemento na lista apontada por essa posição X.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Que salganhada jpaires, não percebi nada...

D7Sousa:

A tua função adicionar calcula a hash do numero e guarda em numeroAux.

Se a posição calculada estiver livre (0) guarda lá, senão, enquanto houver posições ocupadas, anda para a frente.. Agora aí está o problema. Tu não queres calcular novas Hash's..

o código do else seria:

while(tabelaHash[numeroAux] != 0){
            numeroAux++;
            if(numeroAux>=MAX_SIZE)
                 numeroAux=0;
}
  
tabelaHash[numeroAux] = numero;

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Que salganhada jpaires, não percebi nada...

D7Sousa:

A tua função adicionar calcula a hash do numero e guarda em numeroAux.

Se a posição calculada estiver livre (0) guarda lá, senão, enquanto houver posições ocupadas, anda para a frente.. Agora aí está o problema. Tu não queres calcular novas Hash's..

o código do else seria:

while(tabelaHash[numeroAux] != 0){
            numeroAux++;
            if(numeroAux>=MAX_SIZE)
                 numeroAux=0;
}
  
tabelaHash[numeroAux] = numero;

Desculpa lá, eu agora é que não estou a perceber. Então se chegares ao fim da hashtable (MAX_SIZE), o que fazes é meter o número na posição 0 (zero) ? Porquê ? E se essa posição já lá tiver algo ? :S

O que eu disse para ele fazer foi algo do género

 
while(tabelaHash[numeroAux] != 0){
            numeroAux++;
            numeroAux = Hash(numeroAux);
               
                if(tabelaHash[numeroAux] == 0){
                    tabelaHash[numeroAux] = numero;
                    break;
                }
        }

ou (e esta hipotese aproximasse da hipotese que tu deste)

 
while(tabelaHash[numeroAux] != 0){
            numeroAux++;
            numeroAux = Hash(numeroAux);
        }
tabelaHash[numeroAux] = numero;

De resto, ele não pode calcular novas Hashs porque ? Não estou a ver qual é o problema, poderá ser mais pesado é verdade, mas de resto até me parece (que calculando novas hashs) que deverá fazer uma melhor distribuição das entradas.

Agora a tua proposta é que não é viável. Imagina o seguinte

1. numeroAux = X

2. Agora imagina que as posições >= X estão todas preenchidas e as posições < X algumas estão preenchidas e outras não

3. Entras no while e como as posições até MAX_SIZE estão todas preenchidas ficas no fim que numeroAux = 0

4. De seguida escreves o numero em numeroAux ( = 0). Ou seja, não só estas a escrever numa posição que já pode ter alguma coisa, como estas a ignorar que podem haver posições livres que nem sequer visitaste/consideraste

Por isso é que eu digo que calculando novas Hash tens uma maior distribuição da procura: tanto procuras para a frente do teu número original, como para trás.

Agora, o problema óbvio de qualquer implementação que considere resolver as colisões desta forma é que se a tabela ficar cheia não poderás inserir novos elementos e (se nao se alterar o código) entra-se em ciclo. Por isso é que eu propus resolver as colisões usando listas ligadas, até porque é mais limpinho. De resto, para verificar se a tabela está cheia é só questão de incrementar uma variável global cada vez que é inserido um novo valor.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

void Adicionar(int tabelaHash[]){
    int numero, numeroAux;
     
    printf("Numero: ");
    scanf("%d", &numero);
       
    numeroAux = Hash(numero);

    if(tabelaHash[numeroAux] == 0){
        tabelaHash[numeroAux] = numero;
    }
    else{    
        while(tabelaHash[numeroAux] != 0){
            numeroAux++;
            numeroAux = Hash(numeroAux);
               
                if(tabelaHash[numeroAux] == 0){
                    tabelaHash[numeroAux] = numero;
                }
        }
    }
    printf("*** NumeroAux = %d\n", numeroAux);
} 

O teu problema está, de facto no while.

O que se passa é que tu quando tas no while e entras no if, preenches a posição "numeroAux" e esta deixa de ser 0. Mas depois vais para o while, e como a posição não é zero, procuras de novo por uma posição que esteja a zero, e aqui entras em ciclo procurando sempre por uma nova posição para guardar o valor que já guardaste.

O que tu queres é, quando executas o corpo do if sair do while. Podes usar um break (acho que é essa a keyword) para isso. Outra alternativa seria fazer o while sem if lá dentro, e quando o while parasse é porque a posição estava livre e ai fazias o if.

Alguma dúvida diz

Edit: Outra coisa, essa forma de resolver as colisões não é a mais robusta, porque é que não consideras usar listas? A ideia é teres uma hashtable que indexa listas. Cada vez que há um elemento para a posição X, colocas esse elemento na lista apontada por essa posição X.

Olá isso do que disseste em cima não está correcto. Eu primeiramente inicializo o vector a 0 dai andar há procura dos zeros.

Quando a solução do break, isso e uma péssima ideia um bom programador deve evitar ao máximo utilizar breaks excepto no switch.

Por ultimo, sim eu sei que esta não a é a melhor maneira de fazer uma tabela de Hash, o ideal e como disseste que e fazer com listas ligadas, mas isto e um exercício académico logo tenho de fazer o que me pedem.

Cumprimentos

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Que salganhada jpaires, não percebi nada...

D7Sousa:

A tua função adicionar calcula a hash do numero e guarda em numeroAux.

Se a posição calculada estiver livre (0) guarda lá, senão, enquanto houver posições ocupadas, anda para a frente.. Agora aí está o problema. Tu não queres calcular novas Hash's..

o código do else seria:

while(tabelaHash[numeroAux] != 0){
            numeroAux++;
            if(numeroAux>=MAX_SIZE)
                 numeroAux=0;
}
  
tabelaHash[numeroAux] = numero;

Tens razão não tinha reparado nisso, mas agora ja corrigi e já funciona perfeitamente. Muito obrigado.

Cumprimentos

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Desculpa lá, eu agora é que não estou a perceber. Então se chegares ao fim da hashtable (MAX_SIZE), o que fazes é meter o número na posição 0 (zero) ? Porquê ? E se essa posição já lá tiver algo ? :S

O que eu disse para ele fazer foi algo do género

 
while(tabelaHash[numeroAux] != 0){
            numeroAux++;
            numeroAux = Hash(numeroAux);
               
                if(tabelaHash[numeroAux] == 0){
                    tabelaHash[numeroAux] = numero;
                    break;
                }
        }

ou (e esta hipotese aproximasse da hipotese que tu deste)

 
while(tabelaHash[numeroAux] != 0){
            numeroAux++;
            numeroAux = Hash(numeroAux);
        }
tabelaHash[numeroAux] = numero;

De resto, ele não pode calcular novas Hashs porque ? Não estou a ver qual é o problema, poderá ser mais pesado é verdade, mas de resto até me parece (que calculando novas hashs) que deverá fazer uma melhor distribuição das entradas.

Agora a tua proposta é que não é viável. Imagina o seguinte

1. numeroAux = X

2. Agora imagina que as posições >= X estão todas preenchidas e as posições < X algumas estão preenchidas e outras não

3. Entras no while e como as posições até MAX_SIZE estão todas preenchidas ficas no fim que numeroAux = 0

4. De seguida escreves o numero em numeroAux ( = 0). Ou seja, não só estas a escrever numa posição que já pode ter alguma coisa, como estas a ignorar que podem haver posições livres que nem sequer visitaste/consideraste

Por isso é que eu digo que calculando novas Hash tens uma maior distribuição da procura: tanto procuras para a frente do teu número original, como para trás.

Agora, o problema óbvio de qualquer implementação que considere resolver as colisões desta forma é que se a tabela ficar cheia não poderás inserir novos elementos e (se nao se alterar o código) entra-se em ciclo. Por isso é que eu propus resolver as colisões usando listas ligadas, até porque é mais limpinho. De resto, para verificar se a tabela está cheia é só questão de incrementar uma variável global cada vez que é inserido um novo valor.

Já tentas-te implementar este código? Eu já o fiz e funciona perfeitamente.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu sei...

O que se passa é que tu quando entras no while e encontras a primeira posição livre, preenchela. Mas depois quando sais do if vais de novo para o while e verificas de novo se esta posição está livre e como JÁ não está vais procurar por outra e assim sucessivamente. Vais preenchendo todas as posições até isso "rebentar".

Percebeste ou não ? É que a seguir só se fizer um desenho  :confused:

Quanto ao break, foi uma de duas sugestões que dei. É a melhor ? Certamente que não, prefiro (e não sou o único) muito mais a outra sugestão que fiz, agora tu usas o que te puser mais à vontade.

Já agora, qual é a universidade se não for muita indiscrição.

Funciona? Tu quereres dizer que "corre" sem entrar em ciclos, isso OK. Agora, implementar assim OMG =X Sempre que não encontras uma posição livre metes no zero =X Isso funciona até ao dia em que a hash começar a encher e tu começares a pôr tudo no zero :S

edit- tas a falar do código que eu postei ou que o edsousa postou ?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora