ConcurrentHashMap returns null if I remove the very next object

Question

I'm trying to understand how a failsafe iterator works. I encountered something strange in concurrent hashmap. The code is as follows --

    ConcurrentHashMap<String,String> hm = new ConcurrentHashMap<String,String>();
    hm.put("name1", "value1");
    hm.put("name2", "value2");
    hm.put("name3", "value3");

    Iterator<String> itr = hm.keySet().iterator();
    int index = 0;
    while(itr.hasNext()) {
        System.out.println(hm.get(itr.next()));
        hm.put(index+"1", index+"2");
        hm.remove("name2");
        index++;
    }
    System.out.println("--- Second iteration --- ");
    Iterator<String> itr2 = hm.keySet().iterator();
    while(itr2.hasNext()) {
        System.out.println(hm.get(itr2.next()));
    }

which prints :

    value3
    null
    value1
    --- Second iteration --- 
    12
    02
    value3
    value1
    22

I'm confused why removing an element in the first case was updated while addition is not! I'm using 1.8 runtime environment.

Answer 1

The Iterator for ConcurrentHashMap navigates the underlying data structure in a way which is thread safe. It does this as a single pass and if a key/entry which it has "passed" it won't see that change. If a change occurs beyond the point which the Iterator has reached, it might see that change if it doesn't change again before it gets there. Here is an example;

Map<Integer, Boolean> map = new ConcurrentHashMap<>();
for (int i = 0; i < 10; i++)
    map.put(i, true);
System.out.println(map.keySet());
List<Integer> ints = new ArrayList<>(map.keySet());
Map<Integer, Boolean> map2 = new ConcurrentHashMap<>();
for (int i = 0; i < 10; i += 2)
    map2.put(ints.get(i), false);
System.out.println("All evens " + map2.keySet());
// all evens
Iterator<Integer> iter = map2.keySet().iterator();
for (int i = 8; i >= 0; i -= 2) {
    // remove evens and add odds
    map2.remove(ints.get(8 - i));
    map2.remove(ints.get(i));
    map2.put(ints.get(i + 1), false);
    System.out.println(iter.next() +" - full set is: "+map2.keySet());
}
while (iter.hasNext())
    System.out.println(iter.next());
System.out.println("All odds " + map2.keySet());

prints

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
All evens [0, 2, 4, 6, 8]
0 - full set is: [2, 4, 6, 9]
2 - full set is: [4, 7, 9]
4 - full set is: [5, 7, 9]
5 - full set is: [3, 5, 7, 9]
7 - full set is: [1, 3, 5, 7, 9]
9
All odds [1, 3, 5, 7, 9]

Note how the keys the iterator sees if NOT the keys set at any given moment. Instead changes which occur after (in this case higher numbers) are visible, but keys which are in it's past (in this case lower numbers) are not.