Detailed explanation of the sample code of iterator in Java collection framework

This article mainly provides you with a brief introduction to the relevant information about the iterator in the Java collection framework. It has certain reference value. Interested friends can refer to

Array data in Java can Obtained through index, what about objects? Also through index? Today we will analyze the method iteration-Iterator for obtaining collection objects in Java collections.

This article mainly analyzes the iterator part in the Java collection framework, Iterator. The source code analysis is based on JDK1.8, analysis tool, AndroidStudio. Please correct me if there are any deficiencies in the article analysis!

1. Introduction

We often use the iteration interface provided by JDK to iterate Java collections.

 Iterator iterator = list.iterator();
      while(iterator.hasNext()){
        String string = iterator.next();
        //do something
      }

The above is the basic template used by iterators. In fact, we can simply understand iteration as traversal, which is a standardized method class for traversing all objects in various containers. It always controls the Iterator and sends it the "forward", "backward", and "get current element" commands to indirectly traverse the entire collection. In Java, Iterator is an interface, which only provides basic rules for iteration:

  public interface Iterator<E> {
  //判断容器内是否还有可供访问的元素
  boolean hasNext();
  //返回迭代器刚越过的元素的引用，返回值是 E
  E next();
  //删除迭代器刚越过的元素
  default void remove() {
    throw new UnsupportedOperationException("remove");
  }
}

The above is the basic declaration of the iterator. We analyze it through specific collections.

2. Collection classification

2.1 Iterator of ArrayList

We can know by analyzing the source code of ArrayList that an internal class is first defined inside ArrayList Itr, the inner class implements the Iterator interface, as follows:

private class Itr implements Iterator<E> {
  //....
}

The inner class implements the Iterator interface, and the Iterator of ArrayList returns its inner class Itr, so we mainly look at How is Itr implemented.

  public Iterator<E> iterator() {
    return new Itr();
  }

Next we analyze the implementation of its internal class Itr.

  private class Itr implements Iterator<E> {

    protected int limit = ArrayList.this.size;

    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 < limit;
    }

    @SuppressWarnings("unchecked")
    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();
    }
  }

First let’s analyze the defined variable:

    protected int limit = ArrayList.this.size;

    int cursor;    // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

Among them, limit is the size of the current ArrayList, cursor represents the index of the next element, and lastRet It is the index of the previous element. If not, it returns -1. expectedModCount is of little use. We will then analyze and see how to determine whether there are subsequent elements during iteration.

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

It’s very simple, it is to determine whether the index of the next element has reached the capacity of the array. If it does, it will be gone. It’s the end!

Next, let’s analyze the method of obtaining the element of the current index 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];
    }

Why do we need to judge modCount in the next method? That is, it is used to determine whether the collection has been modified during the traversal process. modCount is used to record the number of modifications of the ArrayList collection. It is initialized to 0. Whenever the collection is modified (modifications on the structure, internal updates are not counted), such as add, remove and other methods, modCount + 1, so if modCount remains unchanged, It means that the collection content has not been modified. This mechanism is mainly used to implement the fast failure mechanism of the ArrayList collection. Among Java collections, a large part of the collections have fast failure mechanisms. Therefore, to ensure that no errors occur during the traversal process, we should ensure that no structural modifications are made to the collection during the traversal process (except for the remove method, of course). If an abnormal error occurs, we should carefully check whether the program has errors instead of No processing is done after catch. The above code is relatively simple, it just returns the array value at the index.

For the iteration method of ArrayList, it mainly judges the value of the index and compares it with the size of the array to see if there is no data to traverse, and then obtains the values ​​​​in the array in turn. It mainly captures each collection. The underlying implementation can be iterated.

Next we will analyze the Iterator method of HashMap. Other methods are similar, as long as you grasp the underlying implementation.

2.2 HashMap’s Iterator

In HashMap, there is also a class that implements the Iterator interface. It is just an abstract class, HashIterator. Let’s take a look at its implementation. .

 private abstract class HashIterator<E> implements Iterator<E> {
    HashMapEntry<K,V> next;    // next entry to return
    int expectedModCount;  // For fast-fail
    int index;       // current slot
    HashMapEntry<K,V> current;   // current entry

    HashIterator() {
      expectedModCount = modCount;
      if (size > 0) { // advance to first entry
        HashMapEntry[] 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();
      HashMapEntry<K,V> e = next;
      if (e == null)
        throw new NoSuchElementException();

      if ((next = e.next) == null) {
        HashMapEntry[] 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;
    }
  }

Similarly, it also defines a variable

    HashMapEntry<K,V> next;    // next entry to return
    int expectedModCount;  // For fast-fail
    int index;       // current slot
    HashMapEntry<K,V> current;   // current entry

next represents the node of the next entry. expectedModCount is also used to determine the modified status and is used for fast collection Failure mechanism. Index represents the current index, and the node entry represented by current's current index. Let's take a look at how to determine whether there is a value for the next element.

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

It is very simple to determine whether next is null. If it is null, it means there is no data.

Then analyze the method of obtaining elements

    final Entry<K,V> nextEntry() {
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
      HashMapEntry<K,V> e = next;
      if (e == null)
        throw new NoSuchElementException();
      // 一个Entry就是一个单向链表
      // 若该Entry的下一个节点不为空，就将next指向下一个节点;
      // 否则，将next指向下一个链表(也是下一个Entry)的不为null的节点。
      if ((next = e.next) == null) {
        HashMapEntry[] t = table;
        while (index < t.length && (next = t[index++]) == null)
          ;
      }
      current = e;
      return e;
    }

The above is the detailed content of Detailed explanation of the sample code of iterator in Java collection framework. For more information, please follow other related articles on the PHP Chinese website!