Java source code analysis: in-depth discussion of Iterator mode

Java source code analysis: in-depth discussion of Iterator mode

Author: Liao Xuefeng

About the Author

Liao Xuefeng, software engineer, is now engaged in J2EE development, you can contact him through askLXF@163.com.

text

A series of important set classes are included in the Java.util package. This article will start from the analysis source code, and in depth, the internal structure of a collection class, and the source code that traverses the collection iterative mode implementation inside.

Let's first discuss a root-interface Collection and then analyze an abstract class AbstractList and its corresponding Iterator interface, and carefully study the realization of the iterative score.

The source code version discussed herein is JDK 1.4.2, because JDK 1.5 uses a lot of generic code in Java.util, in order to simplify the problem, so we still discuss the code of the 1.4 version.

Collection class root interface Collection

The Collection interface is the root type of all collection classes. Its main interface method is:

Boolean Add (Object C)

The Add () method will add a new element. Note that this method returns a boolean, but the return value is not indicating that the success is or not. Read DOC carefully, Collection stipulates: If a collection refuses to add this element, no matter what reason, you must throw an exception. The meaning of this return value is that after the add () method is executed, the collection content changes (that is, there is no number of elements, the location, etc.), which is implemented by the specific class. That is: If the method is wrong, the abnormality will always be thrown; the return value only indicates that this Collection content is changed after the method is executed.

Similar to:

Boolean Add (Collection C);

Boolean Remove (Object O);

Boolean Removeall (Collection C);

Boolean Remainall (Collection C);

Object [] toArray () method is simple, convert the collection into an array returns. Object [] toarray (object [] a) method is a bit more complex, first, return Object [] is still an array that turns all elements of the collection, but the type and parameter A type is the same, such as execution:

String [] o = (String []) C.Toarray (New String [0]);

The actual type obtained is String [].

Secondly, if the parameter A is largely installed, the return will be a new array. If the size of the parameter A can install all elements of the collection, the return is still A, but the contents of A are filled with a collection element. It is especially noted that if the size of A is more than the number of set elements, the portion behind the A is set to NULL.

The last most important method is Iterator (), returns an Iterator, used to traverse all elements of the collection.

Implement traversal collection with Iterator mode

The Iterator mode is a standard access method for traversing a collection class. It can abstract access logic from different types of set classes to avoid exposing the internal structure of the collection to the client.

For example, if you don't use iTerator, the method of traversing an array is to use an index:

For (int i = 0; i

And visit a linked list (LinkedList) must also use the While loop:

While ((E = E.next ())! = null) {... E.Data () ...} The above two method clients must know the internal structure of the collection in advance, the access code and the collection itself are tight Coupling, the access logic cannot be separated from the set class and client code, each collection corresponds to a traversal method, and the client code cannot be reused.

More terror is that if you need to replace ArrayList to LinkedList, the original client code must be overwritten.

To solve the above problems, the Iterator mode always uses the same logic to traverse the collection:

Iterator it = c.iterage (); it.hasnext ();) {...}

The mystery is that the client itself does not maintain the "pointer" of the traversal collection, all internal states (such as the current element location, whether the next element) is maintained by Iterator, and this Iterator is generated by the set class by the factory method, so it Know how to traverse the entire collection.

The client is derived from not directly and the collection class. It always controls the command to send "forward", "back", "rear", "Take the current element" command, can be traversed throughout the collection.

First look at the definition of the Java.util.Iiterator interface:

Public interface itrator {

Boolean hasnext ();

Object next ();

Void remove ();

}

Depending on the first two methods can complete traversal, typical code is as follows:

Iterator it = c.iterator (); it.hasnext ();) {

Object o = it.next ();

// Operation to O ...

}

In JDK1.5, it also simplifies the above code in grammar:

// Type is a specific type, such as String.

For (TYPE T: C) {

// Take the operation of t ...

}

Each set class returns the specific type of Iteerator, Array may return ArrayItemrator, and set may return setiterator, Tree may return TreeITerator, but they all implement the Iterator interface, so the client does not care which Iterator, it only You need to get this Iterator interface, which is the object-oriented power.

Iterator source code analysis

Let's take a look at how AbstractRacyList creates iterator. First of all, AbstractList defines an internal class (Inner Class):

PRIVATE CLASS ITR IMPLEMENTS ITERATOR {

...

}

The definition of the Iterator () method is:

Public iterator itrator () {

Return new itr ();

}

Therefore, the client does not know that it passes the true type of Iterator ITERATOR.

Now we care about how this is the application of the ITR class that implements traverses AbstractList:

PRIVATE CLASS ITR IMPLEMENTS ITERATOR {

INT CURSOR = 0;

INT LastRet = -1;

INT EXPECTEDMODCOUNT = MODCOUNT;

}

The ITR class relysses three int variables (there is also a reference for implied AbstractList) to achieve traversal, and the CURSOR is the next time Next () call time element, the first call next () will return an index of 0. Lastret records the last cursor, so it is always less than Cursor. Variables Cursor and the collection of elements of the collections determine HASNext ():

Public Boolean Hasnext () {

RETURN CURSOR! = size ();

}

Method NEXT () Returns the element of the index as Cursor, then modify the value of Cursor and Lastret:

Public Object next () {

CheckForComodification ();

Try {

Object next = GET (CURSOR);

Lastret = CURSOR ;

Return NEXT;

} catch (indexoutofboundsexception e) {

CheckForComodification ();

Throw new nosuchelementexception ();

}

}

ExpectedModCount represents the expected modcount value to determine whether the collection is modified during the traversal process. AbstractList contains a Modcount variable, which is 0, and modcount plus 1 when the collections are modified once (call add, remove, etc.). Therefore, if MODCOUNT is not changed, the collection content is not modified.

ITR initialization When using an ExpectedModCount to record a collection of modcount variables, after which it is necessary, it will detect the value of Modcount:

Final void CheckforComodification () {

IF (MODCOUNT! = EXPECTEDMODCOUNT)

Throw new concurrentmodificationException ();

}

If the value of MODCOUNT is not recorded in the expectedmodecount, the set content is modified, and the ConcurrentModificationException will be thrown.

This ConcurrentModificationException is RuntimeException, do not capture it on the client. If this exception occurs, there is a problem with the writing of program code, and you should check the code carefully instead of ignore it in catch.

However, the Remove () method called Iterator's own deletes the current element is completely no problem, because in this method, the value of ExpectedModcount and Modcount is automatically synchronized in this method:

Public void remove () {

...

AbstractList.this.remove (Lastret);

...

// Reset the expectedmodcount after calling a collection of Remove () methods:

Expectedmodcount = Modcount;

...

}

To ensure that the traversal process is successfully completed, it is necessary to ensure that the contents of the collection are not changed during the traversal process (except for the Iterator's Remove () method), so that it is ensured that the principle of trailing is only in one thread, or in multi-threaded Traverse code is synchronized.

Finally, give a complete example:

Collection c = new arraylist ();

C.ADD ("abc");

C.ADD ("XYZ");

ITERATOR IT = C.ITerator (); it.hasnext ();) {string s = (string) it.next ();

System.out.println (s);

}

If you replace the ArrayList of the first line of code to LinkedList or Vector, the remaining code can be compiled without changing the line, and the function is unchanged, which is the principle of abstract programming: The dependence is the least dependence on the specific class.