Why is removing the 1st entry from a ConcurrentHas

Question

I created an iterator() and then removed the 1st entry from the map before iterating it. I always get the 1st item returned from the iterator. But when I remove the 2nd or subsequent entries, the current iterator does not return that entry.

Example of removing 1st entry from map:

    Map<Integer,Integer> m1 = new ConcurrentHashMap<>();
    m1.put(4, 1);
    m1.put(5, 2);
    m1.put(6, 3);
    Iterator i1 = m1.entrySet().iterator();
    m1.remove(4);        // remove entry from map
    while (i1.hasNext())
        System.out.println("value :: "+i1.next()); //still shows entry 4=1

and the output is:

value :: 4=1
value :: 5=2
value :: 6=3

Example of removing 3rd entry from map:

    Map<Integer,Integer> m1 = new ConcurrentHashMap<>();
    m1.put(4, 1);
    m1.put(5, 2);
    m1.put(6, 3);
    Iterator i1 = m1.entrySet().iterator();
    m1.remove(6);        // remove entry from map
    while (i1.hasNext())
        System.out.println("value :: "+i1.next()); //does not show entry 6=3

and the output is:

value :: 4=1
value :: 5=2

Why is removing the 1st entry from the map not reflected in the iterator, but removing the 2nd or subsequent entry is?

The Java documentation says:

Iterators, Spliterators and Enumerations return elements reflecting the state of the hash table at some point at or since the creation of the iterator/enumeration. They do not throw ConcurrentModificationException.

That means, its iterators reflect the state of the hash table at the point of creation of the iterator. And when we add or remove an entry to or from the Map, the Iterator will show the original entries?

Answer 1

To achieve exactly once iteration behavior, when you remove an element via the Iterator object, the iterator data structure would need to be updated to keep it in step with what has happened to the collection. This is not possible in the current implementations because they don't keep links to the outstanding iterators. And if they did, they would need to use Reference objects or risk memory leaks.

The iterator is guaranteed to reflect the state of the map at the time of it's creation. Further changes may be reflected in the iterator, but they do not have to be.

Think Iterator as a LinkedList and you have head reference with you. If you happen to remove the head from linked list and does not reset the head.next value and start iterating from head you still be traversing the from the same head because you are using an outdated head reference. But when you remove non-head elements the prior element.next is updated.

Answer 2

The answer is in the documentation you quoted:

Iterators, Spliterators and Enumerations return elements reflecting the state of the hash table at some point at or since the creation of the iterator/enumeration.

At OR since. The iterator might or might not show changes to the map since the iterator's creation.

It is not practical for the designers to enforce more precise behavior during concurrent modification and iteration, but it is not broken.

Answer 3

Actual value check is done in next(),

public final Map.Entry<K,V> next() {
    Node<K,V> p;
    if ((p = next) == null)
        throw new NoSuchElementException();
    K k = p.key;
    V v = p.val;
    lastReturned = p;
    advance();
    return new MapEntry<K,V>(k, v, map);
}

advance method advances if possible, returning next valid node, or null if none.

So for first entry K k = 4; V v = 1; even if it is removed. But for subsequent k,v would decided with update fromadvance()

So if you call next() after remove, it won't be there(which is obvious),

Map<Integer,Integer> m1 = new ConcurrentHashMap<>();
m1.put(4, 1);
m1.put(5, 2);
m1.put(6, 3);
Iterator<Map.Entry<Integer, Integer>> i1 = m1.entrySet().iterator();
m1.remove(4);        // remove entry from map
i1.next();  

while (i1.hasNext())
    System.out.println("value :: "+i1.next());

Answer 4

According to this iterators and spliterators are weakly consistent. The definition of "weakly consistent" can be found here:

Most concurrent Collection implementations (including most Queues) also differ from the usual java.util conventions in that their Iterators and Spliterators provide weakly consistent rather than fast-fail traversal:

• they may proceed concurrently with other operations
• they will never throw ConcurrentModificationException
• they are guaranteed to traverse elements as they existed upon construction exactly once, and may (but are not guaranteed to) reflect any modifications subsequent to construction.

Which means that any modifications made after an iterator has been created may be reflected, but it's not guaranteed. That's just a normal behaviour of a concurrent iterator\spliterator.