Ajuda com HashTable, LinkedList

Programação Java
#1

Bom Dia!

Primeiro Tópico já para pedir ajuda de vocês.
Preciso criar um programa que gere numeros aleatorios sem repetição, e utilize uma função de Hash, e salve em uma HashTable, que utiliza lista encadeada para colisão de dados.

Segue o que fiz até o momento:

import java.util.*;
import java.util.Set;  
import java.util.HashSet;

import javax.swing.JOptionPane;
class HTDemo {
public static void main(String args[]) {
	  
     Hashtable numbers = new Hashtable();
     List listA = new LinkedList();
     List listB = new LinkedList();
     int procura = 0;
     int locationIndex = 0;
     
     int tamVet = 0;  
     tamVet = Integer.parseInt(JOptionPane.showInputDialog(null, "Entre com o tamanho do vetor:"));  
     if (tamVet == 0) {  
         JOptionPane.showMessageDialog(null,"O tamanho não poder ser 0, Saindo do sistema.");  
         System.exit(0);  
     }  

     int UniversoKey = 0;  
     UniversoKey = Integer.parseInt(JOptionPane.showInputDialog(null, "Entre o universo de Chaves:"));  
     if (UniversoKey == 0) {  
         JOptionPane.showMessageDialog(null,"O tamanho não poder ser 0, Saindo do sistema.");  
         System.exit(0);  
     } 
     
     int vet[] = new int[tamVet];  
     
  //  Set<Integer> valores = new HashSet<Integer>(); 
	for(int i=0; i<vet.length; i++){  
        int retorno = (int) (UniversoKey * Math.random());
    //  valores.add(new Integer(retorno));
        vet[i] = retorno;  
    }  
//	System.out.println("Valores gerados:");  
//  for(Integer i : valores) System.out.println(i);
	
	System.out.print("Números Gerados  : [");  
    for(int i=0; i<vet.length; i++){  
        //ESTE IF VERIFICA SE É O ÚLTIMO NÚMERO DO VETOR. SE FOR, NÃO COLOCA VIRGULA DEPOIS
    	if(i < vet.length-1){
        	System.out.print(vet[i]+",");	
        }else {
    	System.out.print(vet[i]);
        }  
    }  
    System.out.print("]\n");
	
   for(int i=0; i<vet.length; i++){
    	if ((vet[i] % tamVet)==0)
    	//	numbers.put("0", vet[i]);
    		listA.add(vet[i]);
    	if ((vet[i] % tamVet)==1)
    	//	numbers.put("1",vet[i]);
     		listB.add(vet[i]);

		}
  //  System.out.println("Números na Posição 0 é: \n"  + numbers.get("0"));
    System.out.println("Números na Posição 0 é: \n" + listA);
  //  System.out.println("Números na Posição 1 é: \n"  + numbers.get("1"));
    System.out.println("Números na Posição 1 é: \n" + listB);
    
    procura = Integer.parseInt(JOptionPane.showInputDialog(null, "Digite o Valor que deseja procurar:"));
    if ((procura % tamVet)==0)
    locationIndex = listA.indexOf(procura);
    if ((procura % tamVet)==1)
    locationIndex = listB.indexOf(procura);
    System.out.println("O numero esta na posição: " + locationIndex);
   
	}

}

O código esta bem bagunçada, estou apanhando bastante, o programa esta gerando numeros aleatorios, mas com repetição.
Mas o que eu queria tentar resolver primeiro, seria a parte de jogar os valor nas listas, que vai da linha 51 à 57.
Segue exemplo de como eu teria que fazer:

Quantidade Numeros: 10
Universo de Numeros: 1 à 100

Numeros sorteados: 85,96,32,88,50,41,40,75,86,6

Ai faz MOD da quantidade de numeros, que neste caso é 10 e joga numa HashTable com lista encadeada:

Exemplo:

0 - 50,40
1 - 41
2 - 32
3 -
4 -
5 - 85,75
6 - 96,86,6
7 -
8 - 88
9 -

de 0 a 9 seriam as minhas listas.
Ele faz 50 mod 10, sobra 0, então joga na lista 0.
41 mod 10, sobra 1, então joga na lista 1.
Ai ele teria que jogar os respectivos numeros em cada lista.

No caso criei duas listas para o 0 e 1, mas eu não sei a quantidade de numeros que vou usar, pode ser 10, 20 ou 30.
Teria algum jeito de eu criar automaticamente isso?
Ou existe outra forma melhor de se fazer?

#2

em relaçao ao nros repetidos quem naum permite q eu saiba é o HashSet, pesquise mais sobre ele.

#3

Pois é, no código, nas linhas 31 à 38, eu tenho um esquema de HashSet, que esta na parte comentada.
Mas eu acho(nao tenho certeza), que eu teria que jogar esses valores em um vetor, mas ele me dá erro quando vou fazer isso.
Pois eu tenho que percorrer esses vetor depois, aplicar a função de Hash no valor e jogar o valor pra sua determinada LinkedList.

Essa parte aqui:

   Set<Integer> valores = new HashSet<Integer>();   
    for(int i=0; i<vet.length; i++){    
        int retorno = (int) (UniversoKey * Math.random());  
        valores.add(new Integer(retorno));  
 //      vet[i] = retorno;
}  
	System.out.println("Valores gerados:");  
    for(Integer i : valores) System.out.println(i);

Deste jeito ele gera numeros aleatorios sem repetição, mas na linha comentada eu tento armazenar em um vetor, e ai me da erro quando executo.
Consigo percorrer o HashSet e aplicar a minha formula?
Eu tenho que tentar colocar em um vetor mesmo??

#4

kra a única ctz que tenho(naum use vetor) no mais vc terá q descobrir sozinho mas vou dar uma dica veja meu codigo de percorrer um array:

[code]
List selectCidade = new ArrayList();
selectCidade.add(new SelectItem(null, “Selecione uma cidade…”));
for (Cidade cidade : cidades) {
selectCidade.add(new SelectItem(cidade.getCodigo().toString(),
cidade.getDescricao()));
}
return selectCidade;

[/code] é só pra vc ter uma idéia ok do poder dessas ferramentas…

#5

Provalvelmente eu tenha me explicado mal, e o meu código esteja confuso. Talvez nem seja essa a melhor maneira de se fazer.

O que eu preciso fazer é seguinte:
Criar um hash table através de um vetor. Colisões devem ser resolvidas através da criação de listas encadeadas. E usar uma função de Hash, exemplo: h1(k) = k mod N.
E para criar os numeros aleatorios sem repetição, eu posso inserir uma lista de números inteiros que estejam dispostos em ordem crescente.
Após a inserção dos números, uma série de consultas deverá ser feita, e os tempos medidos.

#6

Não precisas de saber quantas listas vais ter, precisas só saber, antes de adicionar um número numa posição da hashtable saber se já existe essa lista ou se tens de a criar.

#7

Eu tenho criado duas LinkedList, que criei para armazer os numeros.
Por exemplo:
Se 10 mod 2 = 0 - coloca na listA
Se 10 mod 2 = 1 - coloca na listB

Só que esse processo é manual.
Se eu quiser fazer 100 mod 10 por exemplo, eu teria que criar 10 listas. O problema que não sei quantas listas vão ser, teria que tentar criar algo automatico.

#8

As listas ficam dentro da Hashtable.

Pegando nos números do teu exemplo: 85,96,32,88,50,41,40,75,86,6

85 mod 10 = 5
Então verifica se já existe na hashtable a lista do 5,senão existe cria uma nova lista no 5
adiciona 85 à lista do 5

96 mod 10 = 6… mesma coisa

#9

[quote=pmlm]As listas ficam dentro da Hashtable.

Pegando nos números do teu exemplo: 85,96,32,88,50,41,40,75,86,6

85 mod 10 = 5
Então verifica se já existe na hashtable a lista do 5,senão existe cria uma nova lista no 5
adiciona 85 à lista do 5

96 mod 10 = 6… mesma coisa[/quote]

É isso que pretendo fazer, mas não sei como fazer…vc poderia me dar um exemplo? senão for muito incomodo.

#10 
Hashmap<Integer, List<Integer>> table= new Hashmap<Integer, List<Integer>>();

int number = 85;

int key = number %10; //85 mod 10 = 5 

if (table.get(key)==null){ //Então verifica se já existe na hashtable a lista do 5,senão existe cria uma nova lista no 5 
    table.put(key, new ArrayList<Integer>();
}
table.get(key).add(number); //adiciona 85 à lista do 5

Agora é adaptares ao teu código.

#11

[quote=pmlm][code]
Hashmap<Integer, List> table= new Hashmap<Integer, List>();

int number = 85;

int key = number %10; //85 mod 10 = 5

if (table.get(key)==null){ //Então verifica se já existe na hashtable a lista do 5,senão existe cria uma nova lista no 5
table.put(key, new ArrayList();
}
table.get(key).add(number); //adiciona 85 à lista do 5
[/code]

Agora é adaptares ao teu código.[/quote]

Bah…muito obrigado pela ajuda! vou tentar adaptar para o meu problema. Qualquer te aviso, valeu!!!

#12

Consegui implementar no meu código, mas estou tendo um pequeno problema que não consegui resolver.

[code] HashMap<Integer, List> table= new HashMap<Integer, List>();

 int tamVet = 0;  
 tamVet = Integer.parseInt(JOptionPane.showInputDialog(null, "Entre com a Quantidade de Números a serem Gerados:"));  
 if (tamVet == 0) {  
     JOptionPane.showMessageDialog(null,"O tamanho não poder ser 0, Saindo do sistema.");  
     System.exit(0);  
 }  

 int UniversoKey = 0;  
 UniversoKey = Integer.parseInt(JOptionPane.showInputDialog(null, "Entre o universo de Chaves:"));  
 if (UniversoKey == 0) {  
     JOptionPane.showMessageDialog(null,"O tamanho não poder ser 0, Saindo do sistema.");  
     System.exit(0);  
 } 
 
 int vet[] = new int[tamVet];  
 
Set<Integer> valores = new HashSet<Integer>(); 
for(int i=0; valores.size()<vet.length; i++){  
    int retorno = (int) (UniversoKey * Math.random());
    valores.add(new Integer(retorno));                 
      
    int key = retorno %tamVet;    
      
    if (table.get(key)==null){ //Então verifica se já existe na hashtable a lista do número,senão existe cria uma nova lista desse número   
        table.put(key, new ArrayList<Integer>());  
    }  
    table.get(key).add(retorno); //adiciona o número em sua determinada lista
}  

System.out.println(table);

System.out.println("Valores gerados:");  
for(Integer i : valores) System.out.println(i);[/code]

Por exemplo, eu pedi para gerar 10 números, em um universo de 100, ou seja, que variam de 0 à 100.
Obtive o seguinte resultado:
{0=[30], 2=[72, 72], 3=[13], 4=[34, 74], 5=[25], 7=[47, 37, 87], 9=[99]}
Valores gerados:
34
87
99
37
25
72
13
47
74
30

O programa gerou os 10 números sem repetição de números, mas na lista 2, ele tem o número 72 repetido. Não consegui descobrir o motivo disso.

E fica pior quando coloco para gerar 10 números entre 10 possiveis.
Fica assim:
{0=[0, 0, 0], 1=[1, 1], 2=[2, 2, 2, 2], 3=[3, 3, 3, 3, 3, 3], 4=[4], 5=[5, 5, 5, 5], 6=[6, 6, 6], 7=[7, 7, 7], 8=[8], 9=[9]}
Valores gerados:
0
1
2
3
4
5
6
7
8
9

Alguém sabe me dizer o que estou fazendo de errado?

E queria agradecer mais uma vez o pmlm, sem a ajuda dele estaria na estaca ZERO.
Obrigado!!!

#13

O teu problema está na geração dos números aleatórios.
Usas um set para evitar a repetição mas, mesmo quando aparece um número repetido executas o add na hashtable.

A minha sugestão é para que não uses o random para gerar os números aleatórios mas cries uma lista de inteiros com os números de 1 até universoKey.
Depois fazes Collecions.shuffle e obtens os primeiros tamVet elementos.

#14

[quote=pmlm]O teu problema está na geração dos números aleatórios.
Usas um set para evitar a repetição mas, mesmo quando aparece um número repetido executas o add na hashtable.

A minha sugestão é para que não uses o random para gerar os números aleatórios mas cries uma lista de inteiros com os números de 1 até universoKey.
Depois fazes Collecions.shuffle e obtens os primeiros tamVet elementos.[/quote]

Eu acho que estou no caminho certo, mas estou com dificuldade para ele sortear apenas determinados numeros, na verdade não sei como fazer direito, segue o código:

[code]
HashMap<Integer, List> table= new HashMap<Integer, List>();

 int tamVet = 0;    
 tamVet = Integer.parseInt(JOptionPane.showInputDialog(null, "Entre com a Quantidade de Números a serem Gerados:"));    
 if (tamVet == 0) {    
     JOptionPane.showMessageDialog(null,"O tamanho não poder ser 0, Saindo do sistema.");    
     System.exit(0);    
 }    

 int UniversoKey = 0;    
 UniversoKey = Integer.parseInt(JOptionPane.showInputDialog(null, "Entre o universo de Chaves:"));    
 if (UniversoKey == 0) {    
     JOptionPane.showMessageDialog(null,"O tamanho não poder ser 0, Saindo do sistema.");    
     System.exit(0);    
 }

Set valores = new HashSet();
List lista = new ArrayList () ;
for ( int i = 1 ; i <= UniversoKey ; i++ ){ // de 1 até UniversoKey
lista.add ( new Integer ( i )) ;

Collections.shuffle ( lista ) ;                 
        
    int key = i %tamVet;      
        
    if (table.get(key)==null){ //Então verifica se já existe na hashtable a lista do número,senão existe cria uma nova lista desse número     
        table.put(key, new ArrayList<Integer>());    
    }    
    table.get(key).add(i); //adiciona o número em sua determinada lista  
}

System.out.println(“Valores gerados:” + lista);

System.out.println(“Números Listados:” + table); [/code]

Ele esta gerando os códigos de 1 até universoKey, por exemplo se coloco que UniversoKey é 20, ele vai gerar numeros de 1 a 20. Mas a minha váriavel tamVet me diz quantos numeros quero sortear desses 20. O que eu preciso alterar no código para fazer isso?
Eu sou meio fraquinho mesmo em programação, to apanhando um bocado…

#15

Precisas de dois for… primeiro um só para preencher a lista.
Depois é que fazes o shuffle
E depois novo for para obter a quantidade de números que pretendes. E neste é que adicionas à tua hashtable.

#16

[quote=pmlm]Precisas de dois for… primeiro um só para preencher a lista.
Depois é que fazes o shuffle
E depois novo for para obter a quantidade de números que pretendes. E neste é que adicionas à tua hashtable.[/quote]

Como vc faria isso? falta lógica de programação para mim…infelizmente.

#17

Agora eu teria que pesquisar um determinado numero na minha lista.
Receber um numero, então eu faço mod dele e descubra em qual lista ele esta, e nesta lista dizer em qual posição.
Por exemplo essa lista:

{2=[9], 3=[10, 45], 4=[39, 25, 46], 6=[48]}

Gerei 7 números entre 1 e 51, então fica mod 7.
Se eu quisesse pesquisar o numero 25, faria 25 mod 7, que dá 4, então ele esta na lista 4, como mostra acima, e teria que dizer que ele esta na lista 4, posição 2.
Algo do tipo.
Alguém me dá uma ajuda?

#18 
int numero = ... //o numero a pesquisar

int numeroDaLista = ... //obtido com o modulo do numero

List<Integer> list = hashtable.get(numerodaLista);

for (Integer n:list){
    if (n==numero){
     //encontras-te o número. Só tens de colocar um contador para saber qual a posição na lista
    }
}
#19

[quote=pmlm][code]
int numero = … //o numero a pesquisar

int numeroDaLista = … //obtido com o modulo do numero

List list = hashtable.get(numerodaLista);

for (Integer n:list){
if (n==numero){
//encontras-te o número. Só tens de colocar um contador para saber qual a posição na lista
}
}

[/code][/quote]

Funcionou perfeitamente, nem sei como te agradecer, coloquei o contador e ficou perfeito. Muito Obrigado!!

Só fiquei com uma dúvida, meu código ficou assim, na parte de procura:

[code]procura = Integer.parseInt(JOptionPane.showInputDialog(null, “Digite o Valor que deseja procurar:”));

int numeroDaLista = procura % tamVet;  
  
List<Integer> list = table.get(numeroDaLista);  
int j = 0;  
for (Integer n:list){  
	j++;
    if (n==procura){  
     //encontras-te o número. Só tens de colocar um contador para saber qual a posição na lista  
    	
    	System.out.println("O Número esta na lista: " + numeroDaLista);
    	System.out.println("Na posição: " + j);[/code]

eu alterei hashtable.get , para table.get , que é o nome da nossa tabela certo?
Acima no código haviamos definido table como:

HashMap<Integer, List<Integer>> table= new HashMap<Integer, List<Integer>>();

Se eu alterar de HashMap para Hashtable também funciona.
Só não sei qual a diferença dos 2? qual seria melhor eu utilizar?

#20

Basicamente são a mesma coisa.
Hashtable é a classe original do Java, o acesso a dados é sincronizado (para acessos em multithread).
O Hashmap foi introduzido no Java 2 e na maioria das vezes é o indicado para usar (acesso single thread)