[JAVA]: Scansione di un Hashtable (come un Vector)

[stex1984]

2 quesiti:

il primo:
è possibile scandire una hashtable come un vector?
ad esempio il vector io lo analizzo cosi:

for (i = 0 ; i < vettore.size(); i++)

si può fare una cosa simile con le hashtable?

il secondo:
se si può fare il punto uno, quale delle due soluzioni è più veloce?

grazie ciao

[andbin]

Originariamente inviato da stex1984
è possibile scandire una hashtable come un vector?
ad esempio il vector io lo analizzo cosi:

for (i = 0 ; i < vettore.size(); i++)

si può fare una cosa simile con le hashtable?

No, però puoi ottenere da una Hashtable una enumerazione delle chiavi o dei valori. Ti consiglio di guardare bene la documentazione della classe Hashtable.

[engiman]

Anche HashTable ha il metodo size(), per cui il ciclo for funzionerebbe.

Tuttavia non è possibile utilizzare l'indice i per accedere alla HashTable, che è una Map e quindi è indicizzata tramite chiavi e non conserva l'ordine di inserimento.

Per questo motivo non è corretto paragonare Vector e HashTable: il primo memorizza oggetti mantenendo l'ordine di inserimento (è una List), mentre la seconda memorizza coppie chiave-oggetto (è una Map).

La Collection più simile a Vector è ArrayList, che è più performante in quanto non sincronizzata e che puoi accedere con get(int index).

In ogni caso tutte le Collection (Vector è una Collection) si scorrono tramite un Iterator: se la Collection non è una List (Vector è una List), l'ordine di inserimento non è garantito.

for (Iterator iter=vettore.Iterator(); iter.hasNext(); ) {
     Object o=iter.next();
     // l'oggetto o è disponibile
}

Iterator iter=vettore.Iterator();
while (iter.hasNext()) {
     Object o=iter.next();
     // l'oggetto o è disponibile
}

[stex1984]

quindi mi stai dicendo che un arraylist è pià veloce di un vector?
e tra le list qual'è la più veloce?

ah, e se nella hashtable come chiave memorizzo un indice che funge da contatore, posso sviluppare cosi il for?

for (int i = 0 ; i < table.size(); i++)
{
 oggetto o=table.get(i);
}

il get(key) della hashtable è più veloce della get(index) di una list in generale?

grazie

[engiman]

Prima questione: ArrayList o Vector ?

ArrayList è più veloce di Vector.
La differenza è data dal fatto che Vector è sincronizzata. La differenza di velocità è notevole nel caso di accesso contemporaneo da due thread e trascurabile per accessi non contemporanei.
La regola che uso è: ArrayList sempre, a meno che non ci sia la necessità di avere la sincronizzazione.

Per misurare la velocità in caso di accessi non contemporanei, prova:

import java.util.List;
import java.util.Vector;
import java.util.ArrayList;
import java.util.Iterator;

public class TestVelocita {
	public static void main (String[] args) {
		List lista;
		int n = 5000000;
		int i;
		long elapsed;
		Object o = new Object();
		if (args.length==0) {
			System.out.println("Uso: java TestVelocita [vector|arraylist] [numero oggetti]");
		} else {
			if (args[0].toUpperCase().equals("VECTOR")) {
				lista = new Vector();
			} else {
				lista = new ArrayList();
			}
			
			if (args.length==2) {
				n = Integer.parseInt(args[1]);
			}

			elapsed=System.currentTimeMillis();
			for (i=0; i<=n; i++) {
				lista.add(o);
			}
			elapsed=System.currentTimeMillis()-elapsed;
			System.out.println("Tempo di inserimento: " + elapsed + " ms");

			elapsed=System.currentTimeMillis();
			for (i=0; i<=n; i++) {
				o=lista.get(i);
			}
			elapsed=System.currentTimeMillis()-elapsed;
			System.out.println("Tempo di accesso sequenziale tramite indice: " + elapsed + " ms");

			elapsed=System.currentTimeMillis();
			for (Iterator iter=lista.iterator(); iter.hasNext(); ) {
				o=iter.next();
			}
			elapsed=System.currentTimeMillis()-elapsed;
			System.out.println("Tempo di accesso sequenziale tramite Iterator: " + elapsed + " ms");
		}
	}
}

Sulla mia macchinetta è:

D:\Sviluppo\Test>java TestVelocita vector
Tempo di inserimento di 5000000 oggetti: 468 ms
Tempo di accesso tramite indice a 5000000 oggetti: 94 ms
Tempo di accesso tramite Iterator a 5000000 oggetti: 250 ms

D:\Sviluppo\Test>java TestVelocita arraylist
Tempo di inserimento di 5000000 oggetti: 641 ms
Tempo di accesso tramite indice a 5000000 oggetti: 79 ms
Tempo di accesso tramite Iterator a 5000000 oggetti: 234 ms

Quando ho tempo, faccio un programmino di prova da due thread contemporaneamente.

Seconda questione

Se nella hashtable come chiave memorizzo un indice che funge da contatore, posso sviluppare cosi il for?

for (int i = 0 ; i < table.size(); i++)
{
 oggetto o=table.get(i);
}

No: le chiavi sono oggetti, non int. HashTable non ha un metodo get(int index), ma ha il metodo get (Object o).
Dunque devi fare:

for (int i = 0 ; i < table.size(); i++)
{
 Object o=table.get(new Integer(i));
}

e hai in più l'overhead della creazione di un Integer.

Per HashTable e HashMap, vale la stessa considerazione fatta per Vector e ArrayList: usa sempre la seconda, a meno che non ti serve la sincronizzazione.

Nelle applicazioni che non usano queste Collection in modo particolarmente spinto, la questione è comunque puramente accademica, in quanto non si noterebbe comunque la differenza tra le diverse implementazioni. La regola è di non ottimizzare codice già scritto a meno che non si notano problemi prestazionali o a meno che non stai scrivendo codice per farlo vedere a un professore.

Terza questione
Il metodo get() di una List non è detto che sia velocissimo: il get() un ArrayList è imbattibile, perché è come accedere un array. Il get() di LinkedList può essere lento, perchè deve scorrere tutta la lista. Il get() di HashTable (o HashMap) usa prima l'hashcode dell'oggetto per restringere la ricerca a un solo bucket (l'insieme degli oggetti che hanno lo stesso hashcode) e poi ricerca la chiave: può avere prestazioni intermedie. Comunque ripeto che ArrayList (che è una List) e HashTable (che è una Map) non sono confrontabili, perchè sono strutture diverse e si usano in condizioni diverse.

[stex1984]

ciao, innanzitutto grazie 1000 per la esaustiva risposta...
una cosa non ho capito...
sul mio pc i risultati sono questi:
con vector
Tempo di inserimento: 578 ms
Tempo di accesso sequenziale tramite indice: 94 ms
Tempo di accesso sequenziale tramite Iterator: 297 ms
con arraylist
Tempo di inserimento: 734 ms
Tempo di accesso sequenziale tramite indice: 125 ms
Tempo di accesso sequenziale tramite Iterator: 266 ms

da quello che riesco a capirne è che il vector è + veloce! sia in inserimento che in get(index)...

allora ciò che non capisco è perchè mi dici che arraylist è più veloce... possibile che dipende anche dal pc?
io ho un notebook con amd64 3200+, 1gb ram ddr, hdd 80gb 7200rpm, ati 9600 64mb...

scusami se insisto, ma siccome nel mio programma ho bisogno di alte prestazioni, vorrei ben capire i concetti!!!

grazie

[stex1984]

ho fatto qualche altra prova...
se vuoi valutare...
sono fatte tutte con lo stesso numero di oggetti pari a 5000000

VECTOR
Tempo di inserimento: 453 ms
Tempo di accesso sequenziale tramite indice: 78 ms
Tempo di accesso sequenziale tramite Iterator: 250 ms
ARRAYLIST
Tempo di inserimento: 985 ms
Tempo di accesso sequenziale tramite indice: 109 ms
Tempo di accesso sequenziale tramite Iterator: 500 ms

VECTOR
Tempo di inserimento: 422 ms
Tempo di accesso sequenziale tramite indice: 78 ms
Tempo di accesso sequenziale tramite Iterator: 250 ms
ARRAYLIST
Tempo di inserimento: 1000 ms
Tempo di accesso sequenziale tramite indice: 125 ms
Tempo di accesso sequenziale tramite Iterator: 484 ms

VECTOR
Tempo di inserimento: 500 ms
Tempo di accesso sequenziale tramite indice: 94 ms
Tempo di accesso sequenziale tramite Iterator: 234 ms
ARRAYLIST
Tempo di inserimento: 1000 ms
Tempo di accesso sequenziale tramite indice: 109 ms
Tempo di accesso sequenziale tramite Iterator: 500 ms

ARRAYLIST
Tempo di inserimento: 656 ms
Tempo di accesso sequenziale tramite indice: 109 ms
Tempo di accesso sequenziale tramite Iterator: 235 ms
VECTOR
Tempo di inserimento: 703 ms
Tempo di accesso sequenziale tramite indice: 94 ms
Tempo di accesso sequenziale tramite Iterator: 250 ms

ARRAYLIST
Tempo di inserimento: 656 ms
Tempo di accesso sequenziale tramite indice: 109 ms
Tempo di accesso sequenziale tramite Iterator: 235 ms
VECTOR
Tempo di inserimento: 687 ms
Tempo di accesso sequenziale tramite indice: 94 ms
Tempo di accesso sequenziale tramite Iterator: 250 ms

ARRAYLIST
Tempo di inserimento: 672 ms
Tempo di accesso sequenziale tramite indice: 110 ms
Tempo di accesso sequenziale tramite Iterator: 234 ms
VECTOR
Tempo di inserimento: 688 ms
Tempo di accesso sequenziale tramite indice: 93 ms
Tempo di accesso sequenziale tramite Iterator: 250 ms

ARRAYLIST
Tempo di inserimento: 672 ms
Tempo di accesso sequenziale tramite indice: 109 ms
Tempo di accesso sequenziale tramite Iterator: 234 ms
VECTOR
Tempo di inserimento: 672 ms
Tempo di accesso sequenziale tramite indice: 110 ms
Tempo di accesso sequenziale tramite Iterator: 250 ms