There are two performance issues in IdentityHashMap causing that the map is resized (rehashed) before the number of entries exceeds the expected maximum.

The Javadoc of IdentityHashMap(int) specifies that "putting more than the expected number of key-value mappings into the map may cause the internal data structure to grow". Strictly taken, this statement does not promise that the internal data structure would not grow sooner, but I believe it was meant that way and that most developers understand it that way.

The fact is that the internal data structure may grow before the expected number of key-value mappings inserted into the map exceeds the expected number specified by the constructor's parameter. This is the case if the expected number of entries is one of the following values:

    2, 3, 5, 10, 11, 21, 42, 43, 85, 170, 171, 341,
    682, 683, 1365, 2730, 2731, 5461, 10922, 10923,
    21845, 43690, 43691, 87381, 174762, 174763, 349525,
    699050, 699051, 1398101, 2796202, 2796203, 5592405,
    11184810, 11184811, 22369621, 44739242, 44739243,
    89478485, 178956970, 178956971 and all numbers
    greater than or equal to 357913941

To test this, set a line breakpoint to the first line of code in method resize(int) and fill the map with the expected maximum number of entries. A breakpoint hit confirms the bug.


The first issue is that the capacity of the table is incorrectly computed for the given expected maximum number of entries. The load factor of IdentityHashMap is fixed to always be 2/3, so the capacity is computed as follows:

    int minCapacity = (3 * expectedMaxSize)/2;

This seems to be correct at first sight. The problem is that if 'expectedMaxSize' is an odd number, the computed minCapacity is less than 3/2 of the expected maximum size. Because the threshold for rehashing is computed from the minimum capacity, the rounding bug propagates to the incorrect result of the threshold, which is then 1 lower than it should be.

Fortunately, the above formula is followed by another forumula that rounds the computed minCapacity to the lowest power of two equal to or greater than the initial minCapacity. This eliminates the damage in most cases.


The second issue is that even if the initial capacity and the threshold are computed correctly, the threshold is incorrectly used. The table should get resized (rehashed) if the number of entries _exceeds_ (or would be about to exceed) the threshold. But the table is rehashed as soon as the threshold is _reached_:

    public V put(K key, V value) {
        ...
        if (++size >= threshold)
            resize(len);
        return null;
    }


If only one of the issues shows, the table gets resized as soon as the number of entries reaches the expected maximum number of elements. If both the issues show, the table gets resized when the number of entries is one below the expected maximum number of elements.

This bug is present in JDK 6u18 and also in JDK 5u22.

A simple test application is attached.