本文转载自http://shift-alt-ctrl.iteye.com/blog/1839147
在循环arrayLlist时,经常会遇到remove操作,那么arrayList的remove的底层是怎么做的?
AbstractList中,有一个属性modCount,这个属性是跟踪list中数据被修改的次数,任何对list的add/remove操作,都将导致modCount++.
在AbstractList中还有一个内部类Itr implements Iterator,Itr是一个list遍历的工具类,当然list.iterator()方法也是返回Itr对象,在Itr中有一个校验位属性expectedModCount;对于一个itr对象,其初始时expectedModCount=modCount.
Iterator是list一个视图,其最终还是操作list的存储结构.在使用iterator遍历时,remove()操作,会导致modCount++(AbstractList.remove()),但是还有expectedModCount=modCount,即在iterator中remove数据,会带来expectedModCount与modCount值的同步.
在Iterator遍历时,next(),remove()方法会校验expectedModCount与modCount值是否一致,如果不一致,就意味着这list数据在iterator外部被修改,此时iterator遍历将会造成ConcurrentModificationException.
AbstractLlist不仅支持普通的iterator,还支持ListIterator(ArrayList,LinkedList均支持),ListIterator增加了遍历时双向游标能力(previous,next),增加了add方法.add方法和remove方法一样也做了expectedModCount和modCount一致性校验.
引申一下,如下四个对list数据删除的代码,有区别吗??
如下是4中循环方式:
1) for(int i=0;i<list.size();i++){
list.remove(i);
}
2) for(int i=list.size()-1;i>=0;i--){
list.remove(i);
}
3)
int size = list.size();
for(int i=size-1;i>-1;i--){
list.remove(i);
}
4) for(Object i : list){
list.remove(i);//如果list中存在多个Object互相equals时,此方法仍然有效.注意list.remove(Object)内部使用了遍历操作,并使用equals来比较对象并删除.
}
5) Iterator it = list.iterator()
while(it.hasNext()){
it.next();
it.remove();
}
1),2),3)是最普通的遍历方式,但是在遍历并有删除操作时,似乎它们执行的结果还有些差距,根据坐标删除,那么1)实事上只会有一半被删掉,1)中每删除一次,计算一次list.size(),但是当前i++,且前端删除会造成数组结构copy.
2)后端删除,不会造成copy,每次都是删除最后一个位置,直至结束
3)因为size没有重新计算,在删除一半数据后,抛出IndexOutOfBoundsException
4)/5)正常
提示:foreach方式最终是转换成了iterator的方式进行.(产生于编译过程中).
关于fail fast:
在并发的时候,如果线程A正遍历一个collection(List, Map, Set etc.),这时另外一个线程B却修改了该collection的size,线程A就会抛出一个错:ConcurrentModificationException,表明:我正读取的内容被修改掉了,你是否需要重新遍历?或是做其它处理?这就是fail-fast的含义。
Fail-fast是并发中乐观(optimistic)策略的具体应用,它允许线程自由竞争,但在出现冲突的情况下假设你能应对,即你能判断出问题何在,并且给出解决办法。悲观(pessimistic)策略就正好相反,它总是预先设置足够的限制,通常是采用锁(lock),来保证程序进行过程中的无错,付出的代价是其它线程的等待开销:
Doug Lea的concurrent包给出了另外一种解决方案,Copy On Write。它的CopyOnWriteArrayList、CopyOnWriteArraySet会在线程B试图修改数据容器时,给出一个copy出来的容器(当然,我们程序中是感觉不到的),这样线程A在老版本的v上遍历,线程B则在新版本的v上修改,两者互不相干,也决不会出现ConcurrentModificationException。它的代价则主要是在容器的copy上,当并发程度越高,其开销也越高。
所以,Fast Fail被引入JDK的一个基本前提是:你绝大多数的情形,仅仅是在遍历一个collection,不会有另外的线程会对它做update。如此,它的效率是最充分的。但如果你不断遇到ConcurrentModificationException的异常时,则要考虑是否要进行一定次数的重新遍历,或者干脆采用悲观策略锁住资源来保证线程安全。
相关推荐
fail-fast俗称快速失败,是在多线程进行迭代操作时产生冲突的一种异常抛出机制,下面我们就由ArrayList来深入理解Java中的fail-fast机制.
ArrayList数据批量添加数据,供新手参考
ArrayList operator =(const ArrayList& assignArrayList); // Adds and item and returns added item. Array is resized by one. pItemType Add(pItemType anItem); // Removes the item at the given index....
抽象类、AbstractList 抽象类和具体的ArrayList 的实现纵向研究了Java Collections Framework 中的Fail Fast 机制,通常的编程错误以及这些接口和类之间的关系,以有助于大家对Java Collections Framework 源代码的...
day07_15_ArrayList集合存储基本数据类型
一个C++(Ubuntu16.04+QT5.9.1)通过JNI,调用JAVA类及方法的示例。通过JNI传递和返回多种类型的参数,boolean ,int,String,ArrayList,ArrayList嵌套ArrayList<ArrayList<String>>等。
NULL 博文链接:https://312256159-qq-com.iteye.com/blog/1594752
JAVA获取两个数据量较大的ArrayList的交集、差集以及并集,记录一下以便查阅。JAVA获取两个数据量较大的ArrayList的交集、差集以及并集,记录一下以便查阅。JAVA获取两个数据量较大的ArrayList的交集、差集以及并集...
day09-ArrayList集合&学生管理系统.pdf
在jni中操作arraylist对象,然后添加一个int型数据进去
比较分析Vector、ArrayList和hashtable hashmap数据结构
集合ArrayList测试集合ArrayList测试集合ArrayList测试集合ArrayList测试集合ArrayList测试集合ArrayList测试
Fail-Fast机制 由于HashMap(ArrayList)并不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了map(这里的修改是指结构上的修改
第四章 ArrayList集合&学生管理系统.pdf
java中ArrayList的用法
fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时,就可能会产生fail-fast事件。例如:当某一个线程A通过iterator去遍历某集合的过程中,若该集合的内容被其他线程所...
c#数据结构之array,arraylist,hashtable,dictionary
C#中数组与arraylist C#中数组的应用与arraylist的应用 即两者间的区别
ArrayList转化为DataTable数据加载转换方便程序的灵活运用!
java数据结构 ArrayList、Stack、Map,为提高效率,未做边界判断(由开发人员保证逻辑上不会出现越界),实现了添加和查询的功能,无修改删除功能