⛳ Java集合框架

🎨 一、概述

早在Java 2之前，Java 就提供了特设类。比如：Dictionary、Vector、Stack和Properties这些类用来存储和操作对象组。

虽然这些类都非常有用，但是它们缺少一个核心的，统一的主题。由于这个原因，使用 Vector 类的方式和使用 Properties 类的方式有着很大不同。

集合框架被设计成要满足以下几个目标。

• 该框架必须是高性能的。基本集合（动态数组，链表，树，哈希表）的实现也必须是高效的。
• 该框架允许不同类型的集合，以类似的方式工作，具有高度的互操作性。
• 对一个集合的扩展和适应必须是简单的。

为此，整个集合框架就围绕一组标准接口而设计。你可以直接使用这些接口的标准实现，诸如： LinkedList, HashSet, 和 TreeSet 等,除此之外你也可以通过这些接口实现自己的集合。

简化图：

注：带有Produces没有implements（实现）的关系。

Java 集合类是特别有用的工具类，可用于存储数量不等的对象，并且可以实现常用的数据结构，栈，队列等。Java集合大致分为Set、List、Map和Queue四种体系，其中Set代表无序，不可重复的集合，而List正好相反，List代表有序，可重复的大的集合；Map则代表具有映射关系的集合；Java 5 又增加了Queue体系集合，代表一种队列集合的实现。

🏭 二、Iterator接口

Iterator接口表示对集合进行迭代的迭代器。Iterator接口为集合而生，专门实现接口的集合。

凡是由Collection接口派生来的接口或类，都实现了iterator()方法，iterator()方法返回一个Iterator对象。

Map接口的实现方式是通过EntrySet内部类实现的。

💭 2.1、基础用法

1. 使用集合的iterator()方法返回Iterator对象。
2. while循环遍历。
3. 使用Iterator的hasNext()方法判断是否存在下一个可访问的元素。
4. 使用Iterator的next()方法返回要访问的下一个元素。

import java.util.ArrayList;

import java.util.Iterator;

public class ArrayListTest {

        public static void main(String[] args) {

                 ArrayList testList = new ArrayList();
                  testList.add("String1");
                 testList.add("String2");
                 testList.add("String3");
            	// 获取迭代器
                 Iterator it = testList.iterator();
                 while(it.hasNext()) {  // 判断是否有下一个元素 (刚开始指向头结点)
                          String str = (String)it.next();  // 返回下一个元素
                          System.out.println(str);
                 }
        }
}

🚜 2.2、原理

JDK 中专门提供了一个遍历集合的接口java.util.Iterator。Iterator接口也是Java集合中的一员，但它与Collection、Map接口有所不同，Collection接口与Map接口主要用于存储元素，而Iterator主要用于迭代访问（即遍历）Collection中的元素

因此Iterator对象也被称为迭代器，使你能够通过循环来得到或删除集合的元素。ListIterator 继承了Iterator，以允许双向遍历列表和修改元素。

• 方法：

  1. hasNext() ：该方法会判断集合对象是否还有下一个元素，如果已经是最后一个元素则返回false。如果仍有元素可以迭代，则返回 true。
  2. next()：把迭代器的指向移到下一个位置，同时，该方法返回迭代的下一个元素。
  3. remove() 从迭代器指向的集合中移除迭代器返回的最后一个元素。
  4. default void forEachRemaining(Consumer<? super E> action)：对剩下的所有元素进行处理，action则为处理的动作，意为要怎么处理

  boolean hasNext(); // 是否有下一个元素
  
  E next();   // 获取下一个元素
  
  // 移除元素
  default void remove() {
          throw new UnsupportedOperationException("remove");
      }
      
  // 对剩下的所有元素进行处理，action则为处理的动作，意为要怎么处理
  default void forEachRemaining(Consumer<? super E> action) {
          Objects.requireNonNull(action);
          while (hasNext())
              action.accept(next());
      }
  

测试：DemoIterator

package org.example.f_interator;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

/*
    java.util.Iterator接口:迭代器(对集合进行遍历)
    有两个常用的方法
        boolean hasNext() 如果仍有元素可以迭代，则返回 true。
                          判断集合中还有没有下一个元素,有就返回true,没有就返回false
        E next() 返回迭代的下一个元素。
                  取出集合中的下一个元素
    Iterator是一个接口,我们无法直接使用,需要使用Iterator接口的实现类对象,获取实现类的方式比较特殊
    Collection接口中有一个方法,叫iterator(),这个方法返回的就是迭代器的实现类对象
              Iterator<E> iterator() 返回在此 collection 的元素上进行迭代的迭代器。

    迭代器的使用步骤(重点):
        1.使用集合中的方法iterator()获取迭代器的实现类对象,使用Iterator接口接收(多态)
        2.使用Iterator接口中的方法hasNext判断还有没有下一个元素
        3.使用Iterator接口中的方法next取出集合中的下一个元素
 */
public class DemoIterator {
    public static void main(String[] args) {
        //创建一个集合对象
        Collection<String> coll = new ArrayList<>();
        //往集合中添加元素
        coll.add("姚明");
        coll.add("科比");
        coll.add("麦迪");
        coll.add("詹姆斯");
        coll.add("艾弗森");

        /*
            1.使用集合中的方法iterator()获取迭代器的实现类对象,使用Iterator接口接收(多态)
            注意:
                Iterator<E>接口也是有泛型的,迭代器的泛型跟着集合走,集合是什么泛型,迭代器就是什么泛型
         */
        //多态  接口            实现类对象
        Iterator<String> iterator = coll.iterator();


        /*
            发现使用迭代器取出集合中元素的代码,是一个重复的过程
            所以我们可以使用循环优化
            不知道集合中有多少元素,使用while循环
            循环结束的条件,hasNext方法返回false
         */
        while (iterator.hasNext()) {
            String e = iterator.next();
            System.out.print(e + " ");//姚明 科比 麦迪 詹姆斯 艾弗森
        }

        System.out.println("\n======================");

        for (Iterator<String> it2 = coll.iterator(); it2.hasNext(); ) {
            String e = it2.next();
            System.out.print(e + " ");//姚明 科比 麦迪 詹姆斯 艾弗森
        }

    }
}

• 在获取迭代器的时候，会创建一个原集合的副本。同时会创建一个指针指向迭代器迭代集合的起始位置。
• Collection集合元素的通用获取方式。在取元素之前先要判断集合中有没有元素，如果有，就把这个元素取出来，继续再判断，如果还有就再取出出来。一直把集合中的所有元素全部取出。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vqh9oK7Z-1691910477171)(C:\Users\gu653\AppData\Roaming\Typora\typora-user-images\image-20230809191910673.png)]

🐾 2.3、为什么需要iterator接口

iterator接口是为了定义遍历集合的规范，也是一种抽象，把在不同集合的遍历方式抽象出来，这样遍历的时候，就不需要知道不同集合的内部结构。

为什么需要抽象？

假设没有iterator接口,我们知道，遍历的时候只能通过索引，比如

for(int i=0;i<array.size();i++){
    T item = array[i];
}

这样一来，耦合程度比较高，如果使用的数据结构变了，就要换一种写法，不利于维护已有的代码。如果没有iterator,那么客户端需要维护指针，相当于下放了权限，会造成一定程度的混乱。抽象则是把遍历功能抽取出来，交给iterator处理，客户端处理集合的时候，交给更“专业”的它，it do it well.

值得注意的是，集合类的整体不是继承了iterator接口，而是继承了iterable接口，通过iterable接口的方法返回iterator的对象。值得注意的是，iterator的remove()方法，是迭代过程中唯一安全的修改集合的方法，为何这样说？

如果使用for循环索引的方式遍历，删除掉一个元素之后，集合的元素个数已经变化，很容易出错。例如

for(int i=0;i<collection.size();i++){
    if(i==2){
        collection.remove(i);
    }
}

而iterator的remove()方法则不会出错，因为通过调用hasNext()和next()方法，对指针控制已经处理得比较完善。

☁ 2.4、ListIterator接口

ListIterator继承于Iterator接口，功能更强大，只能用于访问各种List类型，使用List类型的对象list，调用listIterator()方法可以获取到一个指向list开头的ListIterator。

从上面图片接口看，这个接口具有访问下一个元素，判断是否有下一个元素，是否有前面一个元素，判断是否有前一个元素，获取下一个元素的索引，获取上一个元素的索引，移除元素，修改元素，增加元素等功能。和普通的Iterator不一样的是,ListIterator的访问指针可以向前或者向后移动，也就是双向移动。

boolean hasNext();  //是否还有元素 

E next();   //获取下一个元素

boolean hasPrevious();  //是否有上一个元素

E previous();   // 获取上一个元素

int nextIndex();    //获取下一个索引

int previousIndex();    //获取上一个索引

void remove();  //移除

void set(E e); //更新

void add(E e); //添加元素

测试：

List<String> list =
    new ArrayList<String>(Arrays.asList("Book","Pen","Desk"));
// 把指针指向第一个元素
ListIterator<String> lit = list.listIterator(1);
while(lit.hasNext()){
    System.out.println(lit.next());
}
System.out.println("===================================");
//指针指向最后一个元素列表中的最后一个元素修改ChangeDesk。
lit.set("ChangeDesk");
// 往前面遍历
while(lit.hasPrevious()){
    System.out.println(lit.previous());
}

结果：

Pen
Desk
===================================
ChangeDesk
Pen
Book

如果点开ArrayList的源码，看到与ListIterator相关的部分，我们会发现其实ArrayList在底层实现了一个内部类ListItr，继承了Itr,实现了ListIterator接口。这个Itr其实就是实现了Iterator,实现了基本的List迭代器功能，而这个ListItr则是增强版的专门为List实现的迭代器。里面使用cursor作为当前的指针（索引），所有函数功能都是操作这个指针实现。

private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            // 设置当前指针 
            cursor = index;
        }

        public boolean hasPrevious() {
            // 不是第一个元素就表明有前一个元素
            return cursor != 0;
        }
        // 获取下一个元素索引
        public int nextIndex() {
            return cursor;
        }

        // 获取前面一个元素索引
        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            //检查是否被修改
            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 (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();
            }
        }
    }

在上面方法中，有很多校验，比如checkForComodification()，意为检查是否被修改，list中的元素修改有可能导致数组越界。

📢 2.5、iterator在集合中的实现例子

iterator只是一个接口，相当于一个规范，所有的子类或者继承类实现的时候理论上应该遵守，但是不一样的继承类/子类会有不一样的实现。

2.5.1、Iterator在ArrayList的实现

iterator只是一个接口，一个规范，虽然里面有个别方法有默认实现，但是最重要也最丰富的的，是它在子类中的实现与拓展，现在来看在ArrayList 中的实现。ArrayList并没有直接去实现iterator接口，而是通过内部类的方式来操作，内部类为Itr,

private class Itr implements Iterator<E> {
    // 下一个元素的索引（指针）
    int cursor;       // index of next element to return
    // 最后一个元素指针索引
    int lastRet = -1; // index of last element returned; -1 if no such
    // 修改次数（版本号）
    int expectedModCount = modCount;

    Itr() {}
    // 是否有下一个元素
    public boolean hasNext() {
        return cursor != size;
    }

    // 下一个元素
    @SuppressWarnings("unchecked")
    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;
        return (E) elementData[lastRet = i];
    }

    // 移除
    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();
        }
    }

    // 依次处理剩下的元素
    @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 ==