30

I was asked in an interview to calculate the memory usage for HashMap and how much estimated memory it will consume if you have 2 million items in it.

For example:

Map <String,List<String>> mp=new HashMap <String,List<String>>();

The mapping is like this.

key   value
----- ---------------------------
abc   ['hello','how']
abz   ['hello','how','are','you']

How would I estimate the memory usage of this HashMap Object in Java?

10
  • 6
    It depends on what it contains... May 27, 2011 at 20:28
  • @petar Minchev: it stores value in the map, they wanted me to calculate total memory usage. This was confusing as it had one key and multiple values.
    – insomiac
    May 27, 2011 at 20:32
  • @Petar, the hashmap memory allocation is not the entire rertained size, it's the overhead of using it (i.e. shallow size)
    – bestsss
    May 27, 2011 at 20:34
  • huh, now i notice the multiple values edition... the question has degraded so badly :(
    – bestsss
    May 27, 2011 at 21:13
  • Take a look at: roseindia.net/javatutorials/…
    – anubhava
    May 27, 2011 at 21:23

4 Answers 4

24

The short answer

To find out how large an object is, I would use a profiler. In YourKit, for example, you can search for the object and then get it to calculate its deep size. This will give a you a fair idea of how much memory would be used if the object were stand alone and is a conservative size for the object.

The quibbles

If parts of the object are re-used in other structures e.g. String literals, you won't free this much memory by discarding it. In fact discarding one reference to the HashMap might not free any memory at all.

What about Serialisation?

Serialising the object is one approach to getting an estimate, but it can be wildly off as the serialisation overhead and encoding is different in memory and to a byte stream. How much memory is used depends on the JVM (and whether its using 32/64-bit references), but the Serialisation format is always the same.

e.g.

In Sun/Oracle's JVM, an Integer can take 16 bytes for the header, 4 bytes for the number and 4 bytes padding (the objects are 8-byte aligned in memory), total 24 bytes. However if you serialise one Integer, it takes 81 bytes, serialise two integers and they takes 91 bytes. i.e. the size of the first Integer is inflated and the second Integer is less than what is used in memory.

String is a much more complex example. In the Sun/Oracle JVM, it contains 3 int values and a char[] reference. So you might assume it uses 16 byte header plus 3 * 4 bytes for the ints, 4 bytes for the char[], 16 bytes for the overhead of the char[] and then two bytes per char, aligned to 8-byte boundary...

What flags can change the size?

If you have 64-bit references, the char[] reference is 8 bytes long resulting in 4 bytes of padding. If you have a 64-bit JVM, you can use +XX:+UseCompressedOops to use 32-bit references. (So look at the JVM bit size alone doesn't tell you the size of its references)

If you have -XX:+UseCompressedStrings, the JVM will use a byte[] instead of a char array when it can. This can slow down your application slightly but could improve you memory consumption dramatically. When a byte[] in used, the memory consumed is 1 byte per char. ;) Note: for a 4-char String, as in the example, the size used is the same due to the 8-byte boundary.

What do you mean by "size"?

As has been pointed out, HashMap and List is more complex as many, if not all, the Strings can be reused, possibly String literals. What you mean by "size" depends on how it is used. i.e. How much memory would the structure use alone? How much would be freed if the structure were discarded? How much memory would be used if you copied the structure? These questions can have different answers.

What can you do without a profiler?

If you can determine that the likely conservative size, is small enough, the exact size doesn't matter. The conservative case is likely to where you construct every String and entry from scratch. (I only say likely as a HashMap can have capacity for 1 billion entries even though it is empty. Strings with a single char can be a sub-string of a String with 2 billion characters)

You can perform a System.gc(), take the free memory, create the objects, perform another System.gc() and see how much the free memory has reduced. You may need to create the object many times and take an average. Repeat this exercise many times, but it can give you a fair idea.

(BTW While System.gc() is only a hint, the Sun/Oracle JVM will perform a Full GC every time by default)

4
  • 1
    besides YourKit which is not free, you can use jmap (+jhat) that are part of JDK.
    – bestsss
    May 28, 2011 at 17:07
  • 2
    YourKit is free on evaluation. I had several before I bought it. Sometimes in a profession its worth paying for the tools you use.;) May 29, 2011 at 7:32
  • I can't imagine a carpenter who would only use hammers that he could get for free.
    – Stephen C
    Feb 10, 2022 at 4:41
  • 1
    When you try to get the actual memory using a profiling tool like YourKit, you should know What Heap Dumps Are Lying To You About
    – Holger
    Sep 21, 2022 at 7:34
5

I think that the question should be clarified because there is a difference between the size of the HashMap and the size of HashMap + the objects contained by the HashMap.

If you consider the size of the HashMap, in the example you provided, the HashMap stores one reference to the String "aby" and one reference to the List. So the multiple elements in the list do not matter. Only the reference to the list is stored in the value.

In a 32 bits JVM, in one Map entry, you have 4 bytes for the "aby" reference + 4 bytes for the List reference + 4 bytes for the "hashcode" int property of Map entry + 4 bytes for the "next" property of Map entry.

You also add the 4*(X-1) bytes references where the "X" is the number of empty buckets that the HashMap has created when you called the constructor new HashMap<String,List<String>>() . According to http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html, it should be 16.

There are also loadFactor, modCount, threshold and size which are all primitive int type (16 more bytes) and header (8bytes).

So in the end, the size of your above HashMap would be 4 + 4 + 1 + (4*15) + 16 + 8 = 93 bytes

This is an approximation based on data that are owned by the HashMap. I think that maybe the interviewer was interested in seeing if you were aware of the way HashMap works (the fact for example that the default constructor create and array of 16 buckets for Map entry, the fact that the sizes of the objects stored in the HashMap do not affect the HashMap size since it only store the references).

HashMap are so widely used that under certain circumstances, it should be worth using the constructors with initial capacity and load factor.

1
  • 3
    You neglect the memory management overhead of 8 bytes per object, and rounding to 8 bytes of the sizes. A HashMap.Entry is 24 Bytes, not 16, for example. For many cases, this adds up to an enormous amount of memory wasted. For example, a HashMap<Integer, Double> needs about 100 Bytes per stored value due to boxing, with 12 bytes of actual data, and 88 bytes overhead. Now with Strings, there is no autoboxing, and the strings are not as tiny, so it will not be as massive. Sep 4, 2016 at 20:04
1
Summary:

memory = hashmap_array_size*bucket_size
+ n*chained_list_node_size
+ sum(key string sizes)
+ sum(list_string_size(string_list) for each hashmap List<String> value)

= 254 MB
(theoretical in-interview estimate)

Test program total-memory-used-size for 2 million sample entries: (see below)
= 640 MB
(I recommend a simple test program like this for a quick true-total-size estimate)

A minimal estimate (actual implementation probably has a bit more overhead):

Assumed data structure:

Bucket: (Pointer to String key, Pointer to hash-chain-list first-node)

Chained List Node: (Pointer to List<String> value, Next-pointer)
(HashMap is a chained hash - each bucket has a list/tree of values)
(as of Java 8, the list switches to a tree after 8 items)

List<String> instance: (Pointer to first node)

List<String> Node: (Pointer to String value, Next-pointer)

Assumption to simplify this estimate: zero collisions, each bucket has max 1 value (ask interviewer if this is ok - to give a rough, initial answer)

Assumption: 64-bit JVM so 64-bit pointers so pointer_size=8 bytes

Assumption: HashMap underlying array is 50% full (by default, at 75% full, the hashmap is rehashed with double the size), so hashmap_array_size = 2*n

memory = hashmap_array_size*bucket_size
+ n*chained_list_node_size
+ sum(key string sizes)
+ sum(list_string_size(string_list) for each hashmap List<String> value)

So:

memory = (n*2)*(8*2)
+ n*(8*2) + ((2 length_field + 3 string_length)*n)
+ (n*(8 + 3*(8*2)
+ 3*(2 length_field + 4 string_length))
= 2000000*(2*8*2 + 8*2 + (2+3) + (8 + 3*8*2 + 3*(2+4)))
= 254000000
= 254 MB

n = number of items in the hash map

bucket_size = pointer_size*2

chained_list_node_size = pointer_size*2

list_string_size(list) = pointer_size +
list.size()*list_string_node_size
+ sum(string value sizes in this List<String> list)

list_string_node_size = pointer_size*2

String length bytes = length_field_size + string_characters
(UTF-8 is 1 byte per ascii character)
(length_field_size = size of integer = 2)

Assume all keys are length 3.
(we have to assume something to calculate space used)
so: sum(key string sizes) = (2 length_field + 3 string_length)*n

Assume all value string-lists are length 3 and each string is of length 4. So:
sum(list_string_size(string_list) for each hashmap List<String> value)
= n*(8 + 3*(8*2) + 3*(2 length_field + 4 string_length))

A simple test program would give a better real answer:

import java.util.*;
class TempTest {
    public static void main(String[] args) {
        HashMap<String, List<String>> map = new HashMap<>();
        System.gc();
        printMemory();
        for (int i = 0; i < 2000000; ++i) {
            map.put(String.valueOf(i), Arrays.asList(String.valueOf(i), String.valueOf(i) + "b", String.valueOf(i) + "c"));
        }
        System.gc();
        printMemory();
    }

    private static void printMemory() {
        Runtime runtime = Runtime.getRuntime();
        long totalMemory = runtime.totalMemory();
        long freeMemory = runtime.freeMemory();

        System.out.println("Memory: Used=" + (totalMemory - freeMemory) + " Total=" + totalMemory + " Free=" + freeMemory);
    }
}

For me, this took 640MB (after.Used - before.Used).

1
  • For my problem, switching from HashMap<Long, Long> to LongLongHashMap (eclipse collections) reduced my memory footprint. From 433MB to 273MB for a sample-test-allocation of 5 million entries (see test program above). Feb 10, 2022 at 16:10
0

you can't know in advance without knowing what all the strings are, and how many items are in each list, or without knowing if the strings are all unique references.

The only way to know for sure, is to serialize the whole thing to a byte array (or temp file) and see exactly how many bytes that was.

9
  • @john: they asked me for estimated memory usage. is there any idea how to calculate it?
    – insomiac
    May 27, 2011 at 20:38
  • 1
    they probably asked you the question so that you'd ask all the questions we're asking. You can't estimate something without enough information, and so far, just a map of lists of strings isn't enough info. How may items in the map? average size of each key? average number of items in each key's list? average size of each string in each key's list? etc... May 27, 2011 at 20:43
  • @John the memory O() of a data structure size the memory the estimated memory per element, a reference of a string in java depends on the architecture and it's between 4 and 8 bytes. What the string, itself. contains is irrelevant to the data structure.
    – bestsss
    May 27, 2011 at 20:48
  • 2
    @bestsss it really depends on if you're arguing the shallow size of the structure itself, or the deep size of the entire structure. if I asked this interview question, i'd be asking it to see what questions the interviewee asked in order to perform the estimate, not for a detailed discussion about the internals of sun/oracle's implementation of HashMap itself. May 27, 2011 at 21:14
  • @John, but what will you do if you map.put(String.intern(), Boolean.valueOf(b))? I do understand String.intern() might (does) bloat the perm-gen, however you bet you'd get the a similar question on the interview from me.
    – bestsss
    May 27, 2011 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.