Java遍历HashMap,Set, List, ArraryList 删除(remove)或者修改

遍历list的时候为什么不能修改呢?

具体语言实现不同,这里是一些语言无关的点

  • 如果你在遍历时往数组增加数据,会导致遍历不完整(因为增加了新成员长度变了),或者死循环(因为总是有新的进去)
  • 如果在遍历时删除数据,则会导致数组访问越界(因为长度缩短了,指针指向了一个已经标示为空的区域)
  • 如果你只是在遍历时修改这个节点本身的数据,一般来说是安全的(当然需要看具体场景)

以下默认修改为 list 的 add/remove 操作

  • 首先, java 里面有很多种 list :
      java.util.ArrayList;
      java.util.LinkedList;
      java.util.Stack;
      java.util.Vector;
      java.util.concurrent.CopyOnWriteArrayList;

    其中 CopyOnWriteArrayList在遍历的时候修改是不会出错的,实现方法是读写分离,参考维基 Copy-on-write

  • 其次, java 里面有好几种遍历方式:
    for
    iterator
    foreach
    • for,在 for 循环中修改并没有问题,除非你把要访问的对象删除,数组越界,或者一直add生成无穷序列
    • iterator,你用 iterator.remove() 是不会有问题的,因为 iterator.remove() 会设置
      this.expectedModCount = ArrayList.this.modCount;//(1)

      这样之后遍历执行 iterator.next() 就不会抛异常

      public E next() {
      this.checkForComodification();
      ...
      }
      
      final void checkForComodification() {
      if(ArrayList.this.modCount != this.expectedModCount) {
          throw new ConcurrentModificationException();
      }
      }
    • foreach,本质上是隐式的 iterator (可以用 javap -c 比较字节码),由于没有重新设置 expectedModCount ,当你使用 list.remove() 后遍历执行 iterator.next() 时就会报ConcurrentModificationException
  • 最后,这里面有一个特别的地方,就如果删除的是 list 里倒数第二个值,这样触发 hasNext() 的时候结果正好为 false 退出循环不继续执行 next() 也就不会报错
        public boolean hasNext() {
            return this.cursor != ArrayList.this.size;
        }

PS:使用的JDK是java-8-openjdk-amd64

遍历集合的常用方法如下:
for
iterator
foreach
三者都不支持在遍历中添加新成员(可以考虑用CopyOnWriteArrayList的方式)
只有iterator迭代器支持遍历中删除数据,因为 iterator.remove() 会设置 this.expectedModCount = ArrayList.this.modCount;//(1)
这样之后遍历执行 iterator.next() 就不会抛异常,网上称之为“Fail-Fast(快速失败)机制”

迭代器(Iterator)

  迭代器是一种设计模式,它是一个对象,它可以遍历并选择序列中的对象,而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象,因为创建它的代价小。

  Java中的Iterator功能比较简单,并且只能单向移动:

  (1) 使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时,它返回序列的第一个元素。注意:iterator()方法是java.lang.Iterable接口,被Collection继承。

  (2) 使用next()获得序列中的下一个元素。

  (3) 使用hasNext()检查序列中是否还有元素。

  (4) 使用remove()将迭代器新返回的元素删除。

  Iterator是Java迭代器最简单的实现,为List设计的ListIterator具有更多的功能,它可以从两个方向遍历List,也可以从List中插入和删除元素。

迭代器应用:

 list l = new ArrayList();
 l.add("aa");
 l.add("bb");
 l.add("cc");
 for (Iterator iter = l.iterator(); iter.hasNext();) {
  String str = (String)iter.next();
  System.out.println(str);
 }
 /*迭代器用于while循环
 Iterator iter = l.iterator();
 while(iter.hasNext()){
  String str = (String) iter.next();
  System.out.println(str);
 }
 */

对于数组我们是使用下标来进行处理的:

int[] arrays = new int[10];
   for(int i = 0 ; i < arrays.length ; i++){
       int a = arrays[i]; 
      //do something
   }

对于ArrayList是这么处理的:

List<String> list = new ArrayList<String>(); 
  for(int i = 0 ; i < list.size() ;  i++){
      String string = list.get(i);
      //do something
   }

遍历HashMap的方法有多种,比如通过获取map的keySet, entrySet, iterator之后,都可以实现遍历,然而如果在遍历过程中对map进行读取之外的操作则需要注意使用的遍历方式和操作方法。

public class MapIteratorTest {

    private static Map<Integer, String> map = new HashMap<Integer, String>();

    public static void main(String[] args) {
        //init
        for(int i = 0; i < 10; i++){
            map.put(i, "value" + i);
        }

        for(Map.Entry<Integer, String> entry : map.entrySet()){
             Integer key = entry.getKey();
             if(key % 2 == 0){
            	 System.out.println("To delete key " + key);
                 map.remove(key);
                 System.out.println("The key " + + key + " was deleted");
             }
        }

        System.out.println("map size = " + map.size());
        for(Map.Entry<Integer, String> entry : map.entrySet()){
            System.out.println( entry.getKey() +" = " + entry.getValue());
        }
    }
}

上面代码的输出结果为

To delete key 0
The key 0 was deleted
Exception in thread “main” java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextEntry(HashMap.java:793)
at java.util.HashMap$EntryIterator.next(HashMap.java:834)
at java.util.HashMap$EntryIterator.next(HashMap.java:832)
at com.gpzuestc.collection.MapIteratorTest.main(MapIteratorTest.java:60)

通过上面的输出可以发现第一个偶数key元素已经被成功remove,异常的抛出位置是在迭代器遍历下一个元素的时候。

如果把上面高亮的遍历代码替换成keySet的方式,通过keySet的remove操作同样会在遍历下个元素时抛出异常,示例如下。

        Set<Integer> keySet = map.keySet();
        for(Integer key : keySet){
            if(key % 2 == 0){
                System.out.println("To delete key " + key);
                keySet.remove(key);
                System.out.println("The key " + + key + " was deleted");
             }
        }
To delete key 0
The key 0 was deleted
Exception in thread “main” java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextEntry(HashMap.java:793)
at java.util.HashMap$KeyIterator.next(HashMap.java:828)
at com.gpzuestc.collection.MapIteratorTest.main(MapIteratorTest.java:49)

如果要实现遍历过程中进行remove操作,上面两种方式都不能使用,而是需要通过显示获取keySet或entrySet的iterator来实现。

        Iterator<Map.Entry<Integer, String>> it = map.entrySet().iterator();
        while(it.hasNext()){
            Map.Entry<Integer, String> entry = it.next();
            Integer key = entry.getKey();
            if(key % 2 == 0){
           	 System.out.println("To delete key " + key);
           	 it.remove();    
           	 System.out.println("The key " + + key + " was deleted");
 
            }
        }
To delete key 0
The key 0 was deleted
To delete key 2
The key 2 was deleted
To delete key 4
The key 4 was deleted
To delete key 6
The key 6 was deleted
To delete key 8
The key 8 was deleted
map size = 5
1 = value1
3 = value3
5 = value5
7 = value7
9 = value9

分析原因

其实上面的三种遍历方式从根本上讲都是使用的迭代器,之所以出现不同的结果是由于remove操作的实现不同决定的。

首先前两种方法都在调用nextEntry方法的同一个地方抛出了异常

    final Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Entry<K,V> e = next;
            ...
            ...
     }

这里modCount是表示map中的元素被修改了几次(在移除,新加元素时此值都会自增),而expectedModCount是表示期望的修改次数,在迭代器构造的时候这两个值是相等,如果在遍历过程中这两个值出现了不同步就会抛出ConcurrentModificationException异常。

1、HashMap的remove方法实现

public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

2、HashMap.KeySet的remove方法实现

public boolean remove(Object o) {
    return HashMap.this.removeEntryForKey(o) != null;
}

3、HashMap.HashIterator的remove方法实现

public void remove() {
   if (current == null)
        throw new IllegalStateException();
   if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
   Object k = current.key;
   current = null;
   HashMap.this.removeEntryForKey(k);
   expectedModCount = modCount;
}

以上三种实现方式都通过调用HashMap.removeEntryForKey方法来实现删除key的操作。在removeEntryForKey方法内只要移除了key modCount就会执行一次自增操作,此时modCount就与expectedModCount不一致了,上面三种remove实现中,只有第三种iterator的remove方法在调用完removeEntryForKey方法后同步了expectedModCount值与modCount相同,所以在遍历下个元素调用nextEntry方法时,iterator方式不会抛异常。

    final Entry<K,V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
 
        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
 
        return e;
    }

发散

1、如果是遍历过程中增加或修改数据呢?
增加或修改数据只能通过Map的put方法实现,在遍历过程中修改数据可以,但如果增加新key就会在下次循环时抛异常,因为在添加新key时modCount也会自增。

2、有些集合类也有同样的遍历问题,如ArrayList,通过Iterator方式可正确遍历完成remove操作,直接调用list的remove方法就会抛异常。

//会抛ConcurrentModificationException异常
for(String str : list){
	list.remove(str);
}
 
//正确遍历移除方式
Iterator<String> it = list.iterator();
while(it.hasNext()){
	it.next();
	it.remove();
}

3、jdk为什么这样设计,只允许通过iterator进行remove操作?
HashMap和keySet的remove方法都可以通过传递key参数删除任意的元素,而iterator只能删除当前元素(current),一旦删除的元素是iterator对象中next所正在引用的,如果没有通过modCount、 expectedModCount的比较实现快速失败抛出异常,下次循环该元素将成为current指向,此时iterator就遍历了一个已移除的过期数据。

 

本文:Java遍历HashMap,Set, List, ArraryList 删除(remove)或者修改(遍历list的时候为什么不能修改呢?)

发表评论