How the iterator is failsafe in concurrent hash map

As I know that iterator in the CopyOnWriteArrayList is thread-safe due to snapshot reference to the copy of arrayList at the time of iterator is created, and in this all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array so they do not affect the copy referred by snapshot reference and same for CopyOnWriteArraySet ,

But struggling in case of ConcurrentHashMap , so please share your views how the iterator is fail-safe in case of ConcurrentHaspMap

---

Your question is slightly ambiguous - you mention failsafe in the title but thread-safe in the body. I am assuming you mean thread-safe.

From the sample source at GrepCode

... Retrieval operations (including get) generally do not block, so may overlap with update operations (including put and remove). Retrievals reflect the results of the most recently completed update operations holding upon their onset. For aggregate operations such as putAll and clear, concurrent retrievals may reflect insertion or removal of only some entries. Similarly, Iterators 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 java.util.ConcurrentModificationException.

so iteration is thread safe but they define the contract as Iterators and Enumerations return elements reflecting the state of the hash table at some point at or since the creation of the iterator/enumeration .

---

From the docs: "Similarly, Iterators and Enumerations return elements reflecting the state of the hash table at some point at or since the creation of the iterator/enumeration."

The iterators generated by ConcurrentHashMap point to the hash table array as of when the iterator was created, so they don't account for updates that cause the hash table to be resized, which is allowed by their spec. Iterating through the hash buckets is safe because the hash bucket references are volatile .

---

Well, all a hash map is (at least, conceptually, the real implementation is a bit more complicated) is an array of linked lists. A fail safe ( not thread safe ) iterator can be implemented very trivially by traversing the linked lists one-by-one, from first node to last. Something like this would work:

public boolean hasNext() { 
   if(next != null) return true;
   currentNode = currentNode == null ? null : currentNode.next; // volatile
   while(currentNode == null && ++currentIndex < buckets.length) // assume the length is fixed for simplicity
       currentNode = buckets[currentIndex].head; // also volatile
   if(currentNode != null) next = currentNode.data;
   return currentNode != null;
}

public Object next { 
    if(!hasNext()) throw new NoSuchElementException();
    Object result = next;
    next = null;
    return result;
}

This is not really specific to ConcurrentHashMap , they could have implemented it this way for regular maps as well, but chose not to. Why? Well, because a "regular" map is not thread safe, modifying it concurrently is not a good idea, so, if that happens, chances are it is a mistake rather than an intentional occurrence, so, it is better to "fail fast", as soon as such situation is detected rather than ignore it, and proceed, risking potential subtle and hard to diagnose inconsistencies in the future.

If you ask me if I agree with this last statement, the answer is a resounding "no" :) But apparently, there were enough people among java designers, who did, at least back when this decision was made.

链接地址: http://www.djcxy.com/p/76116.html

上一篇: CopyOnWriteArraySet何时有用于实现线程

下一篇: 迭代器如何在并发哈希映射中失效保护