Hash Table Memory Usage in Java

Question

I am using java to read data from file, copy the data to smaller arrays and put these arrays in Hashtables. I noticed that Hashmap consumes more memory (about double) than what is in the original file! Any idea why?

Here is my code:

public static void main(final String[] args) throws IOException {
    final PrintWriter writer = new PrintWriter(new FileWriter("test.txt",
            true));
    for(int i = 0; i < 1000000; i++)
        writer.println("This is just a dummy text!");
    writer.close();

    final BufferedReader reader = new BufferedReader(new FileReader(
            "test.txt"));
    final HashMap<Integer, String> testMap = new HashMap<Integer, String>();
    String line = reader.readLine();
    int k = 0;
    while(line != null) {
        testMap.put(k, line);
        k++;
        line = reader.readLine();
    }
}

Answer 1

This is not a problem of HashMap, its a problem of Java Objects in general. Each object has a certain memory overhead, including the arrays and the entries in your HashMap.

But more importantly: Character data consumes double the space in memory. The reason for this is that Java uses 16 bits for each character, whereas the file is probably encoded in ASCII or UTF-8, which only uses 7 or 8 bits per character.

Update: There is not much you can do about this. The code you posted is fine in principle. It just doesn't work with huge files. You might be able to do a little better if you tune your HashMap carefully, or you might use a byte array instead of a String to store your characters (assuming everything is ASCII or one-byte UTF-8).

But in the end, to solve your out-of-memory problems, the right way to go is to rethink your program so that you don't have to read the whole file into memory at once.

Whatever it is you're doing with the content of that file, think about whether you can do it while reading the file from disk (this is called streaming) or maybe extract the relevant parts and only store those. You could also try to random access the file.

I suggest you read up on those things a bit, try something and come back and ask a new question, specific to your application. Because this thread is getting too long.

Answer 2

A map is an "extendable" structure - when it reaches its capacity it gets resized. So it is possible that say 40% of the space used by your map is actually empty. If you know how many entries will be in your map, you can use the ad hoc constructors to size your map in an optimal way:

Map<xx,yy> map = new HashMap<> (length, 1);

Even if you do that, the map will still use more space than the actual size of the contained items.

In more details: HashMap's size gets doubled when it reaches (capacity * loadFactor). Default load factor for a HashMap is 0.75.

Example:

• Imagine your map has a capacity (size) of 10,000 entries
• You then put 7,501 entries in the map. Capacity * loadFactor = 10,000 * 0.75 = 7,500
• So your hashmap has reached its resize threshold and gets resized to (capacity * 2) = 20,000, although you are only holding 7,501 entries. That wastes a lot of space.

EDIT

This simple code gives you an idea of what happens in practice - the output is:

threshold of empty map = 8192
size of empty map = 35792
threshold of filled map = 8192
size of filled map = 1181712
threshold with one more entry = 16384
size with one more entry = 66640

which shows that if the last item you add happens to force the map to resize, it can artificially increase the size of your map. Admittedly, that does not account for the whole effect that you are observing.

public static void main(String[] args) throws java.lang.Exception {
    Field f = HashMap.class.getDeclaredField("threshold");
    f.setAccessible(true);

    long mem = Runtime.getRuntime().freeMemory();
    Map<String, String> map = new HashMap<>(2 << 12, 1); // 8,192
    System.out.println("threshold of empty map = " + f.get(map));
    System.out.println("size of empty map = " + (mem - Runtime.getRuntime().freeMemory()));

    mem = Runtime.getRuntime().freeMemory();
    for (int i = 0; i < 8192; i++) {
        map.put(String.valueOf(i), String.valueOf(i));
    }
    System.out.println("threshold of filled map = " + f.get(map));
    System.out.println("size of filled map = " + (mem - Runtime.getRuntime().freeMemory()));

    mem = Runtime.getRuntime().freeMemory();
    map.put("a", "a");
    System.out.println("threshold with one more entry = " + f.get(map));
    System.out.println("size with one more entry = " + (mem - Runtime.getRuntime().freeMemory()));
}

Answer 3

There are lots of things internal to the implementation of HashMap (and arrays) that need to be stored. Array lengths would be one such example. Not sure if this would account for double, but it could certainly account for some.