Iterator 這些點你GET到了嗎?

語言: CN / TW / HK

前言

Java 集合框架

Iterator 是 Java 資料結構框架的起始,它是一個頂級介面,夢開始的地方。

讓這個迭代器作為頂級介面可能是出於功能的考慮,不管怎樣的資料結構,都需要遍歷不是。那麼就需要提供一種可以用來遍歷的方式,讓開發者使用也讓 JVM 認識。

一、前世今生

JDK 1.0 的 Enumeration,因名字太長和方法數量有點少不太好擴充套件被廢棄。

JDK 1.2 推出 Iterator 替代。

Iterator JDK 1.8
public interface Iterator<E> {
// 是否包含下一元素
boolean hasNext();
// 下一元素
E next();
// 移除元素
default void remove() {
throw new UnsupportedOperationException("remove");
}
// 遍歷剩餘元素,遊標之後的
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}


用來遍歷元素,且遍歷的過程中可以刪除。
  • hasNext() 是否含有下一個元素;

  • next() 獲取下一元素;

  • remove() 移除某元素;

  • forEachRemaining() 遍歷當前迭代器尚未遍歷的元素。

二、一致性

遍歷過程中可以修改原資料的稱為弱一致性,不可修改的為強一致性。下面舉兩個例子:

1. 強一致性

資料修改過程中會記錄操作次數 modCount ,遍歷過程發現該值與期望的不一致,會丟擲 ConcurrentModificationException 異常。

常見的有 HashMap、ArrayList

HashMap.HashIterator # nextNode
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount) // 就是這裡
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
ArrayList.Itr # next()
public E next() {
if (modCount != expectedModCount) // 此處表現
throw new ConcurrentModificationException();
int i = cursor;
if (i >= limit)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}

這種強一致性的迭代器官稱為 fail-fast 迭代器。

2. 弱一致性

弱一致性相當於建立時做一個數據的拷貝,因為操作的不是原資料,所以不會出現問題也沒用拋異常。

但是弱一致性帶來一些問題:

  • 空間浪費,因為是複製嘛;

  • 資料不一致,如果遍歷過程中原資料進行了修改,操作的結果可能與想要的發生差異。

弱一致性的有 CopyOnWriteArrayList、ConcurrentHashMap。

CopyOnWriteArrayList.COWIterator # next()

public E next ( ) {

    if (! hasNext())
throw new NoSuchElementException();
// snapshot 是建立時用當時資料賦值的,相當於拷貝副本
return (E) snapshot[cursor++];
}

三、迭代器種類

1. 線性迭代器

  • 持有一個遊標 cursor 用來記錄當前遍歷到的位置;

  • 可以正序、倒序遍歷;

  • 可以查詢前後元素;

  • 可以呼叫 add() set() 新增和修改資料,兩者都是往當前迭代器遍歷下標處新增和修改。

比如 ArrayList 的 Itr 就是一種線性迭代器。

private class Itr implements Iterator<E> {
// Android 新增 limit 引數,也就是當前資料長度作為臨界值
protected int limit = ArrayList.this.size;


int cursor; // 遊標
int lastRet = -1; // 最後一個返回的元素,預設 -1
int expectedModCount = modCount;


public boolean hasNext() {
return cursor < limit;
}


// 下一元素
public E next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
int i = cursor;
if (i >= limit)
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();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();


try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
limit--;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
// 遍歷剩餘元素
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;


if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
}

2. 鏈式迭代器 HashIterator

  • 持有一個遍歷結點、當前遍歷下標;

HashMap 的迭代器就是一種實現 HashIterator。

abstract class HashIterator {    Node<K,V> next;        // 下一個要返回的結點
Node<K,V> current; // 當前結點
int expectedModCount; // for fast-fail 強一致性
int index; // current slot 當前下標


HashIterator() {
expectedModCount = modCount; // 建立時賦值
Node<K,V>[] t = table; // table 是 HashMap 的資料
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}


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


final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
// 遍歷查詢,直到下面結點為 null 或 表為空
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}


public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}


final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}


final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}


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


四、總結和其它

Iterable 介面

如果想讓某個 Object 可以使用 "for-each loop" 也就是增強 for 迴圈,需要實現 Iterable 介面。

public interface Iterable<T> {    /**
* Returns an iterator over elements of type {@code T}.
* @return an Iterator.
*/
Iterator<T> iterator();
}

也就是說,想要使用增強 for 迴圈,必須實現該介面並提供迭代器。如果使用沒有實現該介面的類進行迴圈,編譯器會報錯。

例項

List<Integer> list = new ArrayList<>();list.add(1);


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

ArrayList 最終繼承了 Iterable 所以可以遍歷,那麼這個增強 for 迴圈反編譯之後:

Integer i;for(Iterator iterator = list.iterator(); iterator.hasNext(); System.out.println(i)){
i = (Integer)iterator.next();
}

可以看到其實是使用迭代器進行遍歷的操作,不斷給變數 i 賦值並列印。

注意

因為 Java 有 fail-fast 機制,使用增強 for 迴圈時要考慮所遍歷物件的一致性。使用某些強一致性的結構如 ArrayList,如果要操作資料應使用迭代器:

List<Student> students = new ArrayList<>();
...
Iterator<Student> stuIter = students.iterator();
while (stuIter.hasNext()) {
Student student = stuIter.next();
if (student.getId() == 2) {
// 這裡要使用Iterator的remove方法移除當前物件
// 如果使用List的remove方法,則會出現ConcurrentModificationException
stuIter.remove();
}
}

總結

  • 實現 Iterable 以提供迭代器,實現迴圈功能;

  • 迭代器可以用來遍歷、指定位置插入、移除資料;

  • 使用可迭代資料結構,要注意其一致性;

  • 無論是線性還是鏈式迭代器,主要是依靠內部維護的遊標(下標)來標記當前遍歷位置。

作者:Marker_Sky

連結:https://www.jianshu.com/p/eb9949b454c1

關注我獲取更多知識或者投稿