One 、iterator
The interface is introduced
iterator
Interface , It's also a member of the collective family . And others Map
and Collection
The interface is different ,iterator
It is mainly for the convenience of traversing all the elements in the collection , Used to iteratively access elements in a collection , It is equivalent to defining the specification of traversal elements , And the other Map
and Collection
Interface mainly defines the specification of storage elements .
Remember ? As I said before iterable
Interface , One way is to call it iterator()
, Also return iterator
object .
iteration : The way that elements in a collection are constantly accessed , Determine whether there are elements before taking elements , If there is one, take it out , No, it's over , Keep cycling the process , Until all the elements in it are traversed .
The method of interface definition is as follows :
boolean hasNext(); // Is there the next element
E next(); // Get next element
// Remove elements
default void remove() {
throw new UnsupportedOperationException("remove");
}
// Process all the remaining elements ,action The action of processing , How to deal with
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
But here's the thing , The whole set class is not inherited iterator
Interface , But inherited iterable
Interface , adopt iterable
Interface method returns iterator
The object of . It is worth noting that ,iterator
Of remove()
Method , It's in the iteration process Only safe How to modify the set , Why do you say so ?
If you use for Loop index way traversal , After deleting an element , The number of elements in the set has changed , It's easy to make a mistake . for example
for(int i=0;i<collection.size();i++){
if(i==2){
collection.remove(i);
}
}
and iterator
Of remove()
Methods don't go wrong , Because by calling hasNext()
and next()
Method , The pointer control has been well handled .
Two 、 Why iterator Interface
First , We know iterator
Interface is to define the specification of traversal collection , It's also an abstraction , Abstract the way to traverse different sets , When traversing this way , You don't need to know the internal structure of different sets .
Why abstraction is needed ?
Suppose there is no iterator
Interface , We know , You can only traverse through the index , such as
for(int i=0;i<array.size();i++){
T item = array[i];
}
thus , The coupling degree is relatively high , If the data structure used has changed , It's going to be written in a different way , It's not easy to maintain existing code . without iterator
, Then the client needs to maintain the pointer , It's equivalent to delegating authority , Will cause a certain degree of confusion . Abstraction is to extract traversal function , hand iterator
Handle , When the client processes the collection , To more “ major ” The it ,it do it well.
3、 ... and 、iterator Interface related interface
3.1 ListIterator
ListIterator
Inherited from Iterator
Interface , More powerful , Can only be used to access a variety of List
type , Use List
Object of type list
, call listIterator()
Method can get a point to list
At the beginning ListIterator
From the picture interface above , This interface has access to the next element , Determine if there is the next element , Is there a previous element , Determine if there is a previous element , Get the index of the next element , Get the index of the previous element , Remove elements , Modifying elements , Add elements and other functions . And ordinary Iterator
The difference is ,ListIterator
Can be moved forward or backward , That's two-way movement .
boolean hasNext(); // Are there any elements
E next(); // Get next element
boolean hasPrevious(); // Is there a previous element
E previous(); // Get the previous element
int nextIndex(); // Get the next index
int previousIndex(); // Get the last index
void remove(); // remove
void set(E e); // to update
void add(E e); // Additive elements
The test code is as follows :
List<String> list =
new ArrayList<String>(Arrays.asList("Book","Pen","Desk"));
// Point the pointer to the first element
ListIterator<String> lit = list.listIterator(1);
while(lit.hasNext()){
System.out.println(lit.next());
}
System.out.println("===================================");
// Pointer to the last element modification in the last element list ChangeDesk.
lit.set("ChangeDesk");
// Traverse forward
while(lit.hasPrevious()){
System.out.println(lit.previous());
}
Output is as follows :
Pen
Desk
===================================
ChangeDesk
Pen
Book
If you click on it ArrayList
Source code , See and ListIterator
Relevant part , We'll find out that ArrayList
An inner class is implemented at the bottom ListItr
, Inherited Itr
, Realized ListIterator
Interface . This Itr
In fact, it is realized Iterator
, The basic List Iterator function , And this ListItr
The enhanced version is specially designed for List
Implemented iterators . It uses cursor
As the current pointer ( Indexes ), All function functions are implemented by operating this pointer .
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
// Set the current pointer
cursor = index;
}
public boolean hasPrevious() {
// Not the first element indicates that there is a previous element
return cursor != 0;
}
// Get the next element index
public int nextIndex() {
return cursor;
}
// Get the index of the previous element
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
// Check if it has been modified
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
// Return to the previous element
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
We can see , In the above method , There's a lot of validation , such as checkForComodification()
, Check whether it has been modified ,list The modification of elements in may cause the array to be out of bounds .
3.2 SpitIterator
To be exact ,SpitIterator
and Iterator
Doesn't matter , It's just that the two functions are similar .SpitIterator
It mainly defines the class and divides the collection into multiple sets , Convenient for parallel computing .
3.2.1 SpitIterator Source code method analysis
public interface Spliterator<T> {
// Each element is processed sequentially , The parameter is the action of processing , If there are still elements to be processed, return true, Otherwise return to false
boolean tryAdvance(Consumer<? super T> action);
// Process the remaining elements in turn
default void forEachRemaining(Consumer<? super T> action) {
do { } while (tryAdvance(action));
}
// The most important method , It's used to divide the set
Spliterator<T> trySplit();
// Estimate how many more elements need traversal processing
long estimateSize();
// Get the exact elements , If you can't get accurate , It will return the estimated
default long getExactSizeIfKnown() {
return (characteristics() & SIZED) == 0 ? -1L : estimateSize();
}
// It means that we should Spliterator What are the characteristics , It's like an extended function , Better control and optimization Spliterator Use
int characteristics();
// Determine if there are any features
default boolean hasCharacteristics(int characteristics) {
return (characteristics() & characteristics) == characteristics;
}
// If this Spliterator The source of has ordered characteristics , Then this method will return the corresponding comparator . If the sources are sorted in natural order , Then return to // null. otherwise , If the source is not sorted , Throw out IllegalStateException.
default Comparator<? super T> getComparator() {
throw new IllegalStateException();
}
public static final int ORDERED = 0x00000010;
public static final int DISTINCT = 0x00000001;
public static final int SORTED = 0x00000004;
public static final int SIZED = 0x00000040;
public static final int NONNULL = 0x00000100;
public static final int IMMUTABLE = 0x00000400;
public static final int CONCURRENT = 0x00001000;
public static final int SUBSIZED = 0x00004000;
}
Examples of the methods used are as follows :
public static void spliterator(){
List<String> list = Arrays.asList("1", "2", "3","4","5","6","7","8","9","10");
// Get an iterator
Spliterator<String> spliterator = list.spliterator();
// One by one
System.out.println("tryAdvance: ");
spliterator.tryAdvance(item->System.out.print(item+" "));
spliterator.tryAdvance(item->System.out.print(item+" "));
System.out.println("\n-------------------------------------------");
// Go through the rest in turn
System.out.println("forEachRemaining: ");
spliterator.forEachRemaining(item->System.out.print(item+" "));
System.out.println("\n------------------------------------------");
// spliterator1:0~10
Spliterator<String> spliterator1 = list.spliterator();
// spliterator1:6~10 spliterator2:0~5
Spliterator<String> spliterator2 = spliterator1.trySplit();
// spliterator1:8~10 spliterator3:6~7
Spliterator<String> spliterator3 = spliterator1.trySplit();
System.out.println("spliterator1: ");
spliterator1.forEachRemaining(item->System.out.print(item+" "));
System.out.println("\n------------------------------------------");
System.out.println("spliterator2: ");
spliterator2.forEachRemaining(item->System.out.print(item+" "));
System.out.println("\n------------------------------------------");
System.out.println("spliterator3: ");
spliterator3.forEachRemaining(item->System.out.print(item+" "));
}
- tryAdvance() Traversing one element at a time
- forEachRemaining() Traverse in blocks in sequence
- trySplit() Partition to form another Spliterator, Used in parallel operations , It's the first half , It's to keep dividing the front part
give the result as follows :
tryAdvance:
1 2
-------------------------------------------
forEachRemaining:
3 4 5 6 7 8 9 10
------------------------------------------
spliterator1:
8 9 10
------------------------------------------
spliterator2:
1 2 3 4 5
------------------------------------------
spliterator3:
6 7
There are other uses that are not listed here , Mainly trySplit() after , It can be used for multi-threaded traversal . Ideal time , It can be divided into two parts , Good for parallel computing , But not necessarily equally .
3.2.2 SpitIterator What's the use of these characteristic constants ?
spliterator
Its implementation characteristics can be expressed as a set of constants defined in the same interface . That's what we see ORDERED
,DISTINCT
,SORTED
,SIZED
And so on. , This means that every implementation class , Each has its own way of implementation , Different ways of implementation , The implementation features are also different , such as ArrayList
The implementation feature is ORDERED
,SIZED
and SUBSIZED
, We can do this through characteristics()
and hasCharacteristics()
To judge . for example :
public static void main(String[] args) throws Exception{
List<String> list = new ArrayList<>();
Spliterator<String> s = list.spliterator();
System.out.println(s.characteristics());
if(s.hasCharacteristics(Spliterator.ORDERED)){
System.out.println("ORDERED");
}
if(s.hasCharacteristics(Spliterator.DISTINCT)){
System.out.println("DISTINCT");
}
if(s.hasCharacteristics(Spliterator.SORTED)){
System.out.println("SORTED");
}
if(s.hasCharacteristics(Spliterator.SIZED)){
System.out.println("SIZED");
}
if(s.hasCharacteristics(Spliterator.CONCURRENT)){
System.out.println("CONCURRENT");
}
if(s.hasCharacteristics(Spliterator.IMMUTABLE)){
System.out.println("IMMUTABLE");
}
if(s.hasCharacteristics(Spliterator.NONNULL)){
System.out.println("NONNULL");
}
if(s.hasCharacteristics(Spliterator.SUBSIZED)){
System.out.println("SUBSIZED");
}
}
The output is zero
16464
ORDERED
SIZED
SUBSIZED
In the output result 16464 How to connect with others ? In fact, we found that hasCharacteristics()
In the method , The realization is return (characteristics() & characteristics) == characteristics;
, It's not hard to see. , These states are calculated based on and operations . The above results also show that ArrayList
Yes ORDERED
,SIZED
and SUBSIZED
These features .
If it is HashSet
It is characterized by DISTINCT
and SIZED
.
Four 、 iterator Examples of implementations in collections
iterator
It's just an interface , It's equivalent to a norm , In theory, all subclasses or inheritance classes should be implemented in accordance with , But different inheritance classes / Subclasses will have different implementations .
4.1 iterator stay ArrayList The implementation of the
iterator
It's just an interface , A norm , Although there are individual methods with default implementation , But the most important and abundant , It is its implementation and extension in subclasses , Now let's look at ArrayList
In the implementation of .ArrayList
Not directly to achieve iterator
Interface , But through the way of internal classes to operate , The inner class is Itr
,
private class Itr implements Iterator<E> {
// Index of the next element ( The pointer )
int cursor; // index of next element to return
// The last element pointer index
int lastRet = -1; // index of last element returned; -1 if no such
// Number of changes ( Version number )
int expectedModCount = modCount;
Itr() {}
// Is there the next element
public boolean hasNext() {
return cursor != size;
}
// The next element
@SuppressWarnings("unchecked")
public E next() {
// security check
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;
return (E) elementData[lastRet = i];
}
// remove
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();
}
}
// Process the remaining elements in turn
@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;
checkForComodification();
}
// security check , Check if it has been modified
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
You can see it from the source above , A lot about checking for changes , The set tracks changes ( Additions and deletions ) The number of times (modCount Also known as version number ), Each iterator maintains a counter independently , In every operation ( Additions and deletions ), Check that the version number has changed , If you change , Will throw ConcurrentModificationException() abnormal , It's a security mechanism .
security check , The fast failure mechanism implements the main and variable modCount
,expectedModCount
, And one. checkForComodification()
The method is about , That is to say expectedModCount
Is the number of times the inner class has been modified , Literally, it refers to the number of revisions expected in theory ,modCount
Is the number of times an external class has been modified , At the time of creation , Will modCount
Assign a value to expectedModCount
, The two are consistent , If in the process of iteration , Of an external class modCount
Not right expectedModCount
,n Then it will throw ConcurrentModificationException
abnormal .
4.2 iterator stay HashMap The implementation of the
First ,HashMap
It defines one HashIterator
, Why do you do this ? because HashMap
The particularity of storage structure , There are Entry<key,value>, So there are three kinds of traversal , One is Key, One is Value, The other is Entry, These three iterations are similar , So here's the abstract principle , Defined a Hash iterator .
abstract class HashIterator {
// Next node
Node<K,V> next;
// Current node
Node<K,V> current; // current entry
// Expected number of revisions
int expectedModCount; // for fast-fail
// Indexes
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) {
// Point to the first non empty element
do {} while (index < t.length && (next = t[index++]) == null);
}
}
// Whether there is a next node
public final boolean hasNext() {
return next != null;
}
// Get the next node
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
// remove
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
And then we define KeyIterator
,ValueIterator
,EntryIterator
, Inherited from HashIterator
,
// Traverse key
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
// Traverse value
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
// Traverse entry
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
5、 ... and 、 summary
All of the above , About Iterator
, It's actually an iterator , It can be simply understood as traversal using , The main function is to point to a node , Move forward or backward , If the data structure is complex, multiple iterators are needed , such as HashMap
, The interaction between multiple iterators can be avoided . Every iterator has
expectedModCount and modCount, It is to verify whether it has been modified during the iteration , If it changes , An exception will be thrown .
This article is for myself only ( Ben rookie ) Learn to accumulate records , Or learning notes , If there is any infringement , Please contact the author for deletion . No one is perfect , The same is true of articles , The style of writing is immature , I can't help it , Don't spray , If there are mistakes , I would also like to point out that , Be deeply grateful ~
The road to technology is not in the moment , one's nobility lasts forever , Even slowly , Go on and on .
official account : Qin Huai grocery store