Ricerca efficiente

[Ottavioinfo]

Ciao a tutti,
avrei bisogno di memorizzare in una struttura tipo HashMap un'insieme di migliaia di oggetti.
Ovviamente la ricerca poò essere onerosa.
Secondo voi una struttura come la hashmap va bene? o TreeSet o altro?
Grazie

[VincenzoTheBest]

Ti conviene usare una struttura lineare nella quale l'ordine è significativo (ES: Lista) e ciò ti consentirà di effettuare ricerche binarie; senz'altro la ricerca binaria è più efficiente della ricerca sequenziale in termini di complessità computazionale.

[Ottavioinfo]

Originariamente inviato da VincenzoTheBest
Ti conviene usare una struttura lineare nella quale l'ordine è significativo (ES: Lista) e ciò ti consentirà di effettuare ricerche binarie; senz'altro la ricerca binaria è più efficiente della ricerca sequenziale in termini di complessità computazionale.

Ma la lista è è troppo complessa: se per ipotesi l'elemento da cercare è l'ultimo, dovrò scorrere tutti gli oggetti. In questo caso sarebbe meglio un albero binario no?
Ma comunque io cercavo una struttura glia fatta, non la voglio scrivere io con tutti gli algoritmi

[VincenzoTheBest]

Guarda che la ricerca binaria non fa lo scan di tutti gli elementi! La stai confondendo con la ricerca sequenziale.

Inoltre in java le liste sono state implementate usando gli array (ArrayList) ed usando le strutture collegate (LinkedList)!

[Ottavioinfo]

Originariamente inviato da VincenzoTheBest
Guarda che la ricerca binaria non fa lo scan di tutti gli elementi! La stai confondendo con la ricerca sequenziale.

Inoltre in java le liste sono state implementate usando gli array (ArrayList) ed usando le strutture collegate (LinkedList)!

Quindi scusa in che modo farei la ricerca binaria? supponiamo che ho n elementi ed ogniuno dei quali ha una chiave, dove li metteresti?

[VincenzoTheBest]

Originariamente inviato da Ottavioinfo
Quindi scusa in che modo farei la ricerca binaria? supponiamo che ho n elementi ed ogniuno dei quali ha una chiave, dove li metteresti?

Beh se ognuno ha una chiave allora la domanda nemmeno devi porla! Usi l'HashMap.

[Ottavioinfo]

Originariamente inviato da VincenzoTheBest
Beh se ognuno ha una chiave allora la domanda nemmeno devi porla! Usi l'HashMap.

Ma forse non mi sono spiegato bene: con l'HashMap se metto migliaia di oggetti, la get è efficiente o esiste una struttura migliore?

[VincenzoTheBest]

Originariamente inviato da Ottavioinfo
Ma forse non mi sono spiegato bene: con l'HashMap se metto migliaia di oggetti, la get è efficiente o esiste una struttura migliore?

Si i tempi degli operatori get e put (della classe HashMap) sono costanti!

This implementation provides constant-time performance for the basic operations (get and put)

[Ottavioinfo]

Lo sai che hai proprio ragione... i tempi della get sono costanti, sia che nell'HashMap ci siano 100 elementi, sia che ce ne siano 1.000.000.
Ho fatto infatti un test inserendo 2 milioni di oggetti in un'hashmap e la risposta è immediata.
Mi domando ora ma come fa? daccordo che la ricerca non è sequenziale ma quale algoritmo è cosi veloce nella ricerca?
Grazie

[LeleFT]

Originariamente inviato da Ottavioinfo
Lo sai che hai proprio ragione... i tempi della get sono costanti, sia che nell'HashMap ci siano 100 elementi, sia che ce ne siano 1.000.000.
Ho fatto infatti un test inserendo 2 milioni di oggetti in un'hashmap e la risposta è immediata.
Mi domando ora ma come fa? daccordo che la ricerca non è sequenziale ma quale algoritmo è cosi veloce nella ricerca?
Grazie

Semplice: si calcola un hash della chiave (che è un valore numerico, vedi il metodo hashCode() della classe Object, che tutti gli oggetti "dovrebbero" ridefinire) e si utilizza questo valore come indice in un array. Non c'è alcuna ricerca da fare: l'accesso ad un elemento di un array (di cui si conosce la posizione, ovvero l'hash) è un'operazione che non richiede alcun costo computazionale (o meglio, un costo costante).


Ciao.