[JAVA] Problema con la HashMap

[andbin]

Ciao, sto sviluppando un programma in Java che dovrebbe poi permettermi di elaborare tutta una serie di statistiche sulle estrazioni del Lotto (ho tutto lo storico dal 1939!). Ho già scritto parecchie classi ma sto avendo un problema con le HashMap e non riesco a capire perché. Naturalmente non posto tutto il codice (sarebbe troppo lungo) ma solo un pezzettino che ho rifatto a mo' di test:

import java.lang.*;
import java.util.*;

class Terno
{
    private byte[] numeri;

    public Terno (byte n1, byte n2, byte n3)
    {
        numeri = new byte[3];

        numeri[0] = n1;
        numeri[1] = n2;
        numeri[2] = n3;
    }

    public boolean equals (Terno t)
    {
        for (int i=0; i<3; i++)
            if (numeri[i] != t.numeri[i])
                return false;

        return true;
    }

    public int hashCode ()
    {
        return ((int) numeri[2]) * 8100 + ((int) numeri[1]) * 90 + ((int) numeri[0]);
    }

    public String toString ()
    {
        return numeri[0] + ", " + numeri[1] + ", " + numeri[2];
    }
}


public class ProvaTerno
{
    public static void main (String argv[])
    {
        HashMap map = new HashMap (704880);
        int n = 0;

        for (byte i=1; i<=90; i++)
        {
            for (byte j=1; j<=90; j++)
            {
                for (byte k=1; k<=90; k++)
                {
                    if (i != j && j != k && i != k)
                    {
                        Terno t = new Terno (k, j, i);

                        map.put (t, "aaa");
                        n++;
                    }
                }
            }
        }

        System.out.println ("Inseriti: " + n);
        System.out.println ("Dimensione map: " + map.size ());

        Terno t = new Terno ((byte) 5, (byte) 6, (byte) 7);

        System.out.println (t.toString () + (map.containsKey (t) ? " contenuto" : " non contenuto"));
    }
}

In pratica ho una semplice classe Terno che contiene 3 numeri. Ridefinisco i metodi equals(), hashCode() e toString().
Nel main creo un HashMap con capacità di 704880 (che sono tutte le possibili combinazioni per un Terno, prendendo i numeri da 1 a 90 senza ripetizioni e ignorando l'ordine) e poi ci metto nell'HashMap tutte le combinazioni una per una. Come valore ho messo "aaa" tanto per provare (io dovrò metterci un altro oggetto).
Alla fine vado a vedere se è contenuto il Terno 5,6,7.

Avviando questo programma ottengo:

Inseriti: 704880
Dimensione map: 704880
5, 6, 7 non contenuto

In pratica non trova il Terno. Ma non lo trova nemmeno se faccio esplicitamente:

map.put (new Terno ((byte) 5, (byte) 6, (byte) 7), "aaa");

ed è questo che è strano!
Cosa può essere?? Forse il metodo hashCode non è giusto??
Uso il JDK 1.4.2_08-b03.

[sottovento]

Ciao
non ho avuto tempo e modo di verificare approfonditamente, ma vorrei esporti alcuni suggerimenti:

- (C'entra poco) 704880 e' il numero di ripetizioni che ottieni TENENDO CONTO dell'ordine. Infatti ottieni questo numero scrivendo sia (1,2,3) sia (3,2,1) e considerandole differenti. Se dividi questo numero per 3! = 6, allora ottieni il numero delle combinazioni senza ripetizione che non tiene conto dell'ordine, cioe' proprio
n!/(k! * (n-k)!) (il binomiale) = 117480

- Da quello che ho capito (purtroppo non sono ancora passato alla j5), questa HashMap va a controllare il "Riferimento" all'oggetto (visto che sei programmatore C/C++, il puntatore). Lui non sa quale procedure utilizzare per la comparazione e non la ridefinisci scrivendo una equals(obj) nell'oggetto da memorizzare.
Ad orecchio, visto che la HashMap implementa la Map(), immagino che dovrai estendere la HashMap, mettendoci la TUA implementazione della suddetta procedura.

Fammi sapere

High Flying
Sottovento

[kingv]

di sicuro hai sbagliato a ridefinire "equals".
Devi fare l'overriding di quello con firma:

public boolean equals(Object obj)

[andbin]

Originariamente inviato da sottovento

- (C'entra poco) 704880 e' il numero di ripetizioni che ottieni TENENDO CONTO dell'ordine. Infatti ottieni questo numero scrivendo sia (1,2,3) sia (3,2,1) e considerandole differenti. Se dividi questo numero per 3! = 6, allora ottieni il numero delle combinazioni senza ripetizione che non tiene conto dell'ordine, cioe' proprio
n!/(k! * (n-k)!) (il binomiale) = 117480

Scusa ... quando ho detto "ignorando l'ordine" mi sono espresso male. Io intendevo dire appunto che in un Terno, le combinazioni 1,2,3 e 3,2,1 sono la stessa cosa e quindi non differenti. Sai, non sono esperto di calcolo combinatorio!

[andbin]

Originariamente inviato da kingv

di sicuro hai sbagliato a ridefinire "equals".
Devi fare l'overriding di quello con firma:

public boolean equals(Object obj)

Sì, è proprio così! Solo qualche minuto dopo aver postato mi è venuto in mente che il problema era nella equals. Siccome mi capita raramente di dover ridefinire equals(), mi sono confuso, visto che ero già un po' ... fuso.
L'ho corretto e funziona. Grazie.

[andbin]

Ragazzi ... l'altro giorno che ho postato il codice penso di aver "cannato" (di brutto) il calcolo delle combinazioni, vero???
Ho ripreso una mia guida sul Calcolo Combinatorio ed ho visto che in realtà il numero esatto di combinazioni per un terno al lotto è di 117480 e non 704880!!!
Infatti nel primo caso (117480) si parla di "combinazioni senza ripetizioni" mentre nel secondo caso (704880) si parla di "disposizioni senza ripetizioni".
Io in effetti nel codice:

for (byte i=1; i<=90; i++)
{
    for (byte j=1; j<=90; j++)
    {
        for (byte k=1; k<=90; k++)
        {
            if (i != j && j != k && i != k)
            {
                ...
            }
        }
    }
}

eliminavo le ripetizioni grazie al test nel if ma non le varie disposizioni!!!
Ho quindi pensato un attimo a come eliminare anche le disposizioni ed ho modificato semplicemente il test così:

if (i < j && j < k)

In questo modo elimino ripetizioni e disposizioni. Giusto?

[sottovento]

Penso sia meglio modificare i cicli for:
- il for piu' lento (i) va da 1 a 88;
- il for medio (j) va da i + 1 a 89;
- il for piu' veloce (k) va da j+1 a 90;

High Flying
Sottovento

[kingv]

Originariamente inviato da sottovento

Penso sia meglio modificare i cicli for:
- il for piu' lento (i) va da 1 a 88;
- il for medio (j) va da i + 1 a 89;
- il for piu' veloce (k) va da j+1 a 90;

High Flying
Sottovento

esatto, è piu' elegante e ti risparmi un bel po' di iterazioni:

for (int i=1; i<=90; i++)
{
    for (int j=i+1; j<=90; j++)
    {
       for (int k=j+1; k<=90; k++)
        {
                        Terno t = new Terno ((byte)i, (byte)j, (byte)k);
                        map.put (t, "aaa");
                        n++;
        }
    }
}

[andbin]

Giustissimo!!! Avrei dovuto pensarci subito (ci sarei arrivato eh! )
Grazie a tutti e due (sottovento e kingv).
In effetti così si risparmiano molto cicli (non che debba avere chissà quali prestazioni comunque, è un programmino "didattico", ma è sicuramente una miglioria).

[kingv]

ho riletto quello che ho scritto, gli indici giusti sono quelli suggeriti da sottovento, funzionalmente non cambia nulla ma ti risparmi ancora qualche ciclo