Utilizzo di ArrayList o HashMap

Question

Ciao Ho una domanda sull'utilizzo di un ArrayList o HashMap.

Sto provando a creare un programma Paint. Ad ogni oggetto disegnato verrà assegnato un oggetto univoco ID.

Se desidero una velocità di recupero veloce quando faccio clic su un oggetto, dovrei utilizzare uno arraylist o hashmap?

In generale hashmap ha O (1) mentre l'arrailista ha O (n) velocità di recupero.

Tuttavia, penso per il mio caso, poiché quando clicco su un oggetto, otterrò l'ID, quindi l'indice dell'array e posso fare qualcosa come ArraylistObject.get (ithElement); , quindi in questo caso anche questo sarà un processo di recupero di O (1)?

eventuali ingressi?

Grazie!

Answer 1

Se gli oggetti hanno un ID che può essere mappato 1-a-1 su un array di quello che sarà O (1), in pratica sarà leggermente più veloce di una ricerca hashmap (non hai calcolare l'hash).

Tuttavia, il problema sarà ciò che accade quando si elimina un oggetto. Rimarrai con un buco nella lista. Quando crei nuovi oggetti, puoi quindi accodare l'elenco e lasciarlo lentamente più frammentato o cercare di trovare uno slot di riserva, nel qual caso effettuerai una ricerca O (n) di uno spazio libero.

In breve: una hashmap è probabilmente più appropriata.

Answer 2

Tra i lati positivi, potresti essere in grado di ottenere un po 'di prestazioni extra eseguendo ArrayList nel modo giusto. Ma l'eliminazione degli oggetti sarà un dolore reale - come hanno detto Paolo e Anurag, o dovrai mettere un segnaposto vuoto (null?) O rinumerare qualche altro oggetto per riempire il vuoto. Ciò potrebbe causare bug di prestazioni e semplici bug vecchi.

HashMaps, d'altra parte. Semplicità d'uso, prestazioni decenti garantite (a meno che non si assegnino i propri ID in modo grave).

E il recupero degli oggetti tramite ID potrebbe non essere affatto il collo di bottiglia dell'applicazione. Come dice il proverbio, l'ottimizzazione prematura è la radice di tutti i mali.

Answer 3

Se si può garantire che gli ID saranno in un intervallo relativamente piccolo numerico, quindi si dovrebbe utilizzare una matrice semplice (con la dimensione preinizializzati al massimo ID), piuttosto che un ArrayList. Ciò garantisce che non rimuoviate accidentalmente le voci e spostate tutto il resto per colmare il divario, con ogni cosa che finisce con un indice sbagliato. Un array semplice sarà anche un po 'più veloce di un ArrayList.

Se non è possibile fornire tale garanzia, utilizzare una HashMap. È molto improbabile che la differenza di velocità sia evidente e sarà più facile da mantenere.