技术分享collection

ArrayList的remove(Object o)方法 与It

2019-12-30  本文已影响0人  闲庭

其实我们日常学习的知识点和问题都是一环扣一环的，很多问题都是相关联的，本次主要围绕着以下问题展开 ：

  1. ArrayList的remove(Object o)方法 与Iterator 的remove()方法有什么区别？（会引出Fail-Fast机制）
  2. 什么是Fail-Fast机制与Fail-Safe机制机制？(会引出CopyOnWrite思想)
  3. 什么是CopyOnWrite思想？
  4. CopyOnWrite的使用场景与优缺点？

其实我们平时也会遇到这样的需求：将列表中满足某种条件的数据删除；稍后让我们借助下面这个逻辑来简单描述下，就是将列表中将等于"1002"的元素删除，此处就拿遍历ArrayList集合当作事例，代码如下：

private static void testUnsafeArrayList() {
        List<String> arr = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            arr.add("100"+i);
        }
        Iterator it = arr.iterator();
        while (it.hasNext()) {
            String value = String.valueOf(it.next());
            if ("1002".equals(value)){
                arr.remove(value); //使用这个会抛异常ConcurrentModificationException
//                it.remove();  //arr.remove(value)替换成 it.remove()没异常
            }
        }
        System.out.println("删除后的数据：");
        Iterator tmp = arr.iterator();
        while (tmp.hasNext()) {
            String value = String.valueOf(tmp.next());
            System.out.println(value);
        }
    }

运行结果：
执行代码使用 arr.remove(value)你会发现报错如下：

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
    at java.util.ArrayList$Itr.next(ArrayList.java:859)
    at com.liujc.demo.TestUtil.testUnsafeArrayList(TestUtil.java:69)
    at com.liujc.demo.TestUtil.main(TestUtil.java:38)

Process finished with exit code 1

替换方案：
然后使用it.remove()替换arr.remove(value)即可正常运行：

这是什么原因呢？
原因是迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变 modCount 的值。
每当迭代器使用 hashNext()/next() 遍历下一个元素之前，都会检测 modCount 变量是否为 expectedModCount 值，相等的话就返回遍历；否则抛出异常，终止遍历。

这个理由说的似乎有点道理，我要眼见为实。
接下来让我们根据源码来分析下：
首先我们上面代码中利用了ArrayList的remove方法会抛出异常，其实在remove方法中调用了fastRemove, 在fastRemove中执行modCount++;更新了更改次数，查看源码：

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

private void fastRemove(int index) {
        //此处记修改次数
        modCount++; 
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

在依次遍历迭代器Iterator 时调用其next()方法，通过下面next()源码中可以看到首先调用checkForComodification()方法，该方法主要判断 expectedModCount 是否与 modCount 相等，不相等抛出异常：

public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
final void checkForComodification() {
             //此处的modCount已经在remove操作中变更
            if (modCount != expectedModCount) 
                throw new ConcurrentModificationException();
        }

替换方案中使用迭代器的remove方法为什么没有问题？
查看ArrayList的源码中ListItr继承了Itr，对应的remove()中执行expectedModCount = modCount对expectedModCount重新赋值绕过后续检查，源码如下：

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

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            //此处重新赋值，会绕过后续next()方法中的checkForComodification检查条件
            expectedModCount = modCount;  
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
      }

其实我们在遇到问题时尽量做到不但要知其然还要知其所以然，要有这种探索精神，但是看源码有时候也要点到为止。好了，回归正题，上面这个案例分析其实已经描述了Fail-Fast 机制的实现原理，那么现在对Fail-Fast 机制是否了解了呢？

什么是快速失败机制（Fail-Fast）和 安全失败机制（Fail-Safe）？
也许日常没太注意过这两种机制，但是我们肯定都碰到过，其实在我们平时接触的HashMap、ArrayList 这些集合类，这些在 java.util 包的集合类就都是快速失败的(Fail-Fast)；而 java.util.concurrent 包下的类都是安全失败(Fail-Safe)，比如：CopyOnWriteArrayList等。

Fail-Fast机制

Fail-Safe机制

CopyOnWrite思想（写入时复制）

CopyOnWriteArrayList的整个add操作都是在锁的保护下进行的。
这样做是为了避免在多线程并发add的时候，复制出多个副本出来，可能会出现脏读的情况，导致最终的数组数据不是我们期望的。

    public boolean add(E e) {
     //1、先加锁
     final ReentrantLock lock = this.lock;
     lock.lock();
     try {
         Object[] elements = getArray();
         int len = elements.length;
         //2、拷贝数组
         Object[] newElements = Arrays.copyOf(elements, len + 1);
         //3、将元素加入到新数组中
         newElements[len] = e;
         //4、将array引用指向到新数组
         setArray(newElements);
         return true;
     } finally {
        //5、解锁
         lock.unlock();
     }
    }

线程并发的写，则通过锁来控制，如果有线程并发的读，则分以下几种情况：
1、如果写操作未完成，那么直接读取原数组的数据；
2、如果写操作完成，但是引用还未指向新数组，那么也是读取原数组数据；
3、如果写操作完成，并且引用已经指向了新的数组，那么直接从新数组中读取数据。

上一篇下一篇

猜你喜欢

热点阅读