CODEWITHSUNDEEP
java
Thomas
Thomas

Reputation: 1123

How does the content of a Hashtable affect its size in memory?

If I have Hashtable A that has 5 million keys mapped to 5 million unique values, and I have Hashtable B that has 5 million keys mapped to 20 unique values, then approximately how much more memory would Hashtable A use compared to Hashtable B?

All of the keys and values are Strings that are approximately 20-50 characters in length.

My initial guess is that Hashtable A would take up roughly double the space as Hashtable B, but if you include the mappings then Hashtable B would use:

(5 million keys + 5 million mappings + 20 values) / (5 million keys + 5 million mappings + 5 million values) = .66

66.6% of the memory Hashtable A uses. However I don't know if a mapping would use as much space as a key or value if the keys and values are Strings.

Comments?

Upvotes: 1

Views: 183

Answers (2)

rmeador
rmeador

Reputation: 25704

If you're storing literal strings, then the JVM may intern them, in which case the 20 key version would use significantly less memory (just how much less I don't know how to calculate). But for a standard hash table implementation that isn't subject to such magic, they would both use the same amount of memory, since each "bucket" will store a value, regardless of if that value is also stored in other buckets.

Upvotes: 0

Uri
Uri

Reputation: 89849

I don't think this has to do much with the hash table, since the "values" of the hash table are merely references to what I assume are the existing values. The increase in total cost would be based primarily on the size of a value. After all, you could have every key mapped to null.

Also, depending on the size of your keys, this may or may not have an impact. For example, a mapping from 5 million heavy objects (like strings) to 5 million lighter objects like Integers would not be that different from mapping 5 million heavy objects to 20 different values of Integer.

Upvotes: 2

Related Questions