Java: HashSet vs. HashMap

Question

Ho un programma che lavora su enormi set di dati. Gli oggetti vengono memorizzati al meglio su contenitori implementati con hash poiché il programma continua a cercare oggetti nel contenitore.

La prima idea era utilizzare HashMap poiché i metodi di estrazione e rimozione di questo contenitore sono più adatti agli usi di cui ho bisogno.

Ma, sono venuto a vedere l'uso di HashMap è abbastanza materiale di consumo di memoria, che è un grosso problema, così ho pensato di passare a HashSet sarà migliore perché utilizza solo <E>, e non <K,V> per elemento, ma quando ho guardato l'implementazione che ho imparato utilizza una HashMap sottostante! questo significa che non salverà alcun ricordo!

Quindi questo è le mie domande:

• sono tutte le mie ipotesi vero?
• La memoria HashMap è dispendiosa? più specificamente, qual è il suo overhead per ogni voce?
• HashSet è altrettanto dispendioso di HashMap?

• Esistono altri contenitori basati su Hash che consumeranno significativamente meno materiali di consumo?

  aggiornamento

Come richiesto nei commenti mi estendere un po 'sul mio programma, il HashMap è destinato a contenere un paio di altri oggetti, e alcuni valore numerico - un flottante calcolata da loro. lungo la strada ne estrae alcuni ed entra in nuove coppie. Dato un paio ha bisogno di assicurarsi che non tenga questa coppia o per rimuoverla. La mappatura può essere eseguita utilizzando il valore float o lo hashCode dell'oggetto pair.

Inoltre quando dico "enormi set di dati" Sto parlando circa ~ 4 * 10^9 oggetti

Answer 1

sono tutte le mie ipotesi vero?

Lei ha ragione che HashSet viene implementata utilizzando HashMap, in modo da non salverà alcuna memoria utilizzando HashSet invece.

Se si stanno creando mappe con un numero elevato di elementi, è consigliabile creare i propri HashMap s con un initialCapacity in base alle proprie conoscenze, al fine di evitare ripetuti rilasci (quindi problemi di memoria).

La memoria HashMap è dispendiosa? più specificamente, qual è il suo overhead per ogni voce?

No, non è uno spreco. L'overhead è un array sottostante (dimensioni modificate da loadFactor) e un oggetto Entry per ciascuna coppia chiave-valore. Oltre a memorizzare una chiave e un valore, l'oggetto entry memorizza anche un puntatore alla voce successiva in uno slot (nel caso in cui due o più voci occupino lo stesso slot nell'array sottostante). Il load factor predefinito di 0.75 mantiene la dimensione dell'array sottostante al 133% del numero di voci.

Molto specificamente, l'overhead di memoria per ogni articolo è:

• riferimento dell'oggetto voce alla chiave,
• riferimento dell'oggetto ingresso al valore,
• riferimento dell'oggetto ingresso al successivo voce,
• e il riferimento dell'array sottostante alla voce (diviso per fattore di carico).

È molto difficile ottenere molto più ritaglio di quello per una raccolta basata su hash.

HashSet è altrettanto dispendioso di HashMap?

Non si otterrà l'efficienza della memoria utilizzando HashSet anziché HashMap.

C'è qualche altro contenitore basato su Hash che sarà significativamente meno consumabile di memoria ?

se le chiavi sono primitive (ad esempio int s), ci sono personalizzati Map e Set implementazioni là fuori (in third party libraries) che utilizzano più strutture di dati di memoria-efficiente.

Answer 2

Ci sono suggerimenti molto utili su this site sulle prestazioni delle raccolte in java.

HashSet è costruito sulla cima di una HashMap< T, Object >, dove valore è un oggetto singleton ‘presente’. Significa che the memory consumption of aHashSet is identical to HashMap: per memorizzare i valori SIZE, è necessario 32 * SIZE + 4 * CAPACITY byte (oltre alle dimensioni dei valori). Non è sicuramente una collezione amica della memoria.

THashSet potrebbe essere la raccolta di sostituzione più semplice per un HashSet - implementa Set e Iterable, il che significa che è sufficiente aggiornare una singola lettera nell'inizializzazione del set.

THashSet utilizza un singolo array di oggetti per i suoi valori, quindi utilizza 4 * CAPACITY byte per l'archiviazione. Come puoi vedere, rispetto a JDK HashSet, lo risparmi32 * SIZE byte in caso di identico fattore di carico, che rappresenta un enorme miglioramento.

anche l'immagine di sotto del quale ho preso da here ci può aiutare a tenere in mente qualcosa per la scelta di raccolta diritto

Answer 3

E 'vero che HashSet utilizza solo la quantità di memoria HashMap. La differenza tra i due che HasSet implementa Set, cioè, non interessa alcun valore associato a una chiave, ma solo la presenza o meno di un particolare valore. HashMap riguarda la memorizzazione/il recupero (put/get) dei valori per chiave.

Mentre HashMap/HashSet memorizzano i dati in un array che è solitamente leggermente più grande del numero di elementi, questo non rappresenta un problema eccessivo perché il fattore di carico è 0,75. Ciò significa che una HashMap crescerà quando il numero di elementi raggiunge il 75% della dimensione dell'array sottostante.

Una preoccupazione più grande di una mappa di grandi dimensioni sarebbe un sacco di mappe vuoti, dal momento che la dimensione predefinita di un HashMap è 16. Questo può essere compensato impostando la capacità iniziale a 0.

È inoltre possibile utilizzare TreeMap invece Tuttavia, poiché TreeMap è basato su riferimenti anziché su un array, probabilmente si sprecherà ancora più spazio, specialmente con mappe più grandi, oltre a perdere anche velocità. Il vantaggio principale di TreeMap è che mantiene le chiavi in ​​uno stato ordinato, quindi se hai bisogno di ordinarle è la strada da percorrere.

Inoltre, TreeMap può essere utilizzato per motivi di programmazione quando non è possibile o non si desidera eseguire un'implementazione personalizzata dei metodi equals e hashCode del tipo di chiave. Puoi invece fare un comparatore per il tipo di chiave. Ad esempio, per creare una mappa/un set basato su String senza distinzione tra maiuscole e minuscole, utilizzare String.CASE_INSENSITIVE_ORDER come comparatore di un TreeSet