網頁

2020/7/9

Java For-Each Loop 運作原理

本篇探討Java的For-Each Loop如何運作。

Java For-Each Loop是在Java 1.5引入的Enhanced for Loop特性(參考JSR 201),簡化遍歷集合(Collection)及陣列(Array)的for loop語法。

傳統用來遍歷集合或陣列時的for loop迴圈的方式如下。

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);

for(int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

int[] ints = {1,2,3,4,5};

for(int i = 0; i < ints.length; i++) {
    System.out.println(ints[i]);
}

遍歷很多時候只是要取出元素做計算,沒有要進行交換位置或排列的操作,所以傳統的for loop迴圈寫法顯得囉唆且難以閱讀,因此導入For-Each Loop語法讓程式更好操作及閱讀。

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);

for(Integer i : list) {
    System.out.println(i);
}

int[] ints = {1,2,3,4,5};

for (int i : ints) {
    System.out.println(i);
}

然而For-Each Loop背後實際上是簡化Iterator遍歷集合的語法糖。

下面是透過IntelliJ IDEA內建的反編譯器反編譯上面For-Each Loop程式碼的.class,可以看到集合實際上是用Iterator來遍歷;陣列則是傳統的for loop,此即為For-Each Loop的運作原理。

List<Integer> list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
Iterator var2 = list.iterator();
while(var2.hasNext()) {
    Integer i = (Integer)var2.next();
    System.out.println(i);
}
int[] ints = new int[]{1, 2, 3, 4, 5};
int[] var8 = ints;
int var4 = ints.length;
for(int var5 = 0; var5 < var4; ++var5) {
    int i = var8[var5];
    System.out.println(i);
}


衍伸出的議題為在For-Each Loop中對正在遍歷的集合進行新增或刪除元素等異動集合長度結構的操作時為什麼會丟出java.util.ConcurrentModificationException錯誤。

ArrayList為例在For-Each Loop中新增或刪除元素的方法為集合本身的add(E e)remove(Object o)

List<Integer> list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);

for(Integer i : list) {
    System.out.println(i);
    list.remove(new Integer(5));
}

而這些方法內部都異動了一個modCount屬性,此屬性代表ArrayList長度結構被修改的次數,此為確保遍歷元素時不會被不同的執行緒修改所作的fail-fast設計。

java.util.ArrayList

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ...
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    ...
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity); // 異動了modCount
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    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); // 此方法僅異動modCount
                    return true;
                }
        }
        return false;
    }

    /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    private void fastRemove(int index) {
        modCount++; // 異動了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
    }
    ...
}

For-Each Loop遍歷ArrayList實際上是使用其內部的Itr類別。而在呼叫Itr.next()取得下一個元素時會呼叫checkForComodification()透過判斷modCountexpectedModCount屬性值是否相等來檢查是否被併行修改。

java.util.ArrayList.Itr

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ...
    private class Itr implements Iterator {
        ...
        int expectedModCount = modCount; // Itr初始時expectedModCount與modCount設為相同
        ...
        @SuppressWarnings("unchecked")
        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];
        }

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

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount; // 調整為相同,所以不會造成ConcurrentModificationException
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
        ...
        final void checkForComodification() {
            if (modCount != expectedModCount) // 若modCount與expectedModCount不同拋出ConcurrentModificationException
                throw new ConcurrentModificationException();
        }
    }
    ...
}

而使用ArrayList.remove(Object o)時只會異動modCount,執行到checkForComodification()時判斷modCountexpectedModCount值不同而拋出java.util.ConcurrentModificationException錯誤。若是Itr.remove()其會確保modCountexpectedModCount的值相同而不會拋錯,這就是為什麼遍歷ArrayList時若要刪除元素要轉成Iterator來遍歷的原因。


沒有留言:

張貼留言