Java 迭代器引發(fā) ConcurrentModificationException

用戶83 發(fā)布于2019-08-19 11:48 / 2936人閱讀

摘要：迭代器智能嗎第一步，將列表中的根節(jié)點找出來。源碼翻開中迭代器的源碼。在迭代器對象執(zhí)行操作之前，都會執(zhí)行方法，以判斷當(dāng)前操作下是否安全。

引言

ConcurrentModificationException這個異常大家都很熟悉，當(dāng)在forEach進行刪除時都會出現(xiàn)該異常。

如果你還不了解，請參考澍澍的博客：關(guān)于在list循環(huán)的過程中進行刪除的處理 - 晨澍的博客

ConcurrentModificationException的解決方案之一是使用迭代器，但是不代表迭代器就一勞永逸了。

使用的時候還需斟酌數(shù)組的索引。

描述 問題場景

如下圖所示：

原來的同步方法獲取的節(jié)點是節(jié)點的父節(jié)點，根據(jù)父節(jié)點進行對應(yīng)。

然而在同步更新文件的時候，發(fā)現(xiàn)這樣并不好處理，在不改動原代碼的情況下，設(shè)計了將列表轉(zhuǎn)為樹型結(jié)構(gòu)的方法，這樣可以從根節(jié)點向下開始遍歷，便于操作。

也是在牛客網(wǎng)身經(jīng)百戰(zhàn)，實現(xiàn)這個難度不大。但在編寫相關(guān)實現(xiàn)的時候，遇到了一個小問題。

迭代器智能嗎？

第一步，將列表中的根節(jié)點找出來。

@Override
public ClusterNode listToTree(List clusterNodes) {
    logger.debug("聲明根節(jié)點名稱");
    final String ROOT_NAME = "ROOT";

    logger.debug("聲明根節(jié)點");
    ClusterNode rootNode = null;

    logger.debug("獲取迭代器，遍歷節(jié)點列表");
    Iterator iterator = clusterNodes.iterator();
    while (iterator.hasNext()) {

        logger.debug("向后遍歷");
        ClusterNode clusterNode = iterator.next();

        if (ROOT_NAME.equals(clusterNode.getName())) {
            logger.debug("獲取到根節(jié)點，賦值，并從原列表中移除");
            rootNode = clusterNode;
            iterator.remove();
            break;
        }
    }

    logger.debug("設(shè)置子節(jié)點");
    assert rootNode != null;
    setChildrenNode(rootNode, clusterNodes);

    return rootNode;
}

第二步，再從根節(jié)點開始，遞歸設(shè)置子節(jié)點。

/**
 * 為節(jié)點設(shè)置符合條件的子節(jié)點，同時遞歸，設(shè)置子節(jié)點的子節(jié)點
 * @param parentNode   父節(jié)點
 * @param clusterNodes 子節(jié)點列表
 */
private void setChildrenNode(ClusterNode parentNode, List clusterNodes) {
    logger.debug("清空原集合");
    parentNode.getClusterNodes().clear();

    logger.debug("遍歷列表");
    Iterator iterator = clusterNodes.iterator();
    while (iterator.hasNext()) {
        ClusterNode clusterNode = iterator.next();

        logger.debug("如果父節(jié)點匹配");
        if (clusterNode.getParentClusterNode().getName().equals(parentNode.getName())) {
            logger.debug("將當(dāng)前節(jié)點添加到父節(jié)點的子列表中");
            parentNode.getClusterNodes().add(clusterNode);

            logger.debug("移除該節(jié)點");
            iterator.remove();

            logger.debug("遞歸設(shè)置子節(jié)點");
            setChildrenNode(clusterNode, clusterNodes);
        }
    }
}

思想肯定是沒問題的。

調(diào)用了一行遞歸，當(dāng)我在編寫這行代碼的時候就已經(jīng)察覺到可能不對了，因為本次迭代器還沒有迭代完，條件符合時就去遞歸，然后遞歸又去新建迭代器，遞歸中又可能刪除新元素，再遞歸回來，繼續(xù)迭代的結(jié)果還正確嗎？

logger.debug("遞歸設(shè)置子節(jié)點");
setChildrenNode(clusterNode, clusterNodes);

本著完全相信JDK的思想，興許我憂慮的事情，其實大牛們早就幫我解決了呢？雖然感覺可能不對，但還是這樣寫了。想著把測試用例寫得完善一些，錯了再改唄！

測試

一測試，果然出錯了！在調(diào)用next方法時拋出了ConcurrentModificationException異常，看來，迭代器還沒有智能到如此地步。

源碼

翻開ArrayList中迭代器的源碼。(自從上次在慕課網(wǎng)的驅(qū)動下，強制自己閱讀了HashMap的源碼后，發(fā)現(xiàn)自己對讀源碼沒那么抗拒了。)

在刷過編程題后，終于明白為什么這些家公司都問HashMap源碼，HashMap真的是太重要了，可以在實際業(yè)務(wù)中大大降低算法的時間復(fù)雜度！

/**
 * Returns an iterator over the elements in this list in proper sequence.
 *
 * The returned iterator is fail-fast.
 *
 * @return an iterator over the elements in this list in proper sequence
 */
public Iterator iterator() {
    return new Itr();
}

迭代器方法內(nèi)部就返回了一個Itr的對象，這是ArrayList中的私有內(nèi)部類，為什么要用內(nèi)部類呢？一大好處就是內(nèi)部類可以直接訪問外部類的私有成員，具體進行集合操作的時候非常方便。

ConcurrentModificationException，因為十分常見，所以我們常常只關(guān)注了這個異常怎么出現(xiàn)的，往往忽略了異常本身。

并發(fā)修改異常，最簡單的場景，就是線程不安全的多線程并發(fā)場景。

在迭代器對象執(zhí)行操作之前，都會執(zhí)行checkForComodification方法，以判斷當(dāng)前操作下是否安全。就像下面的代碼實現(xiàn)一樣，判斷當(dāng)前的數(shù)量是否是我預(yù)期的數(shù)量。

如果不是，表示有人動過我的列表，拋異常，不干了。

如果是，表示沒有人動過我的列表，才繼續(xù)執(zhí)行。

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

解決方案

既然出現(xiàn)了問題，怎么解決呢？

那就不要在遍歷的過程中再去遞歸修改了，等他遍歷完再說。添加一個待處理的列表，遍歷之后再遞歸，保證每次迭代都不沖突。

logger.debug("下一次需要處理的父節(jié)點");
List nextParentNodes = new ArrayList<>();

logger.debug("遍歷列表");
Iterator iterator = clusterNodes.iterator();
while (iterator.hasNext()) {
    ClusterNode clusterNode = iterator.next();

    logger.debug("如果父節(jié)點匹配");
    if (clusterNode.getParentClusterNode().getName().equals(parentNode.getName())) {
        logger.debug("將當(dāng)前節(jié)點添加到父節(jié)點的子列表中");
        parentNode.getClusterNodes().add(clusterNode);

        logger.debug("移除該節(jié)點");
        iterator.remove();

        logger.debug("添加到下一次父節(jié)點中");
        nextParentNodes.add(clusterNode);
    }
}

logger.debug("遞歸處理所有待處理的父節(jié)點");
for (ClusterNode clusterNode : nextParentNodes) {
    setChildrenNode(clusterNode, clusterNodes);
}

總結(jié)

迭代器并非一勞永逸，保證多次修改的獨立才是最佳實踐。