J2SE Version (please include all output from java -version flag):

java version "1.6.0"
Java(TM) SE Runtime Environment (build 1.6.0-b105)
Java HotSpot(TM) Client VM (build 1.6.0-b105, mixed mode)

Does this problem occur on J2SE 5.0.x or 6.0? Yes / No (pick one)
Yes - reproduced on 1.5.0_12 and 6.0.

Operating System Configuration Information (be specific):
Any but tested on: Microsoft Windows XP [Version 5.1.2600]

Bug Description:

There is a bug in java.util.IdentityHashMap where it can run into an
infinite loop when calling the put() method. This happens when also using
an iterator() on the same object and calling remove selectively on some
elements. The problem appears to be that the map gets confused about the
free space in the map and eventually tries to find a slot for an item even
though there is no free space. Since the IHM uses linear probing rather
than chaining, it runs round the underlying array looking for a free slot
but never finds one.

I confess I have not examined the IdentityHashMapIterator.remove() method
in detail myself to identity the bug since it is quite involved.

I have however developed a test case that keeps hammering the IHM until it
runs into the bug. It then outputs the set of operations that caused the
problem. Someone could then write a program that just applied these
operations to help nail the bug.

The test case I have got is artifical in the sense that it uses only a
single thread and some random probabilities to find the bug. The albeit
simplified scenario where someone might run into this is like this:

private IdentityHashMap _myMap = new IdentityHashMap();

public synchronized void addItem(ObjectWithState o) { _mapMap.put(o, o); //
note using the IHM as a set hence same key and value but not significant}

public synchronized void removeSomeIterms()
{
     Iterator it = idMap.keySet().iterator();
     while (it.hasNext())
     {
         ObjectWithState s = (ObjectWithState) it.next();

         if (s.isDead())
         {
              it.remove();
         }
    }
}

If you run the above there are certain scenarios where the call to addItem
will just go into an infinite loop.

I have attached a class that illustrates the problem. Just run it and it
detects the infinite loop and prints out the series of operations that
caused the infinite loop. If any part of the code is unclear get back to
me.

Workaroud

The only workaround I could see is "don't use IdentityHashMap if you want
to use an iterator like this". We found this in a third party library but
we can get that changed.

(See attached file: TestIdentityHashMap.java)