Concurrent Hashmap - Fail safe issue

Question

I was trying an example for Fail-Safe using ConcurrentHashMap.

Below is the sample snippet which I tried..

ConcurrentHashMap<String, String> cMap = new ConcurrentHashMap<String, String>();
cMap.put("1", "Windows Phone");
cMap.put("2", "iPhone");
cMap.put("3", "HTC");

Iterator iterator=cMap.keySet().iterator();

while (iterator.hasNext()) {
    System.out.println(cMap.get(iterator.next()));
    cMap.put("Samsung", "S5");
}

The output is:

Windows Phone
HTC
iPhone

This is a Fail-Safe example which I understood.

But when I tried the below example, am getting a different output.

ConcurrentHashMap<String, String> cMap = new ConcurrentHashMap<String, String>();
cMap.put("1", "Windows Phone");
cMap.put("2", "iPhone");
cMap.put("3", "HTC");

Iterator iterator=cMap.keySet().iterator();

while (iterator.hasNext()) {
    System.out.println(cMap.get(iterator.next()));
    cMap.put("4", "S5");
}

The output is

Windows Phone
HTC
S5
iPhone

What is the difference between the above two code snippets. In the second code snippet, I'm adding cMap.put("4", "S5"); and this is getting added. But in the fisrt snippet, am adding cMap.put("Samsung", "S5"); which is not getting added to ConcurrentHashmap. Am I making any mistake or what else could be the reason for this different output.

Thanks in advance.

Answer 1

The concurrent map, as opposed to non concurrent hashmap, does not fast-fail if you add stuff while iterating on it.

However, there is no guarantee about when and if the iterator (or the get() method, or any other read operation) will see newly added/removed elements or not.

From the documentation :

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

EDIT :

The reason behind the coherent different result resides in how ConcurrentHashMap organizes segments and iterates on them.

The keys get mapped to different segments, based on the hash of the key :

"1" -> 15
"2" -> 0
"3" -> 6

"4" -> 5
"Samsung" -> 7

When an iterator is called, it iterates on segments from last to first.

So, at moment 0, the iterator starts from segment 15, where it finds key "1"="Windows phone", that goes in output first.

Then, due to iterator internal implementation, it reaches the next element, which is "3"="HTC" at segment 6.

At this moment the insertion of "S5" gets place. If the key is "4" it will go to segment 5, if the key is "Samsung" it will go to segment 7.

After sending "HTC" to output it searches for the next element.

When the key is "4", it goes to segment 5, and find "4"="S5", and send it to output.

When the key is "Samsung", the entry goes to segment 7, which was already scanned and found empty by the iterator, so it does not find it and goes straight to segment 0 to retrieve "2"="Iphone".

This explains the behaviour.

Answer 2

But in the fisrt snippet, am adding cMap.put("Samsung", "S5"); which is not getting added to ConcurrentHashmap.

This is incorrect. You are adding it to the hash map. Print it out afterwards and you will see that the entry is there.

However, items you add to a hash map while iterating over it may or may not be iterated over by the current iterator. Your two samples exhibit both of those behaviors.

Structures in the java.util.concurrent package don't have the check for modifications while iterating, (what you call the "fail-safe"), because their entire point is to be used concurrently. It's not even guaranteed for the regular containers.