HashMap absolute capacity

I 've been doing some performance checks with one HashMap object in my code 开发者_开发知识库and discovered that it slows down adding objects inside at around 2000-2400 objects. In fact when it arrives to 2400 objects circa, it remains blocked and doesn't admit more entries. Is there a limit in this kind of objects that when they've been kept in memory don't admit more entries until they are emptied someway or recycled?

Thank you very much.

---

The only thing I can think of which might explain the problem is if your objects are very large and you are almost running out of heap. When this happens the JVM can stop for increasingly long period of time trying to clean up. In Java 6 it tries to detect this before it gets really bad and throw an OutOfMemoryError (before it has completely run out but it failed to clean up much) Java 5.0 doesn't do this.

It would explain why things speed up again when you discard a few objects.

---

The standard implementation of HashMap is limited to around 750 million entries (depending on how you use it e.g. your load average) The maximum capacity it can have is 2^30 (one billion) and with a load factor of 0.75f (~750m entries) it will try to grow the underlying array to double this size which it cannot do. (As the maximum size is Integer.MAX_VALUE)

You can use LinkedHashMap as a cache, evicting the "eldset" entry based on a rule you have to provide.

However, unless the HashMap is synchronized it will not block. If it going to fail it will throw an exception.

The only consistent way to get a Map to block this way is to have a deadlock.

Another way this can happen is if you are using the same map in two threads in an unsafe manner. In this case the behaviour is undefined, however I have seen it cause problem in the JVM (very rarely) and even "hang" the thread involved. Even if this were the case, I would expect it to have on a growing of the HashMap with a default load factor this would be 3072 (i.e. 4096*0.75) rather than the value you see.

---

Even having a bad hashCode implementation would not explain this problem.

static class BadHash {
    @Override
    public int hashCode() {
        return 1;
    }
}

public static void main(String... args) {
    Map<BadHash, Boolean> map = new HashMap<BadHash, Boolean>();
    for (int i = 0; i <= 100000; i++) {
        if (i % 10000 == 0) System.out.println(i + ": " + new Date());
        map.put(new BadHash(), true);
    }
}

prints the following in 14 seconds.

0: Mon Sep 26 12:23:39 BST 2011
10000: Mon Sep 26 12:23:39 BST 2011
20000: Mon Sep 26 12:23:39 BST 2011
30000: Mon Sep 26 12:23:40 BST 2011
40000: Mon Sep 26 12:23:41 BST 2011
50000: Mon Sep 26 12:23:42 BST 2011
60000: Mon Sep 26 12:23:44 BST 2011
70000: Mon Sep 26 12:23:46 BST 2011
80000: Mon Sep 26 12:23:48 BST 2011
90000: Mon Sep 26 12:23:51 BST 2011
100000: Mon Sep 26 12:23:53 BST 2011

---

Run this program (in a main class):

Map<Long, String> map = new HashMap<Long, String>();
for (long l = 0L; l < 100000; l++) {
    map.put(Long.valueOf(l), String.valueOf(l));
}
System.out.println(map.size());

On my machine this runs, outputs and terminates so quickly that I don't even notice it.

HashMap can support many elements if the hashCode() algorithm is good. Obviously, yours is bad.