Implementation method of Java collection Iterator iteration

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
}

In fact, we can simply understand iteration as traversal, which is a standardized method class for traversing all objects in various containers. It is a very typical design pattern. The Iterator pattern is the standard access method for iterating over collection classes. It can abstract access logic from different types of collection classes, thereby avoiding exposing the internal structure of the collection to the client. This is what we do when there are no iterators. As follows:

For arrays we use subscripts to process:

int[] arrays = new int[10];
for(int i = 0 ; i < arrays.length ; i++){
int a = arrays[i];
//do something
}

For ArrayList this is how we process it:

List<String> list = new ArrayList<String>();
for(int i = 0 ; i < list.size() ; i++){
String string = list.get(i);
//do something
}

For these two methods, we always know the internal structure of the collection in advance. The access code and the collection itself are tightly coupled, and the access logic cannot be separated from the collection class and client code. At the same time, each collection corresponds to a traversal method, and client code cannot be reused. In practical applications, it is quite troublesome to integrate the above two sets. So in order to solve the above problems, the Iterator mode was born, which always uses the same logic to traverse the collection. This eliminates the need for the client itself to maintain the internal structure of the collection, and all internal states are maintained by Iterator. The client never deals directly with the collection class. It always controls the Iterator and sends it the "forward", "backward", and "get current element" commands to indirectly traverse the entire collection.

The above is just a brief explanation of the Iterator pattern. Next, let’s take a look at the Iterator interface in Java and see how it is implemented.

1. java.util.Iterator

In Java, Iterator is an interface. It only provides basic rules for iteration. In the JDK, it is defined like this : Iterator for iterating over collection. Iterators replace Enumeration in the Java Collections Framework. There are two differences between iterators and enumerations:

1. Iterators allow the caller to use well-defined semantics to remove elements from the collection pointed to by the iterator during iteration.

2. The method name has been improved.

The interface is defined as follows:

public interface Iterator {
　　boolean hasNext();
　　Object next();
　　void remove();
}

Among them:

Object next(): Returns the element just crossed by the iterator Reference, the return value is Object, which needs to be cast to the type you need

boolean hasNext(): Determine whether there are any accessible elements in the container

void remove(): Delete the element just crossed by the iterator

For us, we generally only need to use the next() and hasNext() methods to complete the iteration. As follows:

for(Iterator it = c.iterator(); it.hasNext(); ) {
　　Object o = it.next();
　　 //do something
}

As explained earlier, Iterator has a great advantage, that is, we do not need to know the internal results of the collection. The internal structure and state of the collection are maintained by Iterator, through a unified method hasNext(), next() to determine and obtain the next element. As for the specific internal implementation, we don’t need to care. But as a qualified programmer, it is very necessary for us to figure out the implementation of Iterator. Let's analyze the source code of ArrayList.

2. Implementation of Iterator of each collection

The following is an analysis of the Iterator implementation of ArrayList. In fact, if we understand the data structure of ArrayList, Hashset, and TreeSet, the internal Implementation, they will also have a good idea of ​​how they implement Iterator. Because the internal implementation of ArrayList uses an array, we only need to record the index of the corresponding position, and the implementation of its method is relatively simple.

2.1. Iterator implementation of ArrayList

In ArrayList, first define an internal class Itr, which implements the Iterator interface, as follows:

private class Itr implements Iterator<E> {
//do something
}

And the iterator() method of ArrayList is implemented:

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

So by using the ArrayList.iterator() method, what is returned is the Itr() inner class, so now we What needs to be concerned about is the implementation of the Itr() internal class:

Three int-type variables are defined inside Itr: cursor, lastRet, and expectedModCount. Where cursor represents the index position of the next element, and lastRet represents the index position of the previous element

int cursor;
int lastRet = -1;
int expectedModCount = modCount;

It can be seen from the definitions of cursor and lastRet that lastRet is always one less than cursor, so hasNext() The implementation method is extremely simple, you only need to determine whether cursor and lastRet are equal.

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

The implementation of next() is actually relatively simple. Just return the element at the cursor index position, and then modify the cursor and lastRet

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; //cursor + 1
return (E) elementData[lastRet = i]; //lastRet + 1 且返回cursor处元素
}

checkForComodification() 主要用来判断集合的修改次数是否合法，即用来判断遍历过程中集合是否被修改过。modCount 用于记录 ArrayList 集合的修改次数，初始化为 0，，每当集合被修改一次（结构上面的修改，内部update不算），如 add、remove 等方法，modCount + 1，所以如果 modCount 不变，则表示集合内容没有被修改。该机制主要是用于实现 ArrayList 集合的快速失败机制，在 Java 的集合中，较大一部分集合是存在快速失败机制的，这里就不多说，后面会讲到。所以要保证在遍历过程中不出错误，我们就应该保证在遍历过程中不会对集合产生结构上的修改（当然 remove 方法除外），出现了异常错误，我们就应该认真检查程序是否出错而不是 catch 后不做处理。

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

对于 remove() 方法的是实现，它是调用 ArrayList 本身的 remove() 方法删除 lastRet 位置元素，然后修改 modCount 即可。

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

以上所述是小编给大家介绍的Java集合Iterator迭代的实现方法，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对PHP中文网的支持！

更多Java集合Iterator迭代的实现方法相关文章请关注PHP中文网！