Java Improvement Chapter (Thirty) -----Iterator
- 黄舟Original
- 2017-02-11 10:14:531159browse
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
}
## Iteration In fact, we can simply understand iteration as traversal, It is a standardized method class for traversing all objects in various containers. It is a very typical design pattern. Iterator pattern is the standard access method for traversing 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
}
This is how ArrayList is handled:
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 Separate from collection classes 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. It 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 mode. Let’s take a look at the Iterator interface in Java to see how it is implemented. 1. java.util.Iterator
Iterator is an interface in Java, it only provides iteration The basic rules are defined in the JDK as follows: an iterator that iterates over the 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 access the collection pointed to by the iterator during iteration. Remove element.
2. The method name has been improved.
The interface is defined as follows:
public interface Iterator {
boolean hasNext();
Object next();
void remove();
}
Among them:
## where:
It is Object and needs to be cast to the type you need
## boolean hasNext(): Determine whether there are still accessible elements in the container
void remove(): Removes the element just passed by the iterator Generally, only two methods, next() and hasNext(), can be used to complete the iteration. As follows:
for(Iterator it = c.iterator(); it.hasNext(); ) {
Object o = it.next();
//do something
}
前面阐述了Iterator有一个很大的优点,就是我们不必知道集合的内部结果,集合的内部结构、状态由Iterator来维持，通过统一的方法hasNext()、next()来判断、获取下一个元素，至于具体的内部实现我们就不用关心了。但是作为一个合格的程序员我们非常有必要来弄清楚Iterator的实现。下面就ArrayList的源码进行分析分析。
二、各个集合的Iterator的实现
下面就ArrayList的Iterator实现来分析，其实如果我们理解了ArrayList、Hashset、TreeSet的数据结构，内部实现，对于他们是如何实现Iterator也会胸有成竹的。因为ArrayList的内部实现采用数组，所以我们只需要记录相应位置的索引即可，其方法的实现比较简单。
2.1、ArrayList的Iterator实现
在ArrayList内部首先是定义一个内部类Itr，该内部类实现Iterator接口，如下：
private class Itr implements Iterator<E> {
//do something
}而ArrayList的iterator()方法实现：
public Iterator<E> iterator() {
return new Itr();
}所以通过使用ArrayList.iterator()方法返回的是Itr()内部类，所以现在我们需要关心的就是Itr()内部类的实现：
在Itr内部定义了三个int型的变量：cursor、lastRet、expectedModCount。其中cursor表示下一个元素的索引位置，lastRet表示上一个元素的索引位置
int cursor; int lastRet = -1; int expectedModCount = modCount;
从cursor、lastRet定义可以看出，lastRet一直比cursor少一所以hasNext()实现方法异常简单，只需要判断cursor和lastRet是否相等即可。
public boolean hasNext() {
return cursor != size;
}对于next()实现其实也是比较简单的，只要返回cursor索引位置处的元素即可，然后修改cursor、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()主要用来判断集合的修改次数是否合法，即用来判断遍历过程中集合是否被修改过。在java提高篇（二一）-----ArrayList中已经阐述了。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();
}
}这里就对ArrayList的Iterator实现讲解到这里，对于Hashset、TreeSet等集合的Iterator实现，各位如果感兴趣可以继续研究，个人认为在研究这些集合的源码之前，有必要对该集合的数据结构有清晰的认识，这样会达到事半功倍的效果！！！！
—————————————————————————————————— ————————————————————