Java : HashSet vs. HashMap

Question

I have a program working on enormous data sets. The objects are best stored on hash implemented containers since the program keeps seeking for objects in the container.

The first idea was to use HashMap since the methods get and remove of this container are more suitable to the uses I need.

But, I came to see the use of HashMap is pretty memory consumable which is a major problem, so i thought switching to HashSet will be better because it only uses <E>, and not <K,V> per element, but when I looked at the implementation i learned it uses an underlying HashMap! this means it wont save any memory!

So this is my questions:

• Are all my assumptions true?
• Is HashMap memory wasteful? more specifically, what is its overhead for each entry?
• Is HashSet just as wasteful as HashMap?

• Is there any other Hash based containers which will be significantly less memory consumables?

  update

As requested in the comments I will extend a bit on my program, the hashMap is meant to hold a pair of other objects, and some numeric value - a float- calculated from them. along the way it extracts some of them and enters new pairs. Given a pair it needs to ensure it doesnt hold this pair or to remove it. The mapping can be done using the float value or the hashCode of the pair object.

Additionally when i say "enormous data sets" I am talking about ~ 4*10^9 objects

Answer 1

There are very useful tips on this site about collections performance in java.

HashSet is built on top of a HashMap< T, Object >, where value is a singleton ‘present’ object. It means that the memory consumption of aHashSet is identical to HashMap: in order to store SIZE values, you need 32 * SIZE + 4 * CAPACITY bytes (plus size of your values). It is definitely not a memory-friendly collection.

THashSet could be the easiest replacement collection for a HashSet – it implements Set and Iterable, which means you should just update a single letter in the initialization of your set.

THashSet uses a single object array for its values, so it uses 4 * CAPACITY bytes for storage. As you can see, compared to JDK HashSet, you will save 32 * SIZE bytes in case of the identical load factor, which is a huge improvement.

Also the below image which I took from here can help us keeping something in mind for choosing right collection

Answer 2

Are all my assumptions true?

You are correct that HashSet is implemented using HashMap, so you will not save any memory by using HashSet instead.

If you're creating maps with a large number of elements, you should construct your HashMaps with an initialCapacity to the best of your knowledge, in order to prevent repeated rehashing (thus memory thrashing).

Is HashMap memory wasteful? more specifically, what is its overhead for each entry?

No, it's not wasteful. The overhead is an underlying array (size modified by loadFactor), and an Entry object for each key-value pair. In addition to storing a key and value, the entry object also stores a pointer to the next entry in a slot (in case two or more entries are occupying the same slot in the underlying array). The default loadFactor of 0.75 keeps the underlying array size at 133% of the number of entries.

Very specifically, the memory overhead for each entry is:

• the entry object's reference to the key,
• the entry object's reference to the value,
• the entry object's reference to the next entry,
• and the underlying array's reference to the entry (divided by load factor).

It's very difficult to get much more trim than that for a hash-based collection.

Is HashSet just as wasteful as HashMap?

You will gain no memory efficiency by using HashSet instead of HashMap.

Is there any other Hash based containers which will be significantly less memory consumables?

If your keys are primitives (e.g. ints), there are custom Map and Set implementations out there (in third party libraries) which use more memory-efficient data structures.