Quale implementazione della mappa <K,V> dovrei usare se la mia mappa deve essere più piccola che veloce?

Question

Io uso abitualmente lo HashMap nei miei programmi, poiché so che di solito è il più efficiente (se usato correttamente) e può gestire facilmente mappe di grandi dimensioni. So di EnumMap che è molto utile per le chiavi di enumerazione, ma spesso sto generando una piccola mappa che non diventerà mai molto grande, è probabile che venga scartata molto presto e non ha problemi di concorrenza.

È HashMap<K,V> troppo complicato per questi piccoli usi locali e temporanei? C'è un'altra implementazione semplice che posso usare in questi casi?

Penso che sto cercando un'implementazione Map che è analoga a ArrayList per List. Esiste?

---

aggiunta più tardi, dopo le risposte:

Qui è uno scenario in cui un lento ma molto semplice implementazione potrebbe essere meglio - quando ho molti, molti di questi Map s. Supponiamo, per esempio, che io abbia un milione o più di queste piccole mappe minuscole, ciascuna con una manciata (spesso meno di tre) di voci. Ho un basso tasso di riferimento, forse non li faccio effettivamente riferimento prima che vengano scartati la maggior parte del tempo. È ancora il caso che HashMap è la scelta migliore per loro?

L'utilizzo delle risorse è più della semplice velocità: mi piacerebbe qualcosa che non frammentasse molto l'heap e facesse sì che i GC impiegassero molto tempo, ad esempio.

È possibile che HashMap sia la risposta corretta, ma questo non è un caso di ottimizzazione prematura (o almeno potrebbe non esserlo).

---

aggiunto molto più tardi, dopo qualche pensiero:

ho deciso di mano il codice mia SmallMap. È facile crearne uno con AbstractMap. Ho anche aggiunto un paio di costruttori in modo che un SmallMap possa essere costruito da uno esistente Map.

Lungo la strada ho dovuto decidere come rappresentare Entry se implementare SmallSet per il metodo entrySet.

Ho imparato molto dalla codifica (e dall'unità di test questo) e voglio condividere questo, nel caso che qualcun altro ne voglia uno. È su github here.

Answer 1

Non esiste alcuna piccola implementazione standard di Map in Java. HashMap è una delle migliori e più flessibili implementazioni Map disponibili ed è difficile da battere. Tuttavia, nella ristretta area dei requisiti, in cui l'utilizzo dell'heap e la velocità di costruzione sono fondamentali, è possibile fare di meglio.

Ho implementato SmallCollections su GitHub per dimostrare come ciò potrebbe essere fatto. Vorrei amore alcuni commenti sul fatto che ci sono riuscito. Non è affatto sicuro di averlo.

Sebbene le risposte qui offerte fossero a volte utili, tendevano, in generale, a fraintendere il punto. In ogni caso, rispondere alla mia domanda era, alla fine, molto più utile per me che essere dato a qualcuno.

La domanda qui è servita al suo scopo ed è per questo che ho "risposto da solo".

Answer 2

Penso che questo sia l'ottimizzazione prematura. Stai avendo problemi di memoria? Problemi di prestazioni dalla creazione di troppe mappe? Se no, penso che HashMap stia bene.

Inoltre, guardando l'API, non vedo nulla di più semplice di uno HashMap.

In caso di problemi, è possibile implementare la propria implementazione Mappa, che presenta interni molto semplici. Ma dubito che faresti meglio delle implementazioni Map predefinite, in più avrai il sovraccarico per assicurarti che la tua nuova classe funzioni. In questo caso potrebbe esserci un problema con il tuo design.

Answer 3

Una HashMap è probabilmente la collezione più leggera e semplice.

A volte la soluzione più efficiente è utilizzare un POJO. per esempio. se le tue chiavi sono nomi di campi e/o i tuoi valori sono primitivi.

Answer 4

Sono d'accordo con @hvgotcodes che si tratta di ottimizzazione prematura ma è comunque opportuno conoscere tutti gli strumenti nella casella degli strumenti.

Se esegui molte iterazioni su ciò che è in una mappa, una LinkedHashMap è in genere molto più veloce di una HashMap, se hai molti thread che lavorano con la Mappa nello stesso momento, una ConcurrentHashMap è spesso una scelta migliore Non mi preoccuperei di nessuna implementazione della mappa inefficiente per i piccoli insiemi di dati. In genere è il contrario, una mappa costruita in modo errato diventa facilmente inefficace con grandi quantità di dati se si dispone di valori hash errati o se qualcosa lo fa avere troppo pochi bucket per il suo carico.

Poi naturalmente ci sono casi in cui una HashMap non ha senso a tutti, come se si dispone di tre valori che sarete sempre indice con i tasti 0, 1 e 2, ma suppongo che voi capire che :-)

Answer 5

HashMap è una buona scelta perché offre un valore medio pari a O(1) put e ottiene. Non garantisce l'ordinamento attraverso le implementazioni SortedMap (ad es. TreeMap O(log n) puts and gets) ma se non si ha bisogno di ordinare HashMap è migliore.

Answer 6

HashMap utilizza più o meno memoria (se creata) a seconda di come la si inizializza: più bucket significano più utilizzo della memoria, ma accesso più veloce per grandi quantità di articoli; se hai bisogno solo di un piccolo numero di elementi, puoi inizializzarlo con un valore basso, che produrrà meno secchi che saranno comunque veloci (dal momento che ognuno di essi riceverà alcuni articoli). Non c'è spreco di memoria se lo si imposta correttamente (il compromesso è sostanzialmente l'utilizzo della memoria rispetto alla velocità).

Per quanto riguarda la frammentazione dell'heap e lo spreco di cicli GC e quant'altro, non c'è molto che un'implementazione di Map possa fare su di essi; tutto ricade su come lo si imposta. Comprendere che non si tratta dell'implementazione di Java, ma il fatto che generico (come, ad esempio, non può assumere nulla sui valori chiave come EnumMap) hashtables (non HashTable s) sono le migliori implementazioni possibili di una struttura di mappa.

Answer 7

C'è un'alternativa denominata AirConcurrentMap che è più efficiente della memoria sopra 1K Entries di qualsiasi altra mappa che ho trovato ed è più veloce di ConcurrentSkipListMap per le operazioni basate su chiave e più veloce di qualsiasi Mappa per iterazioni e ha un pool di thread interno per scansioni parallele. È ordinato, ad esempio NavigableMap e ConcurrentMap. È gratuito per uso non commerciale non-sorgente e licenza commerciale con o senza fonte. Vedi boilerbay.com per i grafici. Full disclosure: I am the author.

AirConcurrentMap è conforme agli standard, quindi è compatibile con la presa ovunque, anche per una normale mappa.

Gli iteratori sono già molto veloci, specialmente su voci da 1K. Le scansioni a velocità più elevata utilizzano un modello "visitatore" con una chiamata singola (k, v) che raggiunge la velocità degli stream paralleli di Java 8. La scansione parallela di AirConcurrentMap supera gli stream paralleli di Java 8 di circa 4x. Il visitatore filettato aggiunge diviso() e merge() metodi per il visitatore singolo filo che ricordano mappa/ridurre:

static class ThreadedSummingVisitor<K> extends ThreadedMapVisitor<K, Long> { 
    private long sum; 
    // This is idiomatic 
    long getSum(VisitableMap<K, Long> map) { 
     sum = 0; 
     map.getVisitable().visit(this); 
     return sum; 
    } 

    @Override 
    public void visit(Object k, Long v) { 
     sum += ((Long)v).longValue(); 
    } 

    @Override 
    public ThreadedMapVisitor<K, Long> split() { 
     return new ThreadedSummingVisitor<K>(); 
    } 

    @Override 
    public void merge(ThreadedMapVisitor<K, Long> visitor) { 
     sum += ((ThreadedSummingVisitor<K>)visitor).sum; 
    } 
} 
... 
// The threaded summer can be re-used in one line now. 
long sum = new ThreadedSummingVisitor().getSum((VisitableMap)map); 

Answer 8

Android ha un ArrayMap con l'intento di minimizzare memoria. Oltre ad essere nel nucleo, è nella libreria di supporto v4, che, in teoria, dovrebbe essere in grado di compilare anche per i JRE Oracle o OpenJDK. Ecco un collegamento a the source of ArrayMap in a fork of the v4 support library on github.