This article will give you an overview of some popular Java data types memory consumption. This article follows An overview of memory saving techniques in Java and Memory consumption of popular Java data types – part 1 articles earlier published in this blog. I strongly recommend you to read An overview of memory saving techniques in Java before reading this one. This article assumes that size of references is equal to 4 bytes.
HashMap is the most popular map in JDK. Provided that it contains objects with a quality
hashCode method and it has not too high load factor, it will generally give you
O(1) performance of
put methods (as well as similar methods like
You can find a proper hash map description in one of popular textbooks (“Algorithms (4th Edition)” or “Introduction to Algorithms”) or in Wikipedia. Here we will only discuss JDK
HashMap is built on top of the array of
Map.Entry objects. The implementation ensures that this array length is always equal to at least
max( size, capacity ) / load_factor. Default load factor for
HashMap is 0.75 and default capacity is 16. Load factor specifies which part of an array could be used for storage and is a value between 0 and 1. The higher is the load factor, the less space is being wasted, but
HashMap starts to work slower due to increased rate of collisions. The smaller if the load factor, the more memory is wasted, but the performance of a
HashMap is increasing due to smaller possibility of collisions.
So, as you have seen, the default (
new HashMap<>()) size of array of entries is 16 / 0.75 = 21.33 ~ 22.
What is a
HashMap.Entry? It contains a key, a value,
int hash of a key and a pointer to the next entry (remember that entries array could be sparse). It means that an entry occupies 32 bytes (12 bytes header + 16 bytes data + 4 bytes padding). So, a
HashMap with size = S has to spend 32 * S bytes for entries storage. Besides, it will use 4 * C bytes for entries array, where C is the map capacity.
As you can see, if you will make the map capacity small enough (less than 12.5%), its entry array size will start dominating over the entries.