TreeMap Iterator behaviour not consistent upon removal

Question

Today when tying to discover a bug I found the TreeMap iterator behavior a little strange when removing objects. In fact has I tested different uses, in a simple example:

    TreeMap<String, String> map = new TreeMap<String, String>();
    map.put("1", "1");
    map.put("2", "2");
    map.put("3", "3");
    map.put("4", "4");
    map.put("5", "5");

    Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();

     while (iterator.hasNext()) {
        Map.Entry<String, String> entry = iterator.next();
        System.out.println("Before "+entry.getKey());
        iterator.remove();
        System.out.println("After " +entry.getKey());
    }

the result is:

Before 1
After 1 
Before 2
After 2
Before 3
After 3
Before 4
After 4
Before 5
After 5

But if I change it to:

    TreeMap<String, String> map = new TreeMap<String, String>();
    map.put("1", "1");
    map.put("2", "2");
    map.put("3", "3");
    map.put("4", "4");
    map.put("5", "5");

    Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();

            String key = "4";

    while (iterator.hasNext()) {
        Map.Entry<String, String> entry = iterator.next();
        if(entry.getKey().equals(key)){
            iterator.remove();
            System.out.println(entry.getKey());
        }
    }

Then for key = 4 the result is 5 and for key = 5 the result is 5 due to the links being changed upon removal. But why are the behaviors different. JIT? Even if that is the answer, shouldn't they be uniform?

Answer 1

See the Javadoc for Map.Entry for getValue():

Returns the value corresponding to this entry. If the mapping has been removed from the backing map (by the iterator's remove operation), the results of this call are undefined.

The behaviour is undefined once you've removed the entry, hence that may explain why you are getting varying results.

NOTE: Another user, aix, posted a similar answer and I was going to comment on it, but it was deleted/removed for some reason.

EDIT: I'm not sure if this answer is correct, since I just noticed the OP was calling getKey() instead of getValue().

EDIT 2: Thanks to Ed Staub for this: I think the general idea still holds, since the Javadoc for Map.Entry states:

... more formally, the behavior of a map entry is undefined if the backing map has been modified after the entry was returned by the iterator, except through the setValue operation on the map entry.

Answer 2

To answer the question as to why this happens, the comment gives a hint

// If strictly internal, copy successor's element to p and then make p
// point to successor.

AFAIK, this is part of keeping the tree balanced.

What this means if you have only one child node (or none) the node itself is removed. If the node has two children, the node is replaced with its successor.

If you always remove from the start, that node is discarded which you can still use but it is not modified. If you remove the right node from the middle of the tree, the entry is modified to balance the tree so using the entry after removing see the modified entry.