學(xué)習(xí)Java Collection Framework的Iterator實(shí)現(xiàn)

VPointer 發(fā)布于2019-08-16 12:31 / 1505人閱讀

摘要：源碼，由于的結(jié)構(gòu)并不是順序的，在執(zhí)行方法時(shí)不能通過指針或下標(biāo)的方式直接找到下一個(gè)元素，為了能達(dá)到這個(gè)目的，在構(gòu)造函數(shù)和方法中預(yù)先做了處理。

繼續(xù)研讀JDK的源碼，在比較HashMap和ConcurrentHashMap的不同之處發(fā)現(xiàn)了一個(gè)細(xì)節(jié)——關(guān)于Iterator的實(shí)現(xiàn)的不同，其實(shí)HashMap和ConcurrentHashMap還有更多不同的地方，這也是面試經(jīng)常問到的問題，有一篇文章我覺得講的很好了，Java進(jìn)階（六）從ConcurrentHashMap的演進(jìn)看Java多線程核心技術(shù)。
Iterator是一種設(shè)計(jì)模式，在Java Collection Framework中經(jīng)常作為容器的視圖(view)，大多數(shù)時(shí)候只支持刪除、不支持增加，提供統(tǒng)一的接口方法等特點(diǎn)。在Java Collection Framework的Iterator實(shí)現(xiàn)中大多數(shù)是fast-fail方式的，而支持并發(fā)的容器數(shù)據(jù)結(jié)構(gòu)則沒有這個(gè)限制。

非并發(fā)數(shù)據(jù)結(jié)構(gòu)的情況 常見的使用方法

1）使用Iterator遍歷字符串列表

List lists = Arrays.asList("a","b","c");
Iterator iterator = lists.iterator();
while (iterator.hasNext()) {
    String val = iterator.next();
    System.out.println(val);
}

這種做法是for..each的語法的展開形式

for(String val: lists){
    //sout
}

2）使用Iterator遍歷LinkedList

LinkedList linkedList = new LinkedList<>(lists);
iterator = linkedList.iterator();
while (iterator.hasNext()) {
    String val = iterator.next();
    System.out.println(val);
}

3）使用Iterator遍歷HashMap

Map hmap = new HashMap<>(3);
hmap.put("a",1);
hmap.put("b",2);
hmap.put("c",3);

Iterator> mapIterator = hmap.entrySet().iterator();
while (mapIterator.hasNext()) {
    Map.Entry entry = mapIterator.next();
    System.out.println(entry.getKey() + ":" + entry.getValue());
}

非并發(fā)數(shù)據(jù)結(jié)構(gòu)Iterator的實(shí)現(xiàn)

1）ArrayList中的Iterator

list中的結(jié)構(gòu)是順序的，Iterator既然是List的視圖，那它也表現(xiàn)了相同的順序。
ArrayList獲得Iterator,

/**
* 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();
}

源碼，

/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size;
    }

    @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;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

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

Itr是ArrayList的一個(gè)內(nèi)部類，它能使用宿主類的成員變量，事實(shí)上Itr反映了ArrayList的內(nèi)部情況，使用了size、expectedModCount和elementData等屬性。通過游標(biāo)cursor的方式不斷往前遞進(jìn)，只要游標(biāo)小于size就說明依然還有元素可以訪問。
應(yīng)該看到的是，在調(diào)用了new Iterator()之后，可以看做Itr對(duì)ArrayList做了快照，這里的快照并不是很嚴(yán)格，是基于modCount比較來實(shí)現(xiàn)的。它在初始化時(shí)備份了modCount的值，保存為私有的變量expectedModCount。

首先Iterator接口并沒有諸如add的方法，即不能通過Iterator來為容器增加元素；
其次，如果有其他線程變化了容器的結(jié)構(gòu)（structural modification），那么ArrayList.this.modCount的值會(huì)發(fā)生改變，那么在Itr執(zhí)行next或者remove方法時(shí)會(huì)判斷出來modCount != expectedModCount的情況，從而拋出異常fast-fail。
再次，如果執(zhí)行了Itr的remove方法，它能夠調(diào)用ArrayList.this.remove的方法，然后修正游標(biāo)和expectedModCount等。

ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;

2）LinkedList中的Iterator

LinkedList的Iterator和ArrayList中的有一些類似的地方。
首先，LinkedList的iterator入口方法其實(shí)是AbstractSequentialList抽象類中，

/**
* Returns an iterator over the elements in this list (in proper
* sequence).
*
* This implementation merely returns a list iterator over the list.
*
* @return an iterator over the elements in this list (in proper sequence)
*/
public Iterator iterator() {
    return listIterator();
}

/**
* Returns a list iterator over the elements in this list (in proper
* sequence).
*
* @param  index index of first element to be returned from the list
*         iterator (by a call to the next method)
* @return a list iterator over the elements in this list (in proper
*         sequence)
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public abstract ListIterator listIterator(int index);

而這個(gè)ListIterator是一個(gè)接口，它被LinkedList$ListItr實(shí)現(xiàn)，

private class ListItr implements ListIterator {
    private Node lastReturned = null;
    private Node next;
    private int nextIndex;
    private int expectedModCount = modCount;

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();

        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

    public int previousIndex() {
        return nextIndex - 1;
    }

    public void remove() {
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();

        Node lastNext = lastReturned.next;
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }

    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }

    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }

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

LinkedList的Iterator要比ArrayList中的復(fù)雜一些，它更支持了add等方法；
類似原來游標(biāo)的遍歷方式，基于size、expectedModCount等比較邏輯依然存在，只不過遍歷的方式不是原來的下標(biāo)增進(jìn)，而是節(jié)點(diǎn)之間的next指針來實(shí)現(xiàn)。

3）HashMap中的Iterator

HashMap有多個(gè)view視圖，keySet, values, entrySet，這里分析下entrySet這個(gè)視圖，另外兩個(gè)原理和entrySet視圖的差不多。

private final class EntrySet extends AbstractSet> {
    public Iterator> iterator() {
        return newEntryIterator();
    }
    public boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry e = (Map.Entry) o;
        Entry candidate = getEntry(e.getKey());
        return candidate != null && candidate.equals(e);
    }
    public boolean remove(Object o) {
        return removeMapping(o) != null;
    }
    public int size() {
        return size;
    }
    public void clear() {
        HashMap.this.clear();
    }
}

EntrySet的iterator方法中調(diào)用了newEntryIterator,將構(gòu)造EntryIterator實(shí)例，
EntryIterator源碼

private final class EntryIterator extends HashIterator> {
    public Map.Entry next() {
        return nextEntry();
    }
}

EntryIterator繼承了HashIterator類，復(fù)用了父類的大部分方法，只是覆蓋了next方法。
HashIterator源碼，

private abstract class HashIterator implements Iterator {
    Entry next;        // next entry to return
    int expectedModCount;   // For fast-fail
    int index;              // current slot
    Entry current;     // current entry

    HashIterator() {
        expectedModCount = modCount;
        if (size > 0) { // advance to first entry
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Entry nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Entry e = next;
        if (e == null)
            throw new NoSuchElementException();

        if ((next = e.next) == null) {
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
        current = e;
        return e;
    }

    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的結(jié)構(gòu)并不是順序的，在執(zhí)行Iterator.next方法時(shí)不能通過next指針或下標(biāo)的方式直接找到下一個(gè)元素，HashIterator為了能達(dá)到這個(gè)目的，在構(gòu)造函數(shù)和nextEntry方法中預(yù)先做了advance處理。

//構(gòu)造函數(shù)中
if (size > 0) { // advance to first entry
    Entry[] t = table;
    while (index < t.length && (next = t[index++]) == null)
        ;
}
//nextEntry中
if ((next = e.next) == null) {
    Entry[] t = table;
    while (index < t.length && (next = t[index++]) == null)
        ;
}

構(gòu)造函數(shù)中預(yù)先在HashMap的table數(shù)組找到第一個(gè)頭結(jié)點(diǎn)不為null的元素；
(next = t[index++]) == null的寫法有點(diǎn)迷惑性，不考慮HashMap為空的情況，index自增停在next != null的情況，即 next = t[index-1], index已經(jīng)往前一步了；

在nextEntry中如果發(fā)現(xiàn)e.next是null，此時(shí)表示table這個(gè)數(shù)組元素的鏈表遍歷結(jié)束了，需要跳到下一個(gè)頭節(jié)點(diǎn)不為空的元素繼續(xù)遍歷，而index剛好往前一步了，此時(shí)繼續(xù)執(zhí)行

next = t[index++]

假設(shè)next[index]不為空，那么下一個(gè)遍歷的數(shù)組元素頭節(jié)點(diǎn)找到，并且index已經(jīng)自增了。

并發(fā)數(shù)據(jù)結(jié)構(gòu)的情況

以ConcurrentHashMap為例，看ConcurrentHashMap$HashInteraotr的實(shí)現(xiàn)

abstract class HashIterator {
    int nextSegmentIndex;
    int nextTableIndex;
    HashEntry[] currentTable;
    HashEntry nextEntry;
    HashEntry lastReturned;

    HashIterator() {
        nextSegmentIndex = segments.length - 1;
        nextTableIndex = -1;
        advance();
    }

    /**
    * Set nextEntry to first node of next non-empty table
    * (in backwards order, to simplify checks).
    */
    final void advance() {
        for (;;) {
            if (nextTableIndex >= 0) {
                if ((nextEntry = entryAt(currentTable,
                                            nextTableIndex--)) != null)
                    break;
            }
            else if (nextSegmentIndex >= 0) {
                Segment seg = segmentAt(segments, nextSegmentIndex--);
                if (seg != null && (currentTable = seg.table) != null)
                    nextTableIndex = currentTable.length - 1;
            }
            else
                break;
        }
    }

    final HashEntry nextEntry() {
        HashEntry e = nextEntry;
        if (e == null)
            throw new NoSuchElementException();
        lastReturned = e; // cannot assign until after null check
        if ((nextEntry = e.next) == null)
            advance();
        return e;
    }

    public final boolean hasNext() { return nextEntry != null; }
    public final boolean hasMoreElements() { return nextEntry != null; }

    public final void remove() {
        if (lastReturned == null)
            throw new IllegalStateException();
        ConcurrentHashMap.this.remove(lastReturned.key);
        lastReturned = null;
    }
}

這里能看到ConcurrentHashMap的segment分段因素所在，在構(gòu)造函數(shù)中指定了最后一個(gè)segment數(shù)組元素，然后做advance處理，也是從后往前處理的。首先找到不為null的分段segment，然后才是在segment的table數(shù)組中找到不為null的元素，這都是從后往前“前進(jìn)”的。

而與HashMap不同的地方，ConcurrentHashMap的Iterator并不是fast-fail的，它并沒有判斷modCount;除此之外還應(yīng)該看到它對(duì)nextEntry的處理，在advance的方法調(diào)用以下兩個(gè)方法，

/**
* Gets the jth element of given segment array (if nonnull) with
* volatile element access semantics via Unsafe. (The null check
* can trigger harmlessly only during deserialization.) Note:
* because each element of segments array is set only once (using
* fully ordered writes), some performance-sensitive methods rely
* on this method only as a recheck upon null reads.
*/
@SuppressWarnings("unchecked")
static final  Segment segmentAt(Segment[] ss, int j) {
    long u = (j << SSHIFT) + SBASE;
    return ss == null ? null :
        (Segment) UNSAFE.getObjectVolatile(ss, u);
}
/**
* Gets the ith element of given table (if nonnull) with volatile
* read semantics. Note: This is manually integrated into a few
* performance-sensitive methods to reduce call overhead.
*/
@SuppressWarnings("unchecked")
static final  HashEntry entryAt(HashEntry[] tab, int i) {
    return (tab == null) ? null :
        (HashEntry) UNSAFE.getObjectVolatile
        (tab, ((long)i << TSHIFT) + TBASE);
}

它們都是調(diào)用了UNSAFE.getObjectVolatile方法，利用了volatile access的方式，相較于上鎖的方式性能更好。

番外篇 JavaScript實(shí)現(xiàn)的Iterator的例子

這個(gè)例子來自MDN的文檔，做法比較簡(jiǎn)潔,迭代器

function makeIterator(array){
    var nextIndex = 0;

    return {
       next: function(){
           return nextIndex < array.length ?
               {value: array[nextIndex++], done: false} :
               {done: true};
       }
    };
}
var it = makeIterator(["yo", "ya"]);
console.log(it.next().value); // "yo"
console.log(it.next().value); // "ya"
console.log(it.next().done);  // true

可以考慮給這個(gè)makeIterator的返回值加上hasNext屬性，

return {
    next: ...,
    hasNext: function() {
        return nextIndex < array.length;
    }
}

JavaScript利用了閉包實(shí)現(xiàn)了Iterator和Java利用內(nèi)部類實(shí)現(xiàn)有相似的地方。

總結(jié)

Iterator的主要目的還是為了表現(xiàn)底層數(shù)據(jù)結(jié)構(gòu)的所有元素，提供一種統(tǒng)一的遍歷方式。在不同的數(shù)據(jù)結(jié)構(gòu)需要針對(duì)不同語義做出改動(dòng)，像LinkedList的支持add方法，像ConcurrentHashMap和HashMap的advance處理，像ConcurrentHashMap那樣不判斷modeCount而使用volatile access等。