对于循环与迭代器,以避免带有ArrayList的ConcurrentModificationException



问题:在ArrayList中添加、删除和修改项的最佳(性能方面)解决方案是什么,同时避免在操作过程中抛出ConcurrentModificationException

上下文:根据我对这个问题的研究,似乎没有任何直接的答案来回答手头的问题-大多数人建议使用CopyOnWriteArrayList,但我的理解是,对于大尺寸的数组列表(我正在处理,因此是问题的性能方面),不建议使用。

因此,我的理解可以总结如下,但我想确定是否正确/不正确:

重要提示:以下语句都假定操作是在同步块内完成的

  • ArrayList迭代期间的移除应使用Iterator执行,因为如果在集合中间执行移除,for循环会导致不可预测的行为。示例:
Iterator<Item> itemIterator = items.iterator();
while (itemIterator.hasNext()) {
Item item = itemIterator.next();
// check if item needs to be removed
itemIterator.remove();
}
  • 对于添加操作,不能用Iterator完成,但可以用ListIterator完成。示例:
ListIterator<Item> itemIterator = list.listIterator();
while(itemIterator.hasNext()){
\ do some operation which requires iteration of the ArrayList
itemIterator.add(item);                
}
  • 对于添加操作,不一定要使用ListIterator(即,简单的items.add(item)不应该引起任何问题)
  • 对于,在遍历集合时添加操作可以使用ListIterator或For循环来完成,但不能使用Iterator。示例:
Iterator<Item> itemIterator = item.iterator();
while (itemIterator.hasNext()) {
\ do some operation which requires iteration of the ArrayList
items.add(item); \ NOT acceptable - cannot modify ArrayList while in an Iterator of that ArrayList
}
  • 可以使用具有相同性能复杂度的Iterator或for循环来修改ArrayList中的项(这是真的吗?)。示例:
\ iterator example
Iterator<Item> itemIterator = item.iterator();
while (itemIterator.hasNext()) {
Item item = itemIterator.next();
item.update(); // modifies the item within the ArrayList during iteration
}
\ for loop example
for (Item item : items){
item.update();
}

在使用Iterator的迭代过程中的修改是否具有与for循环相同的性能?两种方法之间是否存在线程安全性差异?

额外的问题:如果还需要同步块,那么使用ArrayList的synchronizedList进行添加/删除/修改操作与循环与迭代器相比有什么优势?

while循环和for循环之间没有区别,事实上,明确使用迭代器的循环的惯用形式是for循环:

for(Iterator<Item> it = items.iterator(); it.hasNext(); ) {
Item item = it.next();
item.update();
}

它被编译成与完全相同的代码

for(Item item: items) {
item.update();
}

在线试用!

对于依赖于用于生成它的原始源代码的相同编译代码,没有性能差异


在插入或删除ArrayList的元素时,您必须关注基本限制,而不是关注循环形式。每次插入或删除元素时,受影响索引后面的元素都必须复制到新位置。这并不昂贵,因为数组只包含对对象的引用,但重复执行时,成本很容易相加。

因此,如果您知道插入或删除的数量很小,或者将发生在末尾或接近末尾(因此只有少量元素需要复制),这就不是问题。但是,当在循环中的任意位置插入或删除任意数量的元素时,会遇到二次时间复杂度

你可以通过使用来避免这种情况

items.removeIf(item -> /* check and return whether to remove the item*/);

这将使用内部迭代并推迟元素的移动,直到知道它们的最终位置,从而导致线性时间复杂性

如果这不可行,最好将列表复制到一个新列表中,跳过不需要的元素。这将稍微不那么有效,但仍然具有线性时间复杂性。这也是在任意位置插入大量项目的解决方案。


item.update();属于完全不同的类别。"ArrayList中的项目"是一种错误的心态。如上所述,ArrayList包含对对象的引用,而对象本身不受"位于ArrayList内"的影响。事实上,对象可以同时位于多个集合中,因为所有标准集合都只包含引用。

因此,item.update();更改了Item对象,这是一个独立于ArrayList的操作,当您基于列表假设线程安全时,这是危险的。

当你有这样的代码时

Item item = items.get(someIndex);
// followed by using item

其中get来自synchronizedList

或将项目返回给调用者的手动同步检索操作,或在synchronized块外部使用检索到的Item的任何其他形式的代码,

您的代码不是线程安全的。当update()调用在同步或锁定下完成时,当在列表上循环时,当其他用途在同步或锁之外时,这并没有帮助。为了线程安全,对象的所有使用都必须由相同的线程安全构造保护。


因此,即使在使用synchronizedList时,您不仅必须手动保护循环,正如文档已经告诉的那样,还必须将保护扩展到所包含元素的所有其他用途,如果它们是可变的。

或者,如果你知道自己在做什么,你可以对列表和所包含的元素使用不同的机制,但这仍然意味着"用synchronizedList包装列表"的简单性不存在。

那么它有什么优势呢?实际上没有。在从Java 1.1及其完全同步的VectorHashtable迁移到Java 2的Collection API的过程中,它可能对开发人员有所帮助。但我从来没有使用过同步的包装器。任何非平凡的用例都需要手动同步(或锁定)。

最新更新