Java set [2] - detailed explanation of iterator interface

Qinhuai grocery store 2020-11-08 23:46:32
java set detailed explanation iterator


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

版权声明
本文为[Qinhuai grocery store]所创,转载请带上原文链接,感谢

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云