1. 集合体系概述

1.1 集合与数组

集合和数组都是容器

• 关于存储元素的个数：

  数组定义后类型确定，长度固定

  集合类型可以不固定，大小是可变的

• 关于存储元素的类型：

  数组可以存储基本类型和引用类型的数据

  集合只能存引用数据类型的数据

• 关于适合的场景：

  数组适合做数据个数和类型确定的场景

  集合适合做数据个数不确定，且要做增删元素的场景

1.2 集合类的体系结构

集合类分为两种体系：Collection 和 Map。Collection 单列集合，每个元素（数据）只包含一个值；Map 双列集合，每个元素包含两个值（键值对）。

1.3 Collection 集合的体系

上图中只是列出了几个常用的类型。

Collection 集合分为两类常用的集合体系：

• List 系列集合：添加的元素有序、可重复、有索引
  • ArrayList、LinekdList ：有序、可重复、有索引
• Set 系列集合：添加的元素是无序、不重复、无索引
  • HashSet: 无序、不重复、无索引；LinkedHashSet: 有序、不重复、无索引
  • TreeSet：**按照大小默认升序排序、**不重复、无索引

1.4 集合对泛型的支持

集合体系的全部接口和实现类都是支持泛型的使用的，可以在编译阶段约束集合只能操作某种数据类型。（把运行时期的问题提前到了编译期间，避免了强制类型转换可能出现的异常）

Collection<String> lists = new ArrayList<String>();
Collection<String> lists = new ArrayList<>(); // JDK 1.7开始后面的泛型类型申明可以省略不写

⚠️ 注意：集合和泛型都只能支持引用数据类型，不支持基本数据类型，所以集合中存储的元素都认为是对象

泛型的原理：

把出现泛型变量的地方全部替换成传输的真实数据类型。

泛型的定义位置：

• 类后面 --- > 泛型类
• 方法申明上 --- > 泛型方法
• 接口后面 --- > 泛型接口

1.4.1 自定义泛型类

泛型类的格式：修饰符 class 类名<泛型变量>{ }，此处泛型变量 T 可以随便写为任意标识，常见的如 E、T、K、V 等

作用：编译阶段约定操作的数据的类型，类似于集合的作用。

示例代码：

public class MyArrayList<E> {
    private ArrayList lists = new ArrayList();

    public void add(E e){  // 不是泛型方法。只是使用类定义的这个泛型 E，而不是他自己定义了泛型
        lists.add(e);
    }

    public void remove(E e){
        lists.remove(e);
    }

    @Override
    public String toString() {
        return lists.toString();
    }
}

1.4.2 自定义泛型方法

泛型方法的格式：修饰符 <泛型变量> 方法返回值 方法名称(形参列表){}

作用：方法中可以使用泛型接收一切实际类型的参数，方法更具备通用性

示例代码：

public static void main(String[] args) {
    String[] names = {"小璐", "蓉容", "小何"};
    printArray(names);

    Integer[] ages = {10, 20, 30};
    printArray(ages);

    Integer[] ages2 = getArr(ages);  // 调用泛型函数，得到的内容不需要强转为具体的类型
    String[]  names2 = getArr(names);  // 传进去啥类型，返回出来还是啥类型
}

public static <T> T[] getArr(T[] arr){
    return arr;
}

1.4.3 自定义泛型接口

泛型接口的格式：修饰符 interface 接口名称<泛型变量>{}

作用：泛型接口可以让实现类选择当前功能需要操作的数据类型。

实现类可以在实现接口的时候传入自己操作的数据类型，这样重写的方法都将是针对于该类型的操作。

示例代码：

// 需求：教务系统，提供一个接口可约束一定要完成数据（学生，老师）的增删改查操作
public class Student {
}

public class Teacher {
}

public interface Data<E> {  // 操作数据的接口
    void add(E e);
    void delete(int id);
    void update(E e);
    E queryById(int id);
}

public class StudentData implements Data<Student>{  // 操作学生类数据的实现
    @Override
    public void add(Student student) {

    }

    @Override
    public void delete(int id) {

    }

    @Override
    public void update(Student student) {

    }

    @Override
    public Student queryById(int id) {
        return null;
    }
}

public class TeacherData implements Data<Teacher>{  // 操作教师类数据的实现
    @Override
    public void add(Teacher teacher) {

    }

    @Override
    public void delete(int id) {

    }

    @Override
    public void update(Teacher teacher) {

    }

    @Override
    public Teacher queryById(int id) {
        return null;
    }
}

1.4.4 泛型通配符、上下限

通配符：?

• ? 可以在“使用泛型”的时候代表一切类型。就是在应该填泛型的位置，填 “<?>” 。

• E T K V 是在定义泛型的时候使用的。

泛型的上下限：

• 泛型上限： <? extends Car>，必须是Car或者其子类
• 泛型下限：<? super Car> ，必须是Car或者其父类 ，用的相对较少

2. Collection 集合

2.1 关于 Collection 自身

Collection 是单列集合的祖宗接口，它的功能是全部单列集合都可以继承使用的。

Collection 的常用 API：

方法名称	说明
public boolean add(E e)	把给定的对象添加到当前集合中
public boolean addAll(E e)	把c2(参数)集合的元素全部倒入到c1(被调集合)中去
public void clear()	清空集合中所有的元素
public boolean remove(E e)	把给定的对象在当前集合中删除
public boolean contains(Object obj)	判断当前集合中是否包含给定的对象
public boolean isEmpty()	判断当前集合是否为空
public int size()	返回集合中元素的个数。
public Object[] toArray()	把集合中的元素，存储到数组中

Collection 集合的遍历：

• 法1：迭代器

  迭代器（Java 中为 Iterator）是集合的专用遍历方式。

  Collection 集合获取迭代器：

  Iterator<E> iterator()，返回集合中的迭代器对象，该迭代器对象默认指向当前集合的 0 索引

  Iterator中的常用方法：

  方法名称	说明
  boolean hasNext()	询问当前位置是否有元素存在，存在返回true ,不存在返回false
  E next()	获取当前位置的元素，并同时将迭代器对象移向下一个位置，注意防止取出越界。

  迭代器取元素越界会出现 NoSuchElementException 异常。

  遍历流程的示例代码：

  public class CollectionDemo01 {
      public static void main(String[] args) {
          ArrayList<String> lists = new ArrayList<>();
          Collections.addAll(lists, "赵敏","小昭", "素素","灭绝");
          System.out.println(lists);  // [赵敏, 小昭, 素素, 灭绝]
  
          // 1、得到当前集合的迭代器对象。
          Iterator<String> it = lists.iterator();
  
          // 2、定义while循环
          while (it.hasNext()){
              String ele = it.next();
              System.out.println(ele);
          }
          System.out.println("-----------------------------");
      }
  }
  

• 法2：foreach / 增强 for 循环

  增强 for 循环：既可以遍历集合也可以遍历数组

  遍历格式：

   for(被遍历集合或者数组中元素的类型 变量名称 : 被遍历集合或者数组){
    //在此处使用变量即可，该变量就是元素
  }
  

  遍历流程的示例代码：

  public static void main(String[] args) {
      Collection<String> lists = new ArrayList<>();
      System.out.println(lists);  // [赵敏, 小昭, 殷素素, 周芷若]
  
      for (String ele : lists) {
          System.out.println(ele);
      }
  }
  

  ⚠️ 注意：修改第三方变量的值不会影响到集合中的元素。即，在上述代码中修改 ele 的值，不会影响到 lists 中当前元素的值，故不能通过 foreach 循环来修改元素的值。

  使用增强 for 的快捷键

  IDEA 中输入：lists.for，此时会自动提示增强 for

• 法3：lambda 表达式

  JDK 1.8开始之后的新技术Lambda表达式，故有一种更简单、更直接的遍历集合的方式

  Collection 结合 Lambda 遍历集合的 API：

  方法名称	说明
  default void forEach(Consumer<? super T> action):	结合lambda遍历集合

  遍历流程的示例代码：

  lists.forEach(new Consumer<String>() {
      @Override
      public void accept(String s) {
          System.out.println(s);
      }
  });
  
  // 简化为：《需要掌握的方法》
  lists.forEach(s -> {
      System.out.println(s);
  });
  
  // 进一步简化:
  lists.forEach(s ->  System.out.println(s) );
  
  // 终版简化：
  lists.forEach(System.out::println );
  

  📝 consumer 的具体含义先不用管，会用 forEach 这个方法遍历就行了。

集合中存储的元素是元素对象的地址

集合的并发修改异常问题

Q：当我们从集合中找出某个元素并删除的时候可能出现一种并发修改异常问题

哪些遍历存在问题？

• 迭代器遍历集合且直接用集合删除元素的时候可能出现
• 增强 for 循环遍历集合且直接用集合删除元素的时候可能出现
• Lambda 遍历不能边遍历边删除，会出 bug

哪种遍历且删除元素不出问题？

• 迭代器遍历集合但是用迭代器自己的删除方法操作可以解决
• 使用 for 循环遍历并删除元素不会存在这个问题

示例：

    public static void main(String[] args) {
        // 1、准备数据
        ArrayList<String> list = new ArrayList<>();
        // 添加一批元素
        System.out.println(list); // [黑马, Java, Java, 赵敏, 赵敏, 素素]

        // 需求：删除全部的Java信息。
        // a、迭代器遍历删除
        Iterator<String> it = list.iterator();
        while (it.hasNext()){
            String ele = it.next();
            if("Java".equals(ele)){
                // 删除Java
                // list.remove(ele); // 集合删除会出毛病
                it.remove(); // 删除迭代器所在位置的元素值（没毛病）
            }
        }
        System.out.println(list);

        // b、foreach遍历删除 (会出现问题，这种无法解决的，foreach不能边遍历边删除，会出bug)
        for (String s : list) {
            if("Java".equals(s)){
                list.remove(s);
            }
        }

        // c、lambda表达式(会出现问题，这种无法解决的，Lambda遍历不能边遍历边删除，会出bug)
        list.forEach(s -> {
            if("Java".equals(s)){
                list.remove(s);
            }
        });

        // d、for循环(边遍历边删除集合没毛病，但是必须从后面开始遍历删除才不会出现漏掉应该删除的元素)
        for (int i = list.size() - 1; i >= 0 ; i--) {
            String ele = list.get(i);
            if("Java".equals(ele)){
                list.remove(ele);
            }
        }
        System.out.println(list);
    }

2.2 常见的数据结构

队列：先进先出，后进后出。

栈：后进先出，先进后出。

数组：内存连续区域，查询快，增删慢。

链表：元素是游离的，查询慢，首尾操作极快。

二叉树：永远只有一个根节点, 每个结点不超过2个子节点的树。

查找二叉树：小的左边，大的右边，但是可能树很高，查询性能变差。

平衡查找二叉树：让树的高度差不大于1，增删改查都提高了。

红黑树（就是基于红黑规则实现了自平衡的排序二叉树）

2.3 Collection 之 List 系列集合

List 系列集合特点：（1）有序：存储和取出的元素顺序一致；（2）有索引：可以通过索引操作元素；（3）可重复：存储的元素可以重复。

常见的两种为 ArrayList、LinekdList。

List 系列集合特有的方法：

List集合因为支持索引，所以多了很多索引操作的独特api，其他Collection的功能List也都继承了

方法名称	说明
void add(int index,E element)	在此集合中的指定位置插入指定的元素
E remove(int index)	删除指定索引处的元素，返回被删除的元素
E set(int index,E element)	修改指定索引处的元素，返回被修改的元素
E get(int index)	返回指定索引处的元素

List 系列集合的遍历方式：

①迭代器

②增强for循环

③Lambda表达式

④for循环（因为List集合存在索引）

2.3.1 ArrayList 集合的底层原理

ArrayList 底层是基于数组实现的：根据索引定位元素，快；增删相对慢，需要做元素的移位操作。

第一次创建集合并添加第一个元素的时候，在底层创建一个默认长度为10的数组

List集合存储的元素要超过容量时：扩容到原来大小的 1.5 倍。

2.3.2 LinkedList 集合的底层原理

LinkedList 底层基于双链表实现的，查询元素慢，增删首尾元素非常快，所以多了很多首尾操作的特有 API。

List 系列集合特有的方法：

方法名称	说明
public void addFirst(E e)	在该列表开头插入指定的元素
public void addLast(E e)	将指定的元素追加到此列表的末尾
public E getFirst()	返回此列表中的第一个元素
public E getLast()	返回此列表中的最后一个元素
public E removeFirst()	从此列表中删除并返回第一个元素
public E removeLast()	从此列表中删除并返回最后一个元素

✨ LinkedList 可以完成队列结构，和栈结构 （双链表），示例代码：

public static void main(String[] args) {
    // 1、做一个队列：
    LinkedList<String> queue = new LinkedList<>();
    // 入队
    queue.addLast("1号");
    queue.addLast("2号");
    queue.addLast("3号");
    System.out.println(queue);
    // 出队
    System.out.println(queue.removeFirst());
    System.out.println(queue.removeFirst());
    System.out.println(queue);

    // 2、做一个栈
    LinkedList<String> stack = new LinkedList<>();
    // 入栈 压栈 (push)
    stack.push("第1颗子弹");
    stack.push("第2颗子弹");
    stack.push("第3颗子弹");
    stack.push("第4颗子弹");
    System.out.println(stack);

    // 出栈  弹栈 pop
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack);

}

2.4 Collection 之 Set 系列集合

Set 系列集合的特点：（1）无序：存取顺序不一致；（2）不重复：可以去除重复；（3）无索引：没有带索引的方法，不能用普通for循环遍历，也不能通过索引来获取元素。

Set 集合实现类的特点：

• HashSet : 无序、不重复、无索引
• LinkedHashSet：有序、不重复、无索引
• TreeSet：排序、不重复、无索引

Set 集合的功能：基本与 Collection 的 API 一致。

2.4.1 HashSet 集合的底层原理

HashSet 集合底层采取哈希表存储的数据：对增删改查性能都很好。

Hash表的组成：

• JDK8之前的，底层使用数组 + 链表组成
• JDK8开始后，底层采用数组 + 链表 + 红黑树组成

Hash 值：

JDK 根据对象的地址，按照某种规则算出来的 int 类型的数值。

通过 Object 类的 API public int hashCode() 来返回对象的哈希值。

对象的 Hash 值的特点：

• 同一个对象多次调用 hashCode() 方法返回的哈希值是相同的
• 默认情况下，不同对象的哈希值不同

HashSet 原理详细流程解析：

1. 创建一个默认长度 16 、加载因子 0.75 的数组，数组名table
2. 根据元素的哈希值跟数组的长度求余计算出应存入的位置（哈希算法）
3. 判断当前位置是否为 null，如果是 null 直接存入
4. 如果位置不为 null，表示有元素，则调用 equals 方法比较属性值
   1. 如果一样，则不存；
   2. 如果不一样，则存入数组：
   • JDK 7 新元素占老元素位置，指向老元素
   • JDK 8 中新元素挂在老元素下面
5. 当挂在元素下面的数据过多时，查询性能降低。 从 JDK8 开始，当链表长度超过 8 的时候，自动转换为红黑树。
6. 当数组存满到 16*0.75=12 时，就自动扩容，每次扩容原先的两倍。

哈希表引入红黑树进一步提高了操作数据的性能。

总结：

• HashSet 元素无序的底层原理：使用了哈希表（Hash 值的计算规则导致了无序）。

• HashSet 去重复的底层原理：当该元素要存入的位置不为 null 时，会进行元素比较，不一样的才会存入。如流程 4 中所述。

💡 如果希望 Set 集合认为两个内容一样（而非地址一样）的对象是重复的，必须重写对象的 hashCode() 和 equals() 方法

2.4.2 LinkedHashSet 集合

特点：有序 不重复 无索引

LinkedHashSet 集合中“有序”的特点指的是保证存储和取出的元素顺序一致。

LinkedHashSet 集合底层也是基于哈希表实现的，只是每个元素又额外多了一个双链表机制记录存储的顺序。

2.4.3 TreeSet 集合

特点：不重复 无索引 可排序

TreeSet 集合中“可排序”的特点指的是按照元素的大小默认升序（有小到大）排序.

TreeSet 集合底层是基于红黑树的数据结构实现排序的，增删改查性能都较好.

💡 TreeSet 集合是一定要排序的，可以将元素按照指定的规则进行排序。

TreeSet 集合默认的排序规则：

• 数值类型：Integer , Double，官方默认按照大小进行升序排序。
• 字符串类型：默认按照首字符的编号升序排序。
• 自定义类型如 Student 对象，TreeSet 无法直接排序。

使用 TreeSet 存储自定义类型，需要制定排序规则:

• 方法一：让自定义的类（如苹果类）实现 Comparable 接口重写里面的 compareTo 方法来定制比较规则；
• 方法二（推荐）：TreeSet 集合有参数构造器，可以设置 Comparator 接口对应的比较器对象，来定制比较规则。

关于返回值的规则：

• 元素1 > 元素2：return 正整数；
• 元素1 < 元素2：return 负整数；
• 元素1 == 元素2：return 0，此时 Treeset 集合只会保留一个元素，认为两者重复。

示例代码：

public class Apple implements Comparable<Apple>{
    private String name;
    private String color;
    private double price;
    private int weight;

    public Apple() {
    }

    @Override
    public String toString() {
        return "Apple{" +
                "name='" + name + '\'' +
                ", color='" + color + '\'' +
                ", price=" + price +
                ", weight=" + weight +
                '}';
    }

    /**
      方式一：类自定义比较规则
      o1.compareTo(o2)
     * @param o
     * @return
     */
    @Override
    public int compareTo(Apple o) {
        // 按照重量进行比较的
        return this.weight - o.weight ; // 去重重量重复的元素
        // return this.weight - o.weight >= 0 ? 1 : -1; // 保留重量重复的元素
    }
}

public class SetDemo5 {
    public static void main(String[] args) {
        // 方式二：集合自带比较器对象进行规则定制
        //
//        Set<Apple> apples = new TreeSet<>(new Comparator<Apple>() {
//            @Override
//            public int compare(Apple o1, Apple o2) {
//                // return o1.getWeight() - o2.getWeight(); // 升序
//                // return o2.getWeight() - o1.getWeight(); // 降序
//                // 注意：浮点型建议直接使用Double.compare进行比较
//                // return Double.compare(o1.getPrice() , o2.getPrice()); // 升序
//                return Double.compare(o2.getPrice() , o1.getPrice()); // 降序
//            }
//        });

        Set<Apple> apples = new TreeSet<>(( o1,  o2) ->  Double.compare(o2.getPrice() , o1.getPrice())  );
        apples.add(new Apple("红富士", "红色", 9.9, 500));
        apples.add(new Apple("青苹果", "绿色", 15.9, 300));
        apples.add(new Apple("绿苹果", "青色", 29.9, 400));
        apples.add(new Apple("黄苹果", "黄色", 9.8, 500));
        System.out.println(apples);
    }
}

2.5 Collection 体系的特点、使用场景总结

• 如果希望元素可以重复，又有索引，索引查询要快？
  • 用 ArrayList 集合，基于数组的。（用的最多）
• 如果希望元素可以重复，又有索引，增删首尾操作快？
  • 用 LinkedList 集合，基于链表的。
• 如果希望增删改查都快，但是元素不重复、无序、无索引。
  • 用 HashSet 集合，基于哈希表的
• 如果希望增删改查都快，但是元素不重复、有序、无索引。
  • 用 LinkedHashSet 集合，基于哈希表和双链表。
• 如果要对对象进行排序。
  • 用 TreeSet 集合，基于红黑树。后续也可以用List集合实现排序

3. Collections 集合工具类

java.utils.Collections：是集合工具类

作用：用来操作集合的一个工具类。

⚠️ Collections 并不属于集合，只是一个为了操作集合而造出的一个工具类。

Collections 的常用API：

方法名称	说明
public static <T> boolean addAll(Collection<? super T> c, T... elements)	给集合对象批量添加元素
public static void shuffle(List<?> list)	打乱List集合元素的顺序

Collections 排序相关API：

使用范围：只能对于List集合的排序。

排序方式1：

方法名称	说明
public static <T> void sort(List<T> list)	将集合中元素按照默认规则排序

⚠️ 注意：本方式不可以直接对自定义类型的List集合排序，除非自定义类型实现了比较规则Comparable接口。

排序方式2：

方法名称	说明
public static <T> void sort(List<T> list, Comparator<? super T> c)	将集合中元素按照指定规则排序

示例代码 1： (使用排序方式 1)

public class CollectionsDemo01 {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        //names.add("楚留香");
        //names.add("胡铁花");
        //names.add("张无忌");
        //names.add("陆小凤");
        Collections.addAll(names, "楚留香","胡铁花", "张无忌","陆小凤");
        System.out.println(names);

        // 2、public static void shuffle(List<?> list) :打乱集合顺序。
        Collections.shuffle(names);
        System.out.println(names);

        // 3、 public static <T> void sort(List<T> list):将集合中元素按照默认规则排序。 （排值特性的元素）
        List<Integer> list = new ArrayList<>();
        Collections.addAll(list, 12, 23, 2, 4);
        System.out.println(list);
        Collections.sort(list);
        System.out.println(list);
    }
}

示例代码 2： (使用排序方式 2)

public class CollectionsDemo02 {
    public static void main(String[] args) {
        List<Apple> apples = new ArrayList<>(); // 可以重复！
        apples.add(new Apple("红富士", "红色", 9.9, 500));
        apples.add(new Apple("青苹果", "绿色", 15.9, 300));
        apples.add(new Apple("绿苹果", "青色", 29.9, 400));
        apples.add(new Apple("黄苹果", "黄色", 9.8, 500));

//        Collections.sort(apples); // 方法一：可以的，Apple类已经重写了比较规则
//        System.out.println(apples);

        // 方式二：sort方法自带比较器对象
//        Collections.sort(apples, new Comparator<Apple>() {
//            @Override
//            public int compare(Apple o1, Apple o2) {
//                return Double.compare(o1.getPrice() , o2.getPrice()); // 按照价格排序！！
//            }
//        });

        Collections.sort(apples, ( o1,  o2) ->  Double.compare(o1.getPrice() , o2.getPrice()) );
        System.out.println(apples);

    }
}