Perché ottengo un OutOfMemoryError quando inserisco 50.000 oggetti in HashMap?

Question

Sto cercando di inserire circa 50.000 oggetti (e quindi 50.000 chiavi) in un java.util.HashMap<java.awt.Point, Segment>. Tuttavia, continuo a ricevere un'eccezione OutOfMemory. (Segment è la mia classe - molto leggera - un campo String e 3 int campi).

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.HashMap.resize(HashMap.java:508)
    at java.util.HashMap.addEntry(HashMap.java:799)
    at java.util.HashMap.put(HashMap.java:431)
    at bus.tools.UpdateMap.putSegment(UpdateMap.java:168)

Questo sembra abbastanza ridicolo poiché vedo che c'è molta memoria disponibile sulla macchina - sia nella RAM libera che nello spazio HD per la memoria virtuale.

È possibile che Java sia in esecuzione con alcuni requisiti di memoria rigorosi? Posso aumentarli?

C'è qualche strana limitazione con HashMap? Devo implementare il mio? Ci sono altre classi che vale la pena guardare?

(Sto eseguendo Java 5 con OS X 10.5 su una macchina Intel con 2 GB di RAM.)

Answer 1

Puoi aumentare la dimensione massima dell'heap passando -Xmx128m (dove 128 è il numero di megabyte) a java. Non ricordo le dimensioni predefinite, ma mi sembra che fosse qualcosa di piuttosto piccolo.

Puoi controllare a livello di programmazione quanta memoria è disponibile usando il Runtime classe.

// Get current size of heap in bytes
long heapSize = Runtime.getRuntime().totalMemory();

// Get maximum size of heap in bytes. The heap cannot grow beyond this size.
// Any attempt will result in an OutOfMemoryException.
long heapMaxSize = Runtime.getRuntime().maxMemory();

// Get amount of free memory within the heap in bytes. This size will increase
// after garbage collection and decrease as new objects are created.
long heapFreeSize = Runtime.getRuntime().freeMemory();

(Esempio da Java Developers Almanac )

Anche questo è parzialmente risolto in Domande frequenti sulla VM HotSpot Java e nella pagina Tuning GC 6 Java .

Answer 2

Alcune persone stanno suggerendo di modificare i parametri di HashMap per rafforzare i requisiti di memoria. Suggerirei di misurare invece di indovinare ; potrebbe essere qualcos'altro che causa l'OOME. In particolare, suggerirei di utilizzare NetBeans Profiler o VisualVM (fornito con Java 6, ma vedo che sei bloccato con Java 5).

Answer 3

Un'altra cosa da provare se si conosce in anticipo il numero di oggetti è utilizzare il costruttore HashMap (capacità int, doppio fattore di carico) invece di quello predefinito no-arg che utilizza valori predefiniti di (16,0,75). Se il numero di elementi in HashMap supera (capacità * loadfactor), l'array sottostante in HashMap verrà ridimensionato alla potenza successiva di 2 e la tabella verrà rimodellata. Questo array richiede anche un'area contigua di memoria, ad esempio se si raddoppia da un array di 32768 a un array di dimensioni 65536 sarà necessario un blocco di memoria di 256 KB. Per evitare l'allocazione aggiuntiva e le penalità di rifacimento, basta utilizzare una tabella hash più grande dall'inizio. Ridurrà anche la possibilità di non avere un'area contigua di memoria abbastanza grande da adattarsi alla mappa.

Answer 4

Le implementazioni sono generalmente supportate da array. Le matrici sono blocchi di memoria di dimensioni fisse. L'implementazione dell'hashmap inizia archiviando i dati in uno di questi array a una determinata capacità, diciamo 100 oggetti.

Se riempie l'array e continui ad aggiungere oggetti, la mappa deve aumentare segretamente le dimensioni dell'array. Poiché gli array sono fissi, lo fa creando un array completamente nuovo, in memoria, insieme all'array corrente, leggermente più grande. Questo è indicato come crescita dell'array. Quindi tutti gli elementi del vecchio array vengono copiati nel nuovo array e il vecchio array viene dereferenziato con la speranza che venga spazzato via e la memoria liberata ad un certo punto.

Di solito il codice che aumenta la capacità della mappa copiando gli elementi in un array più grande è la causa di tale problema. Ci sono & Quot; dumb & Quot; implementazioni e soluzioni intelligenti che utilizzano un fattore di crescita o di carico che determina le dimensioni del nuovo array in base alle dimensioni del vecchio array. Alcune implementazioni nascondono questi parametri e altre no, pertanto non è sempre possibile impostarle. Il problema è che quando non è possibile impostarlo, si sceglie un fattore di carico predefinito, come 2. Quindi il nuovo array ha una dimensione doppia rispetto al vecchio. Ora la tua mappa presumibilmente 50k ha un array di supporto di 100k.

Cerca di vedere se riesci a ridurre il fattore di carico fino a 0,25 o qualcosa del genere. questo provoca più collisioni della mappa hash che danneggiano le prestazioni ma stai colpendo un collo di bottiglia della memoria e devi farlo.

Usa questo costruttore:

( http: // java.sun.com/javase/6/docs/api/java/util/HashMap.html#HashMap(int , float))

Answer 5

Probabilmente dovrai impostare il flag -Xmx512m o un numero maggiore quando avvii java. Penso che 64mb sia l'impostazione predefinita.

Modificato per aggiungere: Dopo aver capito quanta memoria i tuoi oggetti stanno effettivamente utilizzando con un profiler, potresti voler esaminare riferimenti deboli o riferimenti deboli per assicurarti di non tenere accidentalmente in ostaggio parte della tua memoria dal garbage collector quando non ci sei usandoli più a lungo.

Answer 6

Potrebbe anche voler dare un'occhiata a questo:

http://java.sun.com/docs/hotspot/gc/

Answer 7

In queste risposte è implicito che Java ha una dimensione fissa per la memoria e non cresce oltre la dimensione heap massima configurata. Questo è diverso, diciamo, C, dove è limitato solo dalla macchina su cui è in esecuzione.

Answer 8

Per impostazione predefinita, JVM utilizza uno spazio heap limitato. Il limite dipende dall'implementazione di JVM e non è chiaro quale JVM si sta utilizzando. Su sistemi operativi diversi da Windows, una Sun JVM a 32 bit su una macchina con almeno 2 Gb utilizzerà una dimensione heap massima predefinita di 1/4 della memoria fisica o 512 Mb nel tuo caso. Tuttavia, il valore predefinito per un & Quot; client & Quot; mode JVM ha una dimensione heap massima di soli 64 Mb, che potrebbe essere ciò in cui ti sei imbattuto. Le JVM di altri fornitori possono selezionare impostazioni predefinite diverse.

Ovviamente, puoi specificare esplicitamente il limite di heap con l'opzione -Xmx<NN>m su java, dove <NN> è il numero di megabyte per l'heap.

Come ipotesi approssimativa, la tua tabella hash dovrebbe usare solo circa 16 Mb, quindi sull'heap devono esserci altri oggetti di grandi dimensioni. Se potessi usare una chiave Comparable in TreeMap, ciò risparmierebbe un po 'di memoria.

Vedi " Ergonomia nella 5.0 JVM " per maggiori dettagli.

Answer 9

Lo spazio heap Java è limitato per impostazione predefinita, ma sembra comunque estremo (anche se quanto sono grandi i tuoi 50000 segmenti?)

Sospetto che tu abbia qualche altro problema, come gli array nel set che diventano troppo grandi perché tutto viene assegnato nello stesso " slot " (influenza anche le prestazioni, ovviamente). Tuttavia, ciò sembra improbabile se i tuoi punti sono distribuiti uniformemente.

Mi chiedo però perché stai usando una HashMap piuttosto che una TreeMap? Anche se i punti sono bidimensionali, è possibile sottoclassarli con una funzione di confronto e quindi effettuare ricerche log (n).

Answer 10

Pensiero casuale: i bucket hash associati a HashMap non sono particolarmente efficienti in termini di memoria. Potresti provare TreeMap in alternativa e vedere se fornisce ancora prestazioni sufficienti.