HashMap e doppioni fantasma

[Pierock]

Salve ragazzi... per caso qualcuno mi saprebbe spiegare questo? .. io oramai sono davvero in panne... vi confesso ke questo problema proprio non lo so gestire...

public static void main(String[] arg){

     HashMap<Integer,Float> MAP2 =new HashMap<Integer,Float>(); 
     int dim= 67000; 

            for(int i=0;i<dim;i++){ 
                 int code = makeHash(i,i,dim); 
                 MAP2.put(code, 4.5f); 
             }

      int cont=0;
		
		for(int i=0;i<dim;i++){
			for(int j=0;j<dim;j++){

				int code = makeHash(i,j,dim);
				if(MAP2.containsKey(code))
				cont++;
			}
		}

		System.out.println(" fatto"+cont);

}

static int makeHash(int i, int j,int n){
		int code=(i*n)+j;
		return code;
	}

in sostanza effettuo dim=67000 inserimenti in un hashmap, e subito dopo, simulando che MAP sia una matrice quadrata, conto quanti valori non nulli contiene...
e .. attenzione attenzione...
il risultato è...

fatto 72792

questo "odioso" fenomeno non si presenta per valori minori di dim , ma peggiora per valori più alti !!!
come devo fare?

[LeleFT]

Originariamente inviato da Pierock
in sostanza effettuo dim=67000 inserimenti in un hashmap, e subito dopo, simulando che MAP sia una matrice quadrata, conto quanti valori non nulli contiene...
e .. attenzione attenzione...
il risultato è...

fatto 72792

questo "odioso" fenomeno non si presenta per valori minori di dim , ma peggiora per valori più alti !!!
come devo fare?

Calma: da quelo che vedo io tu fai 67000 inserimenti, ma 67000 * 67000 controlli... e fai avanzare la variabile "cont" ogni volta che trovi nella HashMap il valore del tuo hash (i, j, dim).

Con i che va da 0 a 66999 e j che va da 0 a 66999. Quante volte accade che i e j siano lo stesso valore e, di conseguenza, abbiano lo stesso hash? 67000 volte. Quante volte accade che i e j siano diversi ma producano lo stesso hash? Evidentemente 5792 volte.

Questo significa che la tua funzione di hash non è tanto buona... infatti, tante volte quell'espressione andrà in "overflow", che Java controlla...


Ciao.

[Pierock]

NO no.. aspetta....
forse sto prendendo una tremenda cantonata, ma ... non può essere come dici tu!!!

ti spiego un attimo l'analogia... dovo realizzare una matrice quadrata (molto molto grande) di cui gli unici elementi non nulli sono lungo la sua diagonale, quindi volevo simulare una struttura a matrice con un hashmap, inserendo esclusivamente i valori non nulli....

per questo motivo (se te lo stavi chiedendo) aggiungo dim=67000 elementi, e successivamente, per controllare che tutto sia andato a buon fine , effettuo dim*dim!

riguardo alla questione di un probabile overflow, ho paura che non sia così, in quanto, considerando una generica matrice A di dimensioni n x n ...
l'indirizzo di ogni generica cella (i,j) della matrice dovrebbe appunto essere i*n+j...così come impostato nella mia funzione makeHash ... quindi escludo categoricamente l'overflow

a dimostrazione di quanto dico.....
aggiungendo queste 2 righe al codice...

   for(int j=0;j<dim;j++){
         int code = makeHash(0,j,dim);
         if(MAP2.containsKey(code)) 
               System.out.print(" "+MAP2.get(code)+"("+j+")"); 
}

verifico a quale indice di riga ho il primo doppione... e guarda caso... la risposta è:


4.5(0) 4.5(64808) ... quindi.. considerando ke il mio hash è dato dall'equazione

i*67000+j .... come fa ad essere uguale a 64808 considerando che i e j sono sempre uguali all'inserimento??

e poi ... se ci fosse un overflow... ci dovrebbe essere anche se utilizzo dim<67000 !

quindi che devo fare??? come me la spiccio?

[LeleFT]

Scusa, ma:

for(int i=0;i<dim;i++){
   for(int j=0;j<dim;j++){
      int code = makeHash(i,j,dim);
      if(MAP2.containsKey(code))
         cont++;
   }
}

Cosa succede nell'ultimo passaggio dei due for annidati? Questo:

makeHash(66999, 66999, 66999);

E makeHash:

int code=(i*n)+j;

ovvero:

int code = (66999 * 66999) + 66999;
= (4488866001) + 66999

Ora, considerando che il più grande numero rappresentabile da un int è (2 ^ 31) - 1, ovvero 2147483647... capirai bene che il numero tra parentesi è decisamente più grande.

Quindi non escluderei l'overflow.

Poi, come già detto, Java controlla questa tipologia di errori e fa rientrare tutto nel range di valori ammissibili, ma questo è un altro discorso.

Non a caso, il numero di celle di una matrice 67000 x 67000 è 4489000000 che non è rappresentabile mediante un int. Prova ad usare un long e vedrai che funziona.

Ciao.

[Pierock]

forse sto prendendo una tremenda cantonata, ma ...

.. come non detto!

grazie mille LeleF