Iteration is no stranger to us in Java. We often use the iterative interface provided by the JDK to iterate over Java collections.
Iterator iterator = list.iterator();
while(iterator.hasNext()){
String string = iterator.next();
//do something
}
Copy the codeIn fact, iteration can be simply understood as traversal. It is a method class that standardizes traversal of all objects in various containers. It is a very typical design pattern. The Iterator pattern is the standard access method for iterating through collection classes. It abstracts the access logic from the different types of collection classes, thus avoiding exposing the internal structure of the collection to the client. This is what we do when we don’t have iterators. As follows:
We use subscripts for arrays:
int[] arrays = new int[10];
for(int i = 0 ; i < arrays.length ; i++){
int a = arrays[i];
//do something
}
Copy the codeArrayList is handled like this:
List<String> list = new ArrayList<String>();
for(int i = 0 ; i < list.size() ; i++){
String string = list.get(i);
//do something
}
Copy the codeWith both approaches, we always know the internal structure of the collection in advance, and the access code and the collection itself are tightly coupled, making it impossible to separate the access logic from the collection class and the client code. At the same time, each collection corresponds to a traversal method, and the client code cannot be reused. How the above two collections need to be integrated in practice is quite cumbersome. So to solve these problems, the Iterator pattern was born, which always iterates over collections using the same logic. The client itself does not need to maintain the internal structure of the collection; all internal state is maintained by Iterator. The client never deals directly with the collection class. It always controls the Iterator, sending it “forward”, “backward”, “fetch the current element” commands to iterate through the collection indirectly.
This is just a brief description of the Iterator pattern. Let’s take a look at the Java Iterator interface and see how it is implemented.
A, Java. Util. Iterator
In Java, Iterator is an interface that provides only the basic rules for iterating. In the JDK, it is defined as an Iterator that iterates over a collection. Iterators replace Enumeration in the Java Collections Framework. Iterators differ from enumerations in two ways:
-
Iterators allow the caller to use well-defined semantics to remove elements from the collection to which the iterator points during iteration.
-
Method names have been improved.
Its interface is defined as follows:
public interface Iterator {boolean hasNext(a);Object next(a);void remove(a);
}
Copy the codeAmong them:
Object Next () : Returns a reference to the element that the iterator just passed. The return value is Object, which needs to be cast to its desired type
Boolean hasNext() : Checks whether there are any more accessible elements in the container
Void remove() : Removes the element that the iterator just passed
For us, we generally just 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
}
Copy the codeIterator has a great advantage, is that we do not need to know the internal result of the set, the internal structure of the set, the state is maintained by Iterator, through the unified method hasNext(), next() to judge, get the next element, as for the specific internal implementation we do not care about. But as a qualified programmer it is important to understand the implementation of Iterator. ArrayList’s source code is analyzed below.
Implementation of each set of iterators
If we understand the data structure and internal implementation of ArrayList, Hashset, and TreeSet, we should have a good idea of how they implement Iterator. Because the internal implementation of ArrayList uses arrays, we only need to record the index of the corresponding position. The implementation of the method is relatively simple.
2.1. Implementation of ArrayList Iterator
Inside an ArrayList we define an inner class, Itr, that implements the Iterator interface, as follows:
private class Itr implements Iterator<E> {
//do something
}
Copy the codeThe ArrayList iterator() method implements:
public Iterator<E> iterator(a) {
return new Itr();
}
Copy the codeSo using arrayList.iterator () returns the Itr() inner class, so now we need to worry about the implementation of the Itr() inner class:
Three variables of type INT 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;
Copy the codeLastRet is equal to lastRet. LastRet is equal to lastRet. LastRet is equal to lastRet. LastRet is equal to lastRet.
public boolean hasNext(a) {
returncursor ! = size; }Copy the codeThe next() implementation is also relatively simple, just return the element at the cursor index position, and then modify the cursor and lastRet.
public E next(a) {
checkForComodification();
int i = cursor; // Record the index position
if (i >= size) // If the element is greater than the number of elements in the collection, an exception is thrown
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 and return the cursor element
}
Copy the codeCheckForComodification () is mainly used to judge whether the number of modifications of the set is legitimate, that is, whether the set has been modified during traversal. ModCount is used to count the number of changes to the ArrayList collection, initialized to 0, and every time the collection is modified (such as adding, removing, etc.), modCount + 1, so if modCount does not change, It indicates that the collection content has not been modified. This mechanism is mainly used to implement a fast failure mechanism for ArrayList collections. In Java collections, a large number of collections have a fast failure mechanism, which is not covered here, but will be covered later. Therefore, in order to ensure no errors during traversal, we should ensure that there will be no structural changes to the collection during traversal (except for the remove method of course). If an exception error occurs, we should carefully check whether the program is wrong, rather than leaving it unprocessed after catching.
final void checkForComodification(a) {
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
}
Copy the codeThe remove() method is implemented by calling the remove() method of ArrayList itself to remove the lastRet position element and then modifying modCount.
public void remove(a) {
if (lastRet < 0)throw new IllegalStateException();
checkForComodification();
</span><span style="color: #0000ff">try</span><span style="color: #000000"> {
ArrayList.</span><span style="color: #0000ff">this</span><span style="color: #000000">.remove(lastRet);
cursor </span>=<span style="color: #000000"> lastRet;
lastRet </span>= -1<span style="color: #000000">;
expectedModCount </span>=<span style="color: #000000"> modCount;
} </span><span style="color: #0000ff">catch</span><span style="color: #000000"> (IndexOutOfBoundsException ex) {
</span><span style="color: #0000ff">throw</span> <span style="color: #0000ff">new</span><span style="color: #000000"> ConcurrentModificationException();
}
}</span></pre>
Copy the codeIf you are interested in the Iterator implementation of Hashset, TreeSet, etc., you can continue to study it. I think it is necessary to have a clear understanding of the data structure of the collection before studying the source code of these sets. This will achieve twice the result with half the effort ！！！！