一、fail-fast机制

本来准备看一下concurrentHashMap，但是发现对多线程的一些机制还不是很清楚，比如fail-fast机制，在List和HashMap中都遇到了，但是当时都是直接略过，所以在此总结一下该机制。

1、定义

“快速失败”也就是fail-fast，它是Java集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。记住是有可能，而不是一定。

例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。

2、产生原因

要了解fail-fast机制，我们首先要对ConcurrentModificationException 异常有所了解。当方法检测到对象的并发修改，但不允许这种修改时就抛出该异常。同时需要注意的是，该异常不会始终指出对象已经由不同线程并发修改，如果单线程违反了规则，同样也有可能会抛出该异常。

诚然，迭代器的快速失败行为无法得到保证，它不能保证一定会出现该错误，但是快速失败操作会尽最大努力抛出ConcurrentModificationException异常，所以因此，为提高此类操作的正确性而编写一个依赖于此异常的程序是错误的做法，正确做法是：ConcurrentModificationException 应该仅用于检测 bug。

下面看一下List和HashMap中是如何实现这一机制的

二、List中的fail-fast机制

最常用的ArrayList和LinkedList都继承自AbstractList（LinkedList继承自AbstractSequentialList，而AbstractSequentialList继承自AbstractList）。

1、modCount

在AbstractList中定义了变量modCount，顾名思义，它表示的就是修改次数。

1	protected transient int modCount = 0;

这个变量是实现这一机制的关键，在子类中都会通过判断它来判断集合是否被修改。

2、ArrayList中的实现

2.1、modCount++

这个变量什么时候会改变呢，直接在源码中搜索modCount++：

  public void trimToSize() {
      modCount++;
      /** 省略此处代码 */  
  }

  private void ensureExplicitCapacity(int minCapacity) {
      modCount++;
     /** 省略此处代码 */  
  }

  public E remove(int index) {
      rangeCheck(index);
      modCount++;
      /** 省略此处代码 */  
      return oldValue;
  }

  private void fastRemove(int index) {
      modCount++;
      /** 省略此处代码 */  
  }

  public void clear() {
      modCount++;
/** 省略此处代码 */  
  }

  protected void removeRange(int fromIndex, int toIndex) {
      modCount++;
      /** 省略此处代码 */  
  }

  public boolean removeIf(Predicate<? super E> filter) {
      /** 省略此处代码 */  
          modCount++;
     /** 省略此处代码 */  
  }

  public void replaceAll(UnaryOperator<E> operator) {
      /** 省略此处代码 */  
      modCount++;
  }

  public void sort(Comparator<? super E> c) {
      /** 省略此处代码 */  
      modCount++;
  }

以上就是修改modCount的所有操作了，可以看出，在add、remove、clear等涉及改变ArrayList元素个数的操作是，modCount都会+1。

注意一点，就是set方法的时候并没有改变这个值，也就是说是这个变量的修改指的是结构上面的修改，而不是简单的修改集合元素的内容。

2.2、listIterator

接下来就看一下什么时候回产生这个异常，ail-fast是在操作迭代器时产生的，下面看一下ArrayList的迭代器

 public ListIterator<E> listIterator() {
     return new ListItr(0);
 }

 private class ListItr extends Itr implements ListIterator<E> {
     ListItr(int index) {
         super();
         cursor = index;
     }
     /** 省略此处代码 */  
     public E previous() {
         checkForComodification();
         /** 省略此处代码 */  
     }
     public void set(E e) {
         /** 省略此处代码 */  
         checkForComodification();
         /** 省略此处代码 */  
     }
     public void add(E e) {
         checkForComodification();
/** 省略此处代码 */  
     }
 }

 private class Itr implements Iterator<E> {
     int cursor;       // index of next element to return
     int lastRet = -1; // index of last element returned; -1 if no such
     int expectedModCount = modCount;

     /** 省略此处代码 */  
     public E next() {
         checkForComodification();
         /** 省略此处代码 */  
     }
     public void remove() {
         /** 省略此处代码 */  
         checkForComodification();
         /** 省略此处代码 */  
     }
     public void forEachRemaining(Consumer<? super E> consumer) {
         /** 省略此处代码 */  
         checkForComodification();
     }

     final void checkForComodification() {
         if (modCount != expectedModCount)
             throw new ConcurrentModificationException();
     }
 }

可以看出，迭代器在调用next、remove、add、set等方法时，都会先调用checkForComodification方法，该方法和很简单，判断modCount != expectedModCount的话就抛出异常，而expectedModCount在迭代器初始化的时候就指定了等于modCount，在迭代过程中如果有其他线程改变结构导致modCount发生变化，这里就会抛出异常。

有两个线程（线程A，线程B），其中线程A负责遍历list、线程B修改list。线程A在遍历list过程的某个时候（此时expectedModCount = modCount=N），线程启动，同时线程B增加一个元素，这是modCount的值发生改变（modCount + 1 = N + 1）。线程A继续遍历执行next方法时，通告checkForComodification方法发现expectedModCount = N ，而modCount = N + 1，两者不等，这时就抛出ConcurrentModificationException 异常，从而产生fail-fast机制。

2、LinkedList中的实现

与ArrayList的实现基本一致，只是方法上上有不同，就不再贴代码了。

3、遍历List删除元素的方法

有一道面试题就是：如何在遍历ArrayList的时候删除一个元素？

这个问题看似很简单，但其实暗藏玄机。比如，正常来讲用for-each直接遍历并删除

List<String> list=new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
for(String s: list){
	if(s.equals("a")){
		list.remove(s);
	}
}

会直接抛出java.util.ConcurrentModificationException。因为for-each实际上使用的是List的迭代器，而在迭代过程中，删除了一个元素就相当于List的结构发生了变化，就会抛出上文所说的ConcurrentModificationException。

那么怎样才能正确的遍历并且删除元素呢，必须得用到Iterator的remove方法，比如：

List<String> list=new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
Iterator<String> i=list.iterator();
while(i.hasNext()){
	String s=i.next();
	if(s.equals("a")){
		i.remove();//必须的迭代器的remove方法
	}
}

那么为什么迭代器的remove方法就不会抛出异常呢？再来看一下源码就知道了：

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    //省略

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    //省略
}

可以看出，调用remove方法之后，通过expectedModCount = modCount;来修改了expectedModCount 的值，这样就相当于迭代器自己遍历的时候，是可以对List的结构进行修改的。

三、HashMap中的fail-fast机制

通过ArrayList的分析可以了解到fail-fast机制的原理，其实在各个类的实现中应该都是差不多的，只是细节上略有不同。

1、modCount

HashMaP的modCount 变量是直接定义在本类中的，而不是像ArrayList一样在父类的抽象类中

1	transient int modCount;

还有一个比较奇葩的地方就是，在ArrayList中，modCount改变的时候都是modCount++;

而在HashMap中，既有modCount++; 又有++modCount; 这点不是很理解

2、HashIterator

HashMap与List的另一点重要的不同在于，HashMap无法直接返回迭代器，因为它存储的是键值对，在源码分析的时候说过它可以返回三类Collection的集合，而这些集合才可以产生迭代器。

// Views  
Set<K> keySet();  
Collection<V> values();  
Set<Map.Entry<K, V>> entrySet();

再看看他们如何返回迭代器

public Set<K> keySet() {
    Set<K> ks;
    return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
}
final class KeySet extends AbstractSet<K> {
    /** 省略此处代码 */  
    public final Iterator<K> iterator()     { return new KeyIterator(); }
    /** 省略此处代码 */  
}

public Collection<V> values() {
    Collection<V> vs;
    return (vs = values) == null ? (values = new Values()) : vs;
}
final class Values extends AbstractCollection<V> {
    /** 省略此处代码 */  
    public final Iterator<V> iterator()     { return new ValueIterator(); }
    /** 省略此处代码 */  
}

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    /** 省略此处代码 */  
    public final Iterator<Map.Entry<K,V>> iterator() {
        return new EntryIterator();//为什么这里要另起一行！！！！！！！！！！！！！！！
    }
    /** 省略此处代码 */  
}

可以看出，三个方法返回的迭代分别是新建的一个KeyIterator、ValueIterator、EntryIterator。

那么再来看一下这三个类：

   
final class KeyIterator extends HashIterator
       implements Iterator<K> {
       public final K next() { return nextNode().key; }
   }

   final class ValueIterator extends HashIterator
       implements Iterator<V> {
       public final V next() { return nextNode().value; }
   }

   final class EntryIterator extends HashIterator
       implements Iterator<Map.Entry<K,V>> {
       public final Map.Entry<K,V> next() { return nextNode(); }
   }

又都同时继承同一个父类HashIterator，只是对自己相关的方法进行了重写，那么再看这个最终的类：

abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        /** 省略此处代码 */  
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Node<K,V> nextNode() {
        /** 省略此处代码 */  
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        /** 省略此处代码 */  
    }

    public final void remove() {
        /** 省略此处代码 */  
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        /** 省略此处代码 */  
    }
}

这个就和上面的ArrayList很像了，在最开始的时候指定expectedModCount，并且每次nextNode和remove的时候检查，如果modCount != expectedModCount不相等则抛出异常。

3、++modCount

接下来也看一下map中的哪些操作会导致modCount值的改变

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    /** 省略此处代码 */  
    ++modCount;
    /** 省略此处代码 */  
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    /** 省略此处代码 */  
            ++modCount;
   /** 省略此处代码 */  
}

public V computeIfAbsent(K key,
                         Function<? super K, ? extends V> mappingFunction) {
    /** 省略此处代码 */  
    ++modCount;
    /** 省略此处代码 */  
}

public V compute(K key,
                 BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    /** 省略此处代码 */  
        ++modCount;
    /** 省略此处代码 */  
}
public V merge(K key, V value,
               BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
    /** 省略此处代码 */  
        ++modCount;
        ++size;
    /** 省略此处代码 */  
}

还有一个就是下面这个，我这强迫症真是没法忍了，上面的三个迭代器风格不一样也就算了，连个自加操作都没法统一

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

可以看出，HashMap也是新加或者删除结点等对结构有改变的操作时modCount发生改变。

四、解决方案

怎样避免产生这个异常，要么就是直接涉及多线程的直接加锁串行执行，但是这样的话会严重影响效率，在Java并发编程实战这本书中，有一节叫做并发容器，介绍了专门为多线程并发访问设计的容器。

1、CopyOnWriteArrayList

ArrayList 的一个线程安全的变体，其中所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制来实现的。

它的线程安全性在于，只要正确的发布一个事实不可变的对象，那么在访问该对象的时候就不需要再进一步的同步。在每次修改时，都会创建并重新发布一个新的容器副本，从而实现可变性。

CopyOnWriterArrayList不会产生ConcurrentModificationException异常，并且返回的元素与迭代器创建时的元素完全一致，而不必考虑之后修改操作带来的影响。

由于每次修改容器都会复制底层数组，需要很大的开销，特别是容器规模很大的时候。所以，只有当迭代操作远远多于修改操作的时候，才使用这个容器。

2、concurrentHashMap

就是下面要分析到的concurrentHashMap