Ajuda com Hashtable por favor

Programação Java
#1

Ola a todos,

Estou desenvolvendo um programinha besta onde eu faço manualmente os métodos de uma hashtable e estou com dificuldade na lógica do método de remoção.

Nesse meu código abaixo, se inserirmos um valor qualquer e fizermos a busca ele retornará “TRUE” como deveria, mas ao chamar o método de remoção obtenho um “ArrayIndexOutofBounds”. Isso é visivelmente corrigido no método “removeLP” já que não faço a verificação da variável “aux” comparada ao tamanho do vetor.

Meu problema é, mesmo fazendo essa verificação, eu não consigo um output correto do método “busca” após remover algum valor.

Alguém poderia me ajudar?

Obrigado.

[code]public class HashTable {
private int [] vetor_inteiro;
private boolean [] vetor_booleano;
private int tamanho;

public HashTable(int tam) {
    vetor_inteiro = new int[tam];
    vetor_booleano = new boolean[tam];
    tamanho = tam;
    
}

public int HashCode(int chave){
    return (107 * chave)%tamanho;
    
}

public void insere(int chave){
    int aux = HashCode(chave);
    if(vetor_inteiro[aux]==0){
        vetor_inteiro[aux]=chave;
    }else
        linearProbing(chave, aux+1);
    
    
}

public void linearProbing(int chave, int aux){
    if(aux!=tamanho){
        
        if(vetor_inteiro[aux]==0){
            vetor_inteiro[aux]=chave;
            vetor_booleano[aux]=false;
            
        }else
            linearProbing(chave, aux+1);
    }else
        System.out.print("Vetor cheio");
}

public boolean busca(int chave){
    int aux = HashCode(chave);
    if(vetor_inteiro[aux]==chave)
        return true;
    else
        return buscaLP(chave, aux+1);
    
}

public boolean buscaLP(int chave, int aux){
    if(aux!=tamanho){
        if(vetor_inteiro[aux]==chave)
            return true;
        else
            return buscaLP(chave, aux+1);
        
    }else
        return false;
}

public void remove(int chave){
    int aux = HashCode(chave);
    if(vetor_booleano[aux]==true){
        vetor_inteiro[aux]=0;
    }else
        removeLP(chave, aux+1);
    
}

public void removeLP(int chave, int aux){
    if(vetor_booleano[aux]==true){
        vetor_inteiro[aux]=0;
    }else
        removeLP(chave, aux+1);
    
}

}[/code]

#2

Tem várias coisas estranhas neste código:

a) linearProbing
b) buscaLP
c) removeLP

Que coisa louca são estes métodos?

Vc utiliza um tal de aux (cruz credo) para circular nos arrays de forma sequencial sendo que o valor dele é retornado (HashCode) de forma NÃO sequencial (baseado em um parametro), deste jeito ao meu ver, se o valor de interesse estiver antes do valor de retorno o mecanismo pode não encontrar-lo causando a anomalia.

flws

#3

Bom esses métodos com LP (Linear Probing) são métodos que tem a necessidade de existir.

Tomando por base o hashcode, diferentes números sempre podem gerar um hashcode igual, desse forma por Linear Probing procuro o próximo valor do vetor que estiver vazio para fazer essa inserção.

Essa variável “aux” serve apenas para eu poder ter como base o valor do Hashcode de cada elemento e a partir dele fazer a chamada correta dos parâmetros dentro do campo.

Pensa assim, meu hashcode deu 0 durante a chamada do método “Insere”, quando eu chamar o método “busca” eu vou pegar esse hashcode (que armazenei no aux) e usar ele para saber se meu valor existe na posição correta.

Por hashcode entenda índice.

Espero ter esclarecido.

#4

Necessidade não tem. Na verdade, eles tornam a performance do HashTable instável, e são extremamente lentos, o que as vezes tornam a solução pior que o problema. Algumas abordagens alternativas são:

  1. Substituir o elemento anterior ou dar erro (ou seja, deixar para quem usa a classe a tarefa de corrigir o problema). É mais útil em aplicações de performance crítica.
  2. Colocar uma lista em cada posição do hash. Nesse caso, 2 elementos poderiam ocupar a mesma posição, mas a classe de hashtable fica um pouco mais complexa. A vantagem dessa abordagem é que ela escala melhor em uma hashtable cheia.

Agora também não há mal nenhum em seguir a linha que você está fazendo. Linear probing é uma alternativa sim, e muito usada.

No seu método removeLP, faltou testar se você está no último elemento da lista. Caso contrário, você obterá uma arrayIndexOutOfBoundException mesmo. Agora não entendi o porque de usar recursão num método tão simples. Não seria melhor usar um for direto?

Ah sim, e é uma boa também o seus métodos “LP” serem private ou, pelo menos, protected. Acho que não é o intuito que o usuário do seu HashTable os chame diretamente.

Engraçado, o seu método de busca me parece correto. Que valor você obtém após a remoção? Já tentou usar um debugger?

#5

Necessidade não tem. Na verdade, eles tornam a performance do HashTable instável, e são extremamente lentos, o que as vezes tornam a solução pior que o problema. Algumas abordagens alternativas são:

  1. Substituir o elemento anterior ou dar erro (ou seja, deixar para quem usa a classe a tarefa de corrigir o problema). É mais útil em aplicações de performance crítica.
  2. Colocar uma lista em cada posição do hash. Nesse caso, 2 elementos poderiam ocupar a mesma posição, mas a classe de hashtable fica um pouco mais complexa. A vantagem dessa abordagem é que ela escala melhor em uma hashtable cheia.

Agora também não há mal nenhum em seguir a linha que você está fazendo. Linear probing é uma alternativa sim, e muito usada.

No seu método removeLP, faltou testar se você está no último elemento da lista. Caso contrário, você obterá uma arrayIndexOutOfBoundException mesmo. Agora não entendi o porque de usar recursão num método tão simples. Não seria melhor usar um for direto?

Ah sim, e é uma boa também o seus métodos “LP” serem private ou, pelo menos, protected. Acho que não é o intuito que o usuário do seu HashTable os chame diretamente.

Engraçado, o seu método de busca me parece correto. Que valor você obtém após a remoção? Já tentou usar um debugger?[/quote]

Muito obrigado pela resposta completa. Sou bem iniciante em Java e não é de estranhar caso tenha várias coisas estranhas no meu código.

Para eu fazer a verificação se estou no último elemento da lista, verificando se o Hashcode for diferente do length do vetor, como eu fiz em outros métodos, daria certo não?

As chamadas recursivas foram feitas sem um “sentido específico”. Era a idéia inicial do exercício na verdade e serviu como uma forma de praticar a lógica já que tanto me confude tais métodos.

Eu faço uma classe main da seguinte forma:

[code]public class main {

public static void main(String args[]){

   HashTable ht = new HashTable(10);
   ht.insere(150);
   ht.insere(270);
   ht.insere(200);
   ht.insere(1000);
   ht.insere(666);
   ht.insere(999);
   
   System.out.println("Valor 150 existe: "+ht.busca(150) );
   System.out.println("Valor 270 existe: "+ht.busca(270) );
   System.out.println("Valor 200 existe: "+ht.busca(200) );
   System.out.println("Valor 1000 existe: "+ht.busca(1000) );
   System.out.println("Valor 666existe: "+ht.busca(666) );
   System.out.println("Valor 999 existe: "+ht.busca(999) );
          
   System.out.println("Após remoção dos valores 150,270, 200: " );

   ht.remove(150);
   ht.remove(270);
   ht.remove(200);

   System.out.println("Valor 150 existe: "+ht.busca(150) );
   System.out.println("Valor 270 existe: "+ht.busca(270) );
   System.out.println("Valor 200 existe: "+ht.busca(200) );

}

}[/code]

Após o método de remoção, se eu fizer uma busca novamente ele deveria me retornar “FALSE”, mas sempre o retorno é “TRUE” desses valores que foram removidos.

#6

Acho que a presença de 2 vetores está te confundido. Hora você testa pelo valor == 0, hora você testa pela presença do boolean.

Vamos simplificar considerando um valor especial VAZIO, sempre que a posição estiver desocupada, e eliminando o vetor boolean.

Ah sim, como essa classe não mapeia a chave a nada, chame-a de HashSet e não HashTable. Para ser um HashTable além da chave você deveria passar um valor. Depois você pode modificar isso (é bem simples, de fato).

Aqui está o código corrigido. Em alguns trechos, troquei o if pelo operador ternário. Também coloquei os ifs com return no início, para evitar identação. Note que se um if tem um returno dentro, não é necessário usar o else. Evitar identação é sempre uma boa idéia.

[code]import java.util.Arrays;

public class HashSet {
private int[] vetor_inteiro;
private static final int VAZIO = Integer.MIN_VALUE;

public HashSet(int tam) {
    vetor_inteiro = new int[tam];
    Arrays.fill(vetor_inteiro, VAZIO);
}

public int HashCode(int chave) {
    return (107 * chave) % getTamanho();
}

public void insere(int chave) {
    int hash = HashCode(chave);

    if (vetor_inteiro[hash] == chave)
        return;

    if (vetor_inteiro[hash] == VAZIO) {
        vetor_inteiro[hash] = chave;
    } else
        linearProbing(chave, hash + 1);
}

public void linearProbing(int chave, int pos) {
    if (pos == getTamanho())
        throw new IndexOutOfBoundsException("Vetor cheio!");

    if (vetor_inteiro[pos] == VAZIO) {
        vetor_inteiro[pos] = chave;
    } else
        linearProbing(chave, pos + 1);

}

public boolean busca(int chave) {
    int hash = HashCode(chave);
    return vetor_inteiro[hash] == chave ? true : buscaLP(chave, hash + 1);
}

protected boolean buscaLP(int chave, int hash) {
    if (hash == getTamanho())
        return false;

    return vetor_inteiro[hash] == chave ? true : buscaLP(chave, hash + 1);
}

public void remove(int chave) {
    int aux = HashCode(chave);
    if (vetor_inteiro[aux] == chave) {
        vetor_inteiro[aux] = VAZIO;
    } else
        removeLP(chave, aux + 1);
}

protected void removeLP(int chave, int pos) {
    if (pos == getTamanho())
        return;

    if (vetor_inteiro[pos] == chave) {
        vetor_inteiro[pos] = VAZIO;
    } else
        removeLP(chave, pos + 1);
}

public int getTamanho() {
    return vetor_inteiro.length;
}

}[/code]

#7

[quote=ViniGodoy]Acho que a presença de 2 vetores está te confundido. Hora você testa pelo valor == 0, hora você testa pela presença do boolean.

Vamos simplificar considerando um valor especial VAZIO, sempre que a posição estiver desocupada, e eliminando o vetor boolean.

Ah sim, como essa classe não mapeia a chave a nada, chame-a de HashSet e não HashTable. Para ser um HashTable além da chave você deveria passar um valor. Depois você pode modificar isso (é bem simples, de fato).

Aqui está o código corrigido. Em alguns trechos, troquei o if pelo operador ternário. Também coloquei os ifs com return no início, para evitar identação. Note que se um if tem um returno dentro, não é necessário usar o else. Evitar identação é sempre uma boa idéia.

[code]import java.util.Arrays;

public class HashSet {
private int[] vetor_inteiro;
private static final int VAZIO = Integer.MIN_VALUE;

public HashSet(int tam) {
    vetor_inteiro = new int[tam];
    Arrays.fill(vetor_inteiro, VAZIO);
}

public int HashCode(int chave) {
    return (107 * chave) % getTamanho();
}

public void insere(int chave) {
    int hash = HashCode(chave);

    if (vetor_inteiro[hash] == chave)
        return;

    if (vetor_inteiro[hash] == VAZIO) {
        vetor_inteiro[hash] = chave;
    } else
        linearProbing(chave, hash + 1);
}

public void linearProbing(int chave, int pos) {
    if (pos == getTamanho())
        throw new IndexOutOfBoundsException("Vetor cheio!");

    if (vetor_inteiro[pos] == VAZIO) {
        vetor_inteiro[pos] = chave;
    } else
        linearProbing(chave, pos + 1);

}

public boolean busca(int chave) {
    int hash = HashCode(chave);
    return vetor_inteiro[hash] == chave ? true : buscaLP(chave, hash + 1);
}

protected boolean buscaLP(int chave, int hash) {
    if (hash == getTamanho())
        return false;

    return vetor_inteiro[hash] == chave ? true : buscaLP(chave, hash + 1);
}

public void remove(int chave) {
    int aux = HashCode(chave);
    if (vetor_inteiro[aux] == chave) {
        vetor_inteiro[aux] = VAZIO;
    } else
        removeLP(chave, aux + 1);
}

protected void removeLP(int chave, int pos) {
    if (pos == getTamanho())
        return;

    if (vetor_inteiro[pos] == chave) {
        vetor_inteiro[pos] = VAZIO;
    } else
        removeLP(chave, pos + 1);
}

public int getTamanho() {
    return vetor_inteiro.length;
}

}[/code][/quote]

Puxa, muito obrigado! Funcionou perfeitamente!

Aproveitando esse tópico, eu estava tentando tornar esse interatividade mais dinâmica e criar uma interface bem simples em Swing. A idéia era ter 2 campos, uma que seria a chave e outro que seria o tamanho do vetor. Além disso 3 botoões, Inserir, Remover e Buscar além de uma textarea para a exibição do resultado.

Minha dúvida é o seguinte, como posso fazer para instanciar a classe HashSet e passar o valor digitado no campo Tamanho para poder dar início a todo o procedimento?

Meu problema é que não sei como passar esse valor para o construtor da classe HashSet sem colocar essa ação em algum action performed e caso eu instancie dentro de cada actionperformed não dará certo.

Obrigado mais uma vez.

#8

Você pode criar o seu HashSet como um atributo da sua janela. E então acessa-lo de dentro do ActionPerformed.

[code]public class SuaJanela extends JFrame {
private HashSet seuSet;
…

public SuaJanela() {
JButton btnNovo = new JButton();
btnNovo.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent evt) {
seuSet = new HashSet(10);
}
}
}[/code]

Aproveitando que você está estudando, depois tente alterar sua classe para usar Generics e permitir que seu HashSet contenha objetos de qualquer classe, ao invés de só números inteiros. Aí vc se aproveita do método hashCode() que todo objeto java tem implementado.

#9

Muito obrigado pelas dicas. Vou tentar implementar dessa formao Swing.

Estou ainda na fase inicial de Java, e parece que nunca vou entender esse “troço”. Ainda me enrolo demais com os tipos de atributos (protected, private, public…) e a forma de acesso aos mesmos, além também não ter nem idéia desse “Generics” ao qual fez referência.

Estou estudando por um livro chamado Head First Java (em inglês mesmo), não sei se conhece, existe algo que recomende?

Obrigado.

#10

Eu sempre recomendo esse livro mesmo. Mas já fica a dica, para quando vc chegar no capítulo de Generics. :wink:
Eles foram introduzidos no Java 5.

#11