Array sparse efficiente in memoria in Java

(Ci sono alcune domande sugli array sparsi efficienti nel tempo ma sto cercando l’efficienza della memoria.)

Ho bisogno dell’equivalente di una List o di Map che

  1. Può crescere su richiesta semplicemente impostando una chiave più grande di qualsiasi altra prima. (Può assumere che le chiavi siano non negative).
  2. È efficiente in termini di memoria come ArrayList nel caso in cui la maggior parte degli indici non sia null , cioè quando i dati reali non sono molto sparsi.
  3. Quando gli indici sono sparsi, consuma spazio proporzionale al numero di indici non null .
  4. Usa meno memoria di HashMap (poiché questo autoboxes le chiavi e probabilmente non sfrutta il tipo di chiave scalare).
  5. Può ottenere o impostare un elemento nel tempo di log ammortizzato (N) dove N è il numero di voci: non è necessario essere il tempo lineare, la ricerca binaria sarebbe accettabile.
  6. Implementato in una libreria Java pura non virale open source (preferibilmente in Maven Central).

Qualcuno sa di una tale class di utilità?

Mi sarei aspettato che le Collezioni di Commons ne avessero una ma non sembrava.

Mi sono imbattuto in org.apache.commons.math.util.OpenIntToFieldHashMap che sembra quasi corretto tranne che il tipo value è un FieldElement che sembra gratuito; Voglio solo che T extends Object . Sembra che sarebbe facile modificare il suo codice sorgente per essere più generico, anche se preferirei usare una dipendenza binaria se ne è disponibile una.

Vorrei provare con le raccolte di trove , c’è TIntObjectMap che può funzionare per i tuoi intenti.

Guarderei l’implementazione SparseArray di Android per l’ispirazione. È ansible visualizzare la fonte scaricando il codice sorgente di AOSP qui http://source.android.com/source/downloading.html

Ti suggerirò di usare OpenIntObjectHashMap dalla libreria Colt. collegamento

Ho salvato il mio caso di test come jglick / inthashmap . I risultati:

 HashMap size: 1017504 TIntObjectMap size: 853216 IntHashMap size: 846984 OpenIntObjectHashMap size: 760472