Quanta memoria Java HashSet dovrebbe richiedere

Question

Volevo utilizzare uno HashSet<Long> per archiviare una grande lista di numeri univoci in memoria. Ho calcolato la memoria approssimativa da consumare (nella dimensione del puntatore a 64 bit):

lungo richiederebbe 16 byte di spazio. Quindi inizialmente ho moltiplicato il numero di voci con 16 per ottenere la memoria. Ma in realtà, la memoria era molto più di 16 byte per voce. Successivamente ho studiato l'implementazione di HashSet. In breve, nell'implementazione sottostante, memorizza in realtà un oggetto fittizio extra (12 byte) con ogni voce di hashset. E un puntatore (8 byte) alla voce successiva. Così concedendo 12 + 8 byte aggiuntivi per entrata.

Dunque memoria totale per voce: 16 + 12 + 8 = 36 byte. Ma ancora quando ho eseguito il codice e controllato la memoria, era ancora molto più di 36 byte per voce.

La mia domanda (In breve): Quanta memoria ha un HashSet (per esempio, su una macchina a 64 bit)?

Answer 1

La dimensione degli oggetti è un dettaglio di implementazione. Non c'è alcuna garanzia che se è x byte su una piattaforma, su un'altra è anche x byte.

Long è in scatola come sapete, ma 16 byte è sbagliato. La primitiva long richiede 8 byte ma la dimensione della casella attorno a long dipende dall'implementazione. Secondo this Hotspot related answer parole in alto e padding significa che un boxed 4 byte int può arrivare a 24 byte!

L'allineamento e il riempimento di byte menzionati in quella risposta (specifica per Hotspot) si applicano anche agli oggetti Entry che potrebbero anche spingere il consumo verso l'alto.

Answer 2

La memoria utilizzata è 32 * DIMENSIONE + 4 * CAPACITÀ + (16 * DIMENSIONE) segno "SIZE" il numero di elementi.

Answer 3

È possibile misurare esattamente queste dimensioni utilizzando questo test:

long m1 = Runtime.getRuntime().freeMemory(); 
    // create object (s) here 
    long m2 = Runtime.getRuntime().freeMemory(); 
    System.out.println(m1 - m2); 

da eseguire con XX: l'opzione -UseTLAB

Sul mio 64-bit HotSpot HashSet vuoto prende 480 byte.

Perché così tanto? Perché HashSet ha una struttura complessa (IDE in modalità debug aiuta a vedere i campi reali). È basato su HashMap (modello adattatore). Quindi HashSet stesso contiene un riferimento a una HashMap. HashMap contiene 8 campi. I dati effettivi sono in una matrice di nodi. Un nodo ha: int hash; Tasto K; Valore V; Nodo prossimo. HashSet utilizza solo le chiavi e inserisce un oggetto fittizio in valori.

Answer 4

La dimensione predefinita di HashMap è 16 voci HashMapEntry. Ogni HashMapEntry ha quattro oggetti (int keyHash, Object next, Object key, Object value). Quindi introduce un sovraccarico solo per avere voci vuote avvolgendo gli elementi. Inoltre, hashmap ha un tasso di espansione di 2x, quindi per 17 elementi, avrai 32 voci con 15 di esse vuote.

Un modo più semplice è controllare un heapdump con l'analizzatore di memoria.

Answer 5

A HashSet è una bestia complicata.Fuori della parte superiore della mia testa e dopo aver esaminato alcuni dei commenti, qui ci sono alcuni elementi che consumano la memoria che non hanno rappresentato:

1. collezioni di Java (vere e proprie collezioni, non array pianura) può avvenire solo riferimenti a oggetti, non primitivi. Pertanto, la primitiva long viene inserita in un oggetto java.lang.Long e un riferimento aggiunto all'oggetto HashSet. Somebody mentioned that a Long` sarà di 24 byte. Più il riferimento, che è 8 byte.
2. I bucket tabella hash sono raccolte. Non ricordo se sono array o ArrayList, o LinkedList, ecc., Ma poiché gli algoritmi di hashing potrebbero produrre collisioni, gli elementi di HashSet devono essere inseriti in raccolte, che sono organizzati in codice hash. Il caso migliore è un ArrayList con un solo elemento: l'oggetto Long. La dimensione predefinita dell'array di supporto per ArrayList è 10, quindi sono 10 i riferimenti oggetto all'interno dell'oggetto, quindi almeno 80 byte ora per Long. Poiché Long è un numero intero, sospetto che l'algoritmo di hashing faccia un buon lavoro nel diffondere le cose. Non sono sicuro di cosa succederebbe a un valore il cui valore superava il valore Integer.MAX_VALUE. Ciò dovrebbe collidere in qualche modo a causa del paradosso del compleanno.
3. La tabella hash effettiva - HashSet è fondamentalmente un HashMap in cui il valore non è interessante. Sotto il cofano, crea un HashMap, che ha una serie di serbatoi in esso per rappresentare la tabella hash. La dimensione dell'array si basa sulla capacità, che non è chiara in base al numero di elementi aggiunti.
4. La dimensione della tabella hash di solito, intenzionalmente, ha più bucket del necessario, al fine di facilitare la crescita futura. Spero che non sia molto di più. Ma non aspettarti che 5 elementi richiedano esattamente 5 secchi.

Le tabelle hash di breve durata sono una struttura di dati che richiede molta memoria. È il trade-off spazio/tempo. Si ottiene, presupponendo una buona distribuzione hash, ricerche a tempo costante, al costo dell'utilizzo di memoria extra.