skip to content
Honwhy Wang

学习Java Collection Framework的Iterator实现

/ 13 min read

jdk, java

继续研读JDK的源码，在比较HashMap和ConcurrentHashMap的不同之处发现了一个细节——关于Iterator的实现的不同，其实HashMap和ConcurrentHashMap还有更多不同的地方，这也是面试经常问到的问题，有一篇文章我觉得讲的很好了，Java进阶（六）从ConcurrentHashMap的演进看Java多线程核心技术。 Iterator是一种设计模式，在Java Collection Framework中经常作为容器的视图(view)，大多数时候只支持删除、不支持增加，提供统一的接口方法等特点。在Java Collection Framework的Iterator实现中大多数是fast-fail方式的，而支持并发的容器数据结构则没有这个限制。

非并发数据结构的情况

常见的使用方法

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

List<String> lists = Arrays.asList("a","b","c");
Iterator<String> 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<String> linkedList = new LinkedList<>(lists);
iterator = linkedList.iterator();
while (iterator.hasNext()) {
    String val = iterator.next();
    System.out.println(val);
}

3） 使用Iterator遍历HashMap

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


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

非并发数据结构Iterator的实现

1）ArrayList中的Iterator

list中的结构是顺序的，Iterator既然是List的视图，那它也表现了相同的顺序。 ArrayList获得Iterator,

/**
* Returns an iterator over the elements in this list in proper sequence.
*
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
    return new Itr();
}

源码，

/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
    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的一个内部类，它能使用宿主类的成员变量，事实上Itr反映了ArrayList的内部情况，使用了size、expectedModCount和elementData等属性。通过游标cursor的方式不断往前递进，只要游标小于size就说明依然还有元素可以访问。 应该看到的是，在调用了new Iterator()之后，可以看做Itr对ArrayList做了快照，这里的快照并不是很严格，是基于modCount比较来实现的。它在初始化时备份了modCount的值，保存为私有的变量expectedModCount。

首先Iterator接口并没有诸如add的方法，即不能通过Iterator来为容器增加元素； 其次，如果有其他线程变化了容器的结构（structural modification），那么ArrayList.this.modCount的值会发生改变，那么在Itr执行next或者remove方法时会判断出来modCount != expectedModCount的情况，从而抛出异常fast-fail。 再次，如果执行了Itr的remove方法，它能够调用ArrayList.this.remove的方法，然后修正游标和expectedModCount等。

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

2）LinkedList中的Iterator

LinkedList的Iterator和ArrayList中的有一些类似的地方。 首先，LinkedList的iterator入口方法其实是AbstractSequentialList抽象类中，

/**
* Returns an iterator over the elements in this list (in proper
* sequence).<p>
*
* This implementation merely returns a list iterator over the list.
*
* @return an iterator over the elements in this list (in proper sequence)
*/
public Iterator<E> 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 <code>next</code> method)
* @return a list iterator over the elements in this list (in proper
*         sequence)
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public abstract ListIterator<E> listIterator(int index);

而这个ListIterator是一个接口，它被LinkedList$ListItr实现，

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned = null;
    private Node<E> 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<E> 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中的复杂一些，它更支持了add等方法； 类似原来游标的遍历方式，基于size、expectedModCount等比较逻辑依然存在，只不过遍历的方式不是原来的下标增进，而是节点之间的next指针来实现。

3）HashMap中的Iterator

HashMap有多个view视图，keySet, values, entrySet，这里分析下entrySet这个视图，另外两个原理和entrySet视图的差不多。

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator();
    }
    public boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<K,V> e = (Map.Entry<K,V>) o;
        Entry<K,V> 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方法中调用了newEntryIterator,将构造EntryIterator实例， EntryIterator源码

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

EntryIterator继承了HashIterator类，复用了父类的大部分方法，只是覆盖了next方法。 HashIterator源码，

private abstract class HashIterator<E> implements Iterator<E> {
    Entry<K,V> next;        // next entry to return
    int expectedModCount;   // For fast-fail
    int index;              // current slot
    Entry<K,V> 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<K,V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Entry<K,V> 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的结构并不是顺序的，在执行Iterator.next方法时不能通过next指针或下标的方式直接找到下一个元素，HashIterator为了能达到这个目的，在构造函数和nextEntry方法中预先做了advance处理。

//构造函数中
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)
        ;
}

构造函数中预先在HashMap的table数组找到第一个头结点不为null的元素； (next = t[index++]) == null的写法有点迷惑性，不考虑HashMap为空的情况，index自增停在next != null的情况，即 next = t[index-1], index已经往前一步了；

在nextEntry中如果发现e.next是null，此时表示table这个数组元素的链表遍历结束了，需要跳到下一个头节点不为空的元素继续遍历，而index刚好往前一步了，此时继续执行

next = t[index++]

假设next[index]不为空，那么下一个遍历的数组元素头节点找到，并且index已经自增了。

并发数据结构的情况

以ConcurrentHashMap为例，看ConcurrentHashMap$HashInteraotr的实现

abstract class HashIterator {
    int nextSegmentIndex;
    int nextTableIndex;
    HashEntry<K,V>[] currentTable;
    HashEntry<K, V> nextEntry;
    HashEntry<K, V> 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<K,V> seg = segmentAt(segments, nextSegmentIndex--);
                if (seg != null && (currentTable = seg.table) != null)
                    nextTableIndex = currentTable.length - 1;
            }
            else
                break;
        }
    }


    final HashEntry<K,V> nextEntry() {
        HashEntry<K,V> 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分段因素所在，在构造函数中指定了最后一个segment数组元素，然后做advance处理，也是从后往前处理的。首先找到不为null的分段segment，然后才是在segment的table数组中找到不为null的元素，这都是从后往前“前进”的。

而与HashMap不同的地方，ConcurrentHashMap的Iterator并不是fast-fail的，它并没有判断modCount;除此之外还应该看到它对nextEntry的处理，在advance的方法调用以下两个方法，

/**
* 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 <K,V> Segment<K,V> segmentAt(Segment<K,V>[] ss, int j) {
    long u = (j << SSHIFT) + SBASE;
    return ss == null ? null :
        (Segment<K,V>) 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 <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {
    return (tab == null) ? null :
        (HashEntry<K,V>) UNSAFE.getObjectVolatile
        (tab, ((long)i << TSHIFT) + TBASE);
}

它们都是调用了UNSAFE.getObjectVolatile方法，利用了volatile access的方式，相较于上锁的方式性能更好。

番外篇

JavaScript实现的Iterator的例子

这个例子来自MDN的文档，做法比较简洁,迭代器

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

可以考虑给这个makeIterator的返回值加上hasNext属性，

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

JavaScript利用了闭包实现了Iterator和Java利用内部类实现有相似的地方。

总结

Iterator的主要目的还是为了表现底层数据结构的所有元素，提供一种统一的遍历方式。在不同的数据结构需要针对不同语义做出改动，像LinkedList的支持add方法，像ConcurrentHashMap和HashMap的advance处理，像ConcurrentHashMap那样不判断modeCount而使用volatile access等。