08-1-集合

✨你好啊，我是“ 罗师傅”，是一名程序猿哦。
🌍主页链接：楚门的世界 - 一个热爱学习和运动的程序猿
☀️博文主更方向为：分享自己的快乐 briup-jp3-ing
❤️一个“不想让我曾没有做好的也成为你的遗憾”的博主。
💪很高兴与你相遇，一起加油！

前言

目标：Java基础编程，熟练Java开发语法和规则，养成良好编程习惯

集合

我们之前学习过数组，数组特点如下：

• 长度固定：数组在创建时需要指定长度，并且长度在创建后不可改变
• 相同数据类型：例如int数组只能存储int类型的数据
• 连续内存分配：堆空间为数组开辟的内存是连续的，这也导致在插入和删除元素时需要元素整体移动，效率低下
• 随机访问：由于数组中的元素在内存中是连续存储的，并且可以通过索引来访问，因此可以通过索引直接访问数组中的任意元素，时间复杂度为O(1)

如果我们要存储的多个元素值数据类型不一致，或个数不固定时，数组就无法完美的满足我们的要求，这个时候我们会使用Java中提供的集合框架。

集合概述

集合（Collection）是一种用于存储和操作一组对象的数据结构。它提供了一组接口和类，用于处理和操作对象的集合。

集合框架（Collection Framework）是Java中用于表示和操作集合的一组类和接口，位于java.util包中，并提供了一系列的接口和类，包括集合接口（Collection）、列表接口（List）、集合类（Set）、映射接口（Map）等

集合框架的主要目标是提供一种通用的方式来存储和操作对象的集合，无论集合 的集体实现方式如何，用户都可以使用同一的接口和方法操作集合。

集合和数组都可以存储多个元素值，对比数组，我们来理解下集合：

• 数组的长度是固定的，集合的长度是可变的
• 数组中存储的是同一类型的元素(也可以是不同类型Object)，集合中存储的数据可以是不同类型的
• 数组中可以存放基本类型数据或者引用类型变量，集合中只能存放引用类型变量
• 数组是由JVM中现有的类型+[]组合而成的，除了一个length属性，还有从Object中继承过来的方法之外，数组对象就调用不到其他属性和方法了。
• 集合框架由 java.util包下多个接口和实现类组成，定义并实现了很多方法，功能强大。

框架体系

集合框架主要有三个要素组成：

• 接口

整个集合框架的上层结构，都是用接口进行组织的。接口中定义了集合中必须要有的基本方法。

通过接口还把集合划分成了几种不同的类型，每一种集合都有自己对应的接口。

• 实现类

对于上层使用接口划分好的集合种类，每种集合的接口都会有对应的实现类。

每一种接口的实现类很可能有多个，每个的实现方式也会各有不同

• 数据结构

每个实现类都实现了接口中所定义的最基本的方法，例如对数据的存储、检索、操作等方法。但是不同的实现类，它们存储数据的方式不同，也就是使用的数据结构不同。

集合框架继承体系图：

集合分类：

• 单列集合（Single Column Collection）
  • 根接口：java.util.Collection
  • 单列集合是指每个集合元素只包含一个单独的对象，它是集合框架中最简单的形式
• 多列集合（Multiple Column Collection)
  • java.util.Map
  • 多列集合是指每个集合元素由多个列（字段）组成，可以同时存储和操作多个相关的值。

下面只是列出了常用的实现类 噢噢~~

注意事项：

• 图中列出了Java集合框架中的主要接口（并非全部），以及它们之间的继承关系
• 接口中定义了该种集合具有的主要方法
• 将来真正要使用的，是这些接口的实现类，每种实现类对接口的实现方式不同，地城所用的数据结构不同，其特点不同

集合章节学习基本要求：

• 要求会用集合存储数据
• 可以从集合中取出数据
• 掌握每种集合的特点和应用场景

Collection

Collection接口是单列集合类的父接口，这种集合可以将数据一个一个的存放到集合中。它有两个重要的子接口，分别是 java.util.List 和 java.util.Set

Collection 是父接口，其中定义了单列集合（List和Set）通用的一些方法

Collection接口的实现类，都可以使用这些方法

Collection集合基础方法

// 具体使用看文档
// 下面是Collection的基础方法 E表示泛型
public interface Collection<E> extends Iterable<E> {
    //向集合中添加元素
    boolean add(E e)
        //清空集合中所有的元素。
        void clear()
        //判断当前集合中是否包含给定的对象。
        boolean contains(Object o) // 底层用的是重写的equals进行比较
        //判断当前集合是否为空。
        boolean isEmpty()
        //把给定的对象，在当前集合中删除。
        boolean remove(Object o)
        //返回集合中元素的个数。
        int size()
        //把集合中的元素，存储到数组中。
        Object[] toArray()
}

警告问题处理

• 集合接口引用指向实现类对象，固定书写格式：

接口类型<存储的数据类型> 接口引用名 = new 实现类<>(构造方法实参);
Collection<String> coll = new ArrayList<>();

注意：上述格式定义的集合对象，只能存储String类型的元素，如果存放其他引 用类型元素，则编译报错。

• 集合中父类或实现类引用，指向具体对象的写法也是如此

ArrayList<Student> list = new ArrayList<>();

注意，此时创建的list集合，只能存储Student类对象。

Collection 泛型参数 方法补充

public interface Collection<E> extends Iterable<E> {
  //把一个指定集合中的所有数据，添加到当前集合中
  boolean addAll(Collection<? extends E> c)
        //判断当前集合中是否包含给定的集合的所有元素。
        boolean containsAll(Collection<?> c)
        //把给定的集合中的所有元素，在当前集合中删除。
        boolean removeAll(Collection<?> c)
        //判断俩个集合中是否有相同的元素，如果有当前集合只保留相同元素，如果没有当前集合元素清空
        boolean retainAll(Collection<?> c)
        //把集合中的元素，存储到数组中，并指定数组的类型
        <T> T[] toArray(T[] a)
        //返回遍历这个集合的迭代器对象
        Iterator<E> iterator()
}

package com.briup.chap08.test;

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

public class Test03_Element {
 public static void main(String[] args) {
     Collection<Object> c1 = new ArrayList<>();
     String s1 = "hello";
     String s2 = "world";
     c1.add(s1);
     c1.add(s2);
     String s6 = new String("world");
     // 结果显示true，说明集合contains方法借助equals方法进行比较，而非 ==
     // 原因：ArrayList的父类AbstractList重写了equals方法
     boolean f = c1.contains(s6);
     System.out.println("contains(s6): " + f); // true 
 }
}

集合存放自定义类对象

public class Test03_Student {
 public static void main(String[] args) {
     // 准备学生对象，注意s1和s5两个对象的属性一模一样
     Student s1 = new Student("zs", 20);
     Student s2 = new Student("ls", 19);
     Student s3 = new Student("ww", 22);
     Student s4 = new Student("tom", 18);
     Student s5 = new Student("zs", 20);
     // 1.定义只能存储Student对象的集合
     Collection<Student> coll = new ArrayList<>();
     // 2.往集合中添加元素
     coll.add(s1);
     coll.add(s2);
     coll.add(s3);
     coll.add(s4);
     // 3.输出集合元素个数，输出集合对象
     System.out.println("coll.size: " + coll.size());
     System.out.println("coll: " + coll);
     System.out.println("------------");
     // 4.判断s5是否存在
     boolean flag = coll.contains(s5);
     System.out.println("contains(s5): " + flag); // true
     // 5.删除s5
     flag = coll.remove(s5);
     System.out.println("remove(s5): " + flag); // true
     System.out.println("coll.size: " + coll.size());
     System.out.println("coll: " + coll);
 }
}

注意事项：集合中contains、remove等方法，底层借助元素对象的equals方法进行值比较，所以如果要用集合存放自定义类对象，注意重写自定义类的equals方法！

集合遍历

toArray

借助Collection接口中toArray()方法实现，方法原型为： Object[] toArray();

//将集合转化成数组
Object[] array = 集合引用.toArray();
//遍历数组
for (int i = 0; i < array.length; i++) {
 System.out.println(array[i]);
}

迭代器

迭代器是集合框架提供的一种遍历集合元素的方式。通过调用集合的 iterator() 方法可以获取一个迭代器对象，然后使用迭代器的 hasNext() 方法判断是否还有下一个元素，使用 next() 方法获取下一个元素。

//1.获取迭代器对象
Iterator<集合元素类型> iterator = 集合对象.iterator();
//2.借助迭代器中hasNext()和next()方法完成遍历
while (iterator.hasNext()) {
 //获取集合元素
 集合元素类型 变量名 = iterator.next();
 //对集合元素进行输出
 System.out.println(变量名);
}

注意，这种迭代器方式获取集合中的每一个元素，是一种Collection集合及 其子类型集合通用的方式

迭代器原理分析（补充内容，了解即可）：

• java.lang.Iterable 接口中，定义了获取迭代器的方法

public interface Iterable {
    Iterator iterator();
}

• java.util.Collection接口继承了java.lang.Iterable接口

public interface Collection extends Iterable {
    //...
}

所以，Collection接口及其子接口中，都有一个获取迭代器对象的方法：Iterator iterator();

• java.util.Iterator 接口中，主要定义两个方法

public interface Iterator {
    //返回当前迭代器中是否还有下一个对象
    boolean hasNext();
    //获取迭代器中的下一个对象
    Object next();
}

迭代其实现原理：

• 获取迭代器对象：集合类实现了Iterable接口，该接口定义了一个iterator()方法，用于获取迭代器对象。迭代器对象是实现了Iterator接口的具体类的实例。
• 迭代器位置初始化：在创建迭代器对象时，迭代器的位置通常初始化集合的起始位置。不同的集合实现可能对位置初始化进行不同的处理。
• 遍历集合元素：通过调用迭代器对象的hasNext()方法，可判断集合中是否还有下一个元素。如果有下一个元素，可以通过next()方法获取下一个元素，并将迭代器的位置后移。
• 迭代器状态管理：迭代器对象会记录当前迭代的状态，包括当前位置、遍历过程中的操作等。这些状态可以帮助迭代器在遍历过程中正确地访问和操作集合的元素。
• 结束迭代：当集合中没有更多元素时，迭代器的**hasNext()**方法将返回false，表示遍历结束。

迭代器next方法示意图：

注意事项：

• 迭代器的优点是提供了一种统一的遍历方式，对单列集合（直接或间接实现Collection接口），都可以通过迭代器按顺序访问元素。
• 迭代器隐藏了集合的具体实现细节，提供了一种抽象的访问接口，是代码更加灵活何可复用。
• 迭代器是单向的，只能从前往后遍历，无法倒序遍历或者在遍历过程中修改集合
• 如果在迭代过程中队集合进行修改（添加、删除元素），可能会导致迭代器抛出ConcurrentModificationException异常。因此，在使用迭代器遍历时，不要修改集合结构

foreach

除了使用迭代器遍历集合之外，JDK1.5及以后版本JDK，提供了增强for循环实现集合遍历，这种方式相对迭代器遍历更简单。

for(集合元素类型 变量名 : 集合) {
 //操作元素变量
}

每次循环，引用变量会指向集合中的一个元素对象，然后在循环体中对该元 素对象进行操作（只能遍历）

public static void main(String[] args) {
 // 1.实例化集合对象，专门存放String元素
 Collection<String> c1 = new ArrayList<>();
 // 2.添加元素
 c1.add("lwsj");
 c1.add("peter");
 c1.add("parker");
 // 3.foreach遍历
 for (String str : c1) {
     System.out.println(str);
 }
}

可以看出，使用foreach循环对集合进行遍历，会更加简单一些

同时，使用foreach循环也可以遍历数组

public static void main(String[] args) {
 int[] arr = {1,3,5,7,9};
 //每次循环，使用变量i接收数组中的一个数据
 for(int i : arr){
     System.out.println(i);
 }
}

注意：Collection及其子类型的集合，还有数组，都可以使用foreach循环进行遍历！

List接口

java.util.List 接口继承了Collection接口，是常用的一种集合类型。

List集合具有Collection集合的特点之外，还具有自己的一些特点

• List是一种有序集合
• List是一种带索引的集合
• List集合可以存放重复的元素

继承体系

List接口继承了Collection接口，Collection接口继承了Iterable接口

List接口源码：

List接口的实现类：

注意，这些实现类中，都已经实现了List接口、Collection接口、Iterable接口中的方法，我们只要了解并能使用这些接口中的方法，就已经能够操作这些集合对象了（面向接口）。

额外的，我们还需要了解这些常用的接口实现类，分别都是什么特点，使用什么数据结构，一适合在什么样的场景下使用。

常用方法

//返回集合中指定位置的元素。
E get(int index);
//用指定元素替换集合中指定位置的元素,并返回被替代的旧元素。
E set(int index, E element);
//将指定的元素，添加到该集合中的指定位置上。
void add(int index, E element);
//从指定位置开始，把另一个集合的所有元素添加进来
boolean addAll(int index, Collection<? extends E> c);
//移除列表中指定位置的元素, 并返回被移除的元素。
E remove(int index);
//查收指定元素在集合中的所有，从前往后查到的第一个元素（List集合可以重复存放数据）
int indexOf(Object o);
//查收指定元素在集合中的所有，从后往前查到的第一个元素（List集合可以重复存放数据）
int lastIndexOf(Object o);
//根据指定开始和结束位置，截取出集合中的一部分数据
List<E> subList(int fromIndex, int toIndex);

注意：除了这些方法之外，还有从父接口Collection中继承过来的方法。

List集合的方法使用：

public class Test052_List {
 public static void main(String[] args) {
     List<String> list = new ArrayList<>();
     list.add("lwsj");
     list.add("peter");
     list.add("parker");
     list.add("parker"); // 可重复
     list.add(1, "world"); // 指定位置插入，后面的整体往后移动
     list.remove(2);
     list.set(3, "falao");
     System.out.println(list);
     // 遍历
     for (int i = 0; i < list.size(); i++) {
         System.out.println(list.get(i));
     }
     System.out.println("-----------------------------");
     for (String str : list) {
         System.out.println(str);
     }
     System.out.println("-----------------------------");
     Iterator<String> it = list.iterator();
     while (it.hasNext()) {
         String str = it.next();
         System.out.println(str);
     }
 }
}

List集合的特点：有序可重复，并且可以使用下标索引进行访问

ArrayList

java.util.ArrayList是最常用的一种List类型集合，ArrayList类底层使用数组来实现数据的存储，所以它的特点是：增删慢，查找快。

在日常的开发中，查询数据也是用的最多的功能，所以ArrayList是最常用的集 合。

但是，如果项目中对性能要求较高，并且在集合中大量的数据做增删操作，那 么 ArrayList 就不太适合了。

ArrayList源码：

package java.util;
/**
* Resizable-array implementation of the <tt>List</tt>
interface. Implements
* all optional list operations, and permits all elements,
including
* <tt>null</tt>.
* @see LinkedList
* @see Vector
* @since 1.2
*/
public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable,java.io.Serializable
{
    //省略...
    /**
    * Default initial capacity.
    */
    private static final int DEFAULT_CAPACITY = 10;
    /**
    * Shared empty array instance used for empty instances.
    */
    private static final Object[] EMPTY_ELEMENTDATA = {};
}

LinkedList

java.util.LinkedList底层采用的数据结构是双向链表，其特点是：增删快，查找慢。

它的特点刚好和 ArrayList 相反，所以在代码中，需要对集合中的元素做大量 的增删操作的时候，可以选择使用 LinkedList 。

注意：这里描述的快和慢，需要在大量的数据操作下，才可以体现，如果数据量不大的话，集合每一种集合的操作集合没有任何区别

特点验证：

实例化ArrayList、LinkedList集合对象，放入100000个元素，测试两种集合插 入、查询效率！

package com.briup.chap08.test;

import java.util.LinkedList;
import java.util.List;

public class Test054_LinkedList {
 public static void main(String[] args) {
     final int NUM = 100000;
     //		List<String> list = new ArrayList<>();
     List<String> list = new LinkedList<>();

     long start1 = System.currentTimeMillis();
     for (int i = 0; i < NUM; i++) {
         list.add(0, "hello" + i);
     }
     long end1 = System.currentTimeMillis();
     // 3.输出时长
     System.out.println(list.getClass().getSimpleName() + "插入" + NUM + "条数据耗时" + (end1 - start1) + "毫秒");

     // 4.开启计时，从集合种取 100000 个元素
     long start2 = System.currentTimeMillis();
     for (int i = 0; i < list.size(); i++) {
         list.get(i);
     }
     long end2 = System.currentTimeMillis();
     // 5.输出时长
     System.out.println(list.getClass().getSimpleName() + "检索" + NUM + "条数据耗时" + (end2 - start2) + "毫秒");
 }
}
// ArrayList插入100000条数据耗时532毫秒
// ArrayList检索100000条数据耗时1毫秒
// LinkedList插入100000条数据耗时33毫秒
// LinkedList检索100000条数据耗时19608毫秒 

• 注意事项：

  • list.getClass().getSimpleName; 获取list引用指向对象所属类型名（不含包名）

  • System.currentTimeMillis(); 获取当前时刻的时间戳

• 底层实现

LinkedList底层借助双向链表实现，双向链表又由节点构成，每个节点由三部分构成：两个引用（分别指向前、后节点），一个数据域（存储集合元素）。

LinkedList源码分析：

package java.util;
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable,
java.io.Serializable
{
    //省略...
    //头节点
    transient Node<E> first;
    //尾节点
    transient Node<E> last;
    //静态内部类：Node节点类
    private static class Node<E> {
        E item; //数据域，存储数据
        Node<E> next; //指针域：指向后一个节点
        Node<E> prev; //指针域：指向前一个结点
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

• 头尾节点操作方法

在LinkedList中，定义了一些操作头结点和尾结点的方法

//将指定元素插入此列表的开头
void addFirst(E e)
//将指定元素添加到此列表的结尾
void addLast(E e)
//返回此列表的第一个元素
E getFirst()
//返回此列表的最后一个元素
E getLast()
//移除并返回此列表的第一个元素
E removeFirst()
//移除并返回此列表的最后一个元素
E removeLast()
//从此列表所表示的堆栈处弹出一个元素
E pop()
//将元素推入此列表所表示的堆栈
void push(E e)

案例展示： 创建一个LinkedList对象，通过节点方法往里面添加、更新、删除元素。

import java.util.LinkedList;

public class Test054_Node {
    public static void main(String[] args) {
        // 注意，要测试LinkedList中的方法，必须用LinkedList引用指向LinkedList对象
        LinkedList<String> list = new LinkedList<>();
        list.add("lwsj");
        list.add("peter");
        list.add("parker");
        System.out.println(list);

        // 添加头尾节点
        list.addFirst("first");
        list.addLast("last");
        System.out.println(list);

        // 获取头尾节点
        System.out.println("getFirest: " + list.getFirst());
        System.out.println("getLast: " + list.getLast());

        // 删除头尾节点
        list.removeFirst();
        list.removeLast();
        System.out.println(list);
    }
}

Vector

Vector是在JDK1.0引入的，它实现了List接口，属于Java集合框架的一部分，其基于动态数组（Dynamic Array）实现，线程安全，Vector在功能和使用方式上和ArrayList非常相似。

ArrayList是在JDK1.2引入的，非线程安全，但单线程环境下性能更高效，是Vector一个非线程安全的替代品

Vector部分源码：

package java.util;
/**
* The {@code Vector} class implements a growable array of
* objects. Like an array, it contains components that can be
* accessed using an integer index.
* @see LinkedList
* @since JDK1.0
*/
public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable,java.io.Serializable
{
    //省略
    /**
    * 底层借助数组存储数据
    * The array buffer into which the components of the
    vector are
    * stored.
    */
    protected Object[] elementData;
}

Vector 内部也是采用了数组来存储数据，但是Vector中的方法大多数都是线程安全的方法，所以在多线程并发访问的环境中，可以使用Vector来保证集合中元数据操作的安全。

案例展示： 创建Vector集合，往里面添加元素，遍历输出，对比其和ArrayList的用法。

//Vector线程安全但效率较低
//其早期提供的方法使用较为繁琐
public class Test055_Vector {
    public static void main(String[] args) {
        //1.实例化Vector对象
        Vector<String> v = new Vector<>();
        //2.往集合中添加元素
        v.add("hello");
        //早期添加元素，相对麻烦
        v.addElement("123");
        v.addElement("abc");
        //3.遍历Vector
        // 早期遍历方式，相对麻烦 （有点像迭代器的雏形Iterable）
        Enumeration<String> elements = v.elements();
        while(elements.hasMoreElements()) {
            System.out.println(elements.nextElement());
        }
    }
}

结论：我们今后主要使用ArrayList。多线程环境需要保证线程安全的话，后期学 习工具类，可以使 ArrayList变成线程安全。

List小结

数据结构

概述

数据结构是计算机科学中研究数据组织、存储和操作的一门学科。它涉及了如何 组织和存储数据以及如何设计和实现不同的数据操作算法和技术。常见的据结构 有线性数据结构（含数组、链表、栈和队列等），非线性数据结构（树、图 等）。

注意：不同的数据结构适用于不同的场景和问题，选择合适的数据结构可以提高算法的效率和性能。

Java集合框架中不同的实现类底层借助不同数据结构来存储输出，常见的数据结 构有：

• 数组（Array）：有序集合，可以包含重复的元素，ArrayList、Vector
• 链表（LinkedList）：链表是一种动态数据结构，通过阶段之间的链接来组织数据。LinkedList
• 集合（Set）：集合是不允许包含重复元素的无序集合。HashSet、LinkedHasSet、TreeSet
• 映射（Map）：映射是一种键值对的集合，每个键只能对应一个值，HashMap、LinkedHashMap、TreeMap
• 队列（Queue）：队列是一种先进先出（FIFO）LinkedList、PriorityQueue
• 栈（Stack）：栈是一种后进先出（LIFO），Stack
• 树（Tree）：树是一种具有分层结构的数据结构，BinaryTree、BinarySearchTree

数组

看我这篇博客即可：04-数组

链表

链表（linked list），是由一个一个node节点组成，每个node节点中包含两项数 据：指针域、数据域。数据域存储了一个数据，指针域存储指向下一个node节 点对象的引用（单向链表）。

如果是双向链表的话，指针域会存储2个引用，一个指向前一个node节点对象， 另一个指向了下一个node节点对象。

单链表插入、删除节点：

总结：

• 插入和删除不需要像数组那样整体移动元素，所以效率高
• 查询第n个元素，必须从头结点开始逐个结点往后遍历，所以效率低

栈

栈（stack），又称堆栈，仅允许在栈的一段进行插入和删除操作，并且不允许在其他任何位置进行操作

其特点是：先进后出，最先存进去的元素，最后才能取出来。

例如，薯片存在薯片桶中，我们当前只能取出最上面的一个薯片，而最早存放到 薯片桶的薯片，反而是我们最后吃到的一片。

注意1：入栈也称为压栈，把数据存入到栈的顶端位置

注意2：出栈也称为弹栈，把栈顶位置的数据取出

思考，JVM中的栈区中，为什么把main方法标注在最低端位置？

在Java虚拟机（JVM）中，栈（Stack）是用来管理方法调用和局部变量的内存区域，每个线程都会有自己的栈。在JVM中，将“main”方法标注在栈的最低端位置是因为Java程序执行过程通常是从“main”方法开始的，然后逐步调用其他方法，形成方法调用的调用栈。

• 起始点：“main”方法是Java程序的起始点，JVM从这里开始会执行程序。
• 调用栈结构：Java程序中的方法调用是一个栈结构，“main”方法位于底部，其他方法调用逐步堆叠在上面。
• 清晰性：将“main”方法放在底部使程序执行路径更清晰，有助于调试和代码理解
• 编程约定： Java遵循入口点的编程约定，将main方法放在底部是与其他编程语言的一致性选择

队列

队列（Queue），仅允许在队列的一端进行插入，而在队列的另一端进行删除。

其特点是：先进先出，最先存进去的元素，可以最先取出来。

例如，火车穿过山洞的时候，第一节车厢先进去山洞的一端，并且这节车厢优先 从山洞的另一端出来，后面的车厢依次从一端进入并另一端出来。

红黑树

二叉树（Binary tree）是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树，且有左右之分

二叉树中有一种叫做红黑树（Red/Black Tree），它最早被称为平衡二叉B树（sysmmetric binary B-trees）,后来被称为红黑树。

红黑树是一种特殊化的平衡二叉树，它可以在进程插入和删除的时候，如果左右子树的高度相差较大，那么就通过特定操作（左旋、右旋）保持二叉查找树的平衡（动态平衡），从而获得较高的查找性能。

红黑树的每一个阶段的左子树的所有数据都比自己小，而右子树的所有数据都比自己大，并且左右子树的高度近似。

红黑树的约束：

• 根节点必须是黑色
• 其他节点可以是红色或黑色
• 叶子节点（特指null节点）是黑色
• 每个红色节点的子节点都是黑色的
• 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

注意，红黑树的指定颜色的目的，是利用颜色值作为二叉树的平衡对称性的检查

例如，从空树开始演示一个案例： 数字插入顺序为 9、8、12、7、6，对于一个节点来说，新数据如果小于本节 点，会被放在左节点的位置，反之则放在右节点的位置

[红黑树在线演示](Red/Black Tree Visualization (usfca.edu))

哈希表

java中的哈希表（hash），在JDK1.8之前是采用数组+链表进行实现，根据数据 的哈希值，把数据存在数组中，但是当前哈希值冲突的时候，再使用链表进行存 储，那么在数组中，同一hash值的数据都存在一个链表里。

注意，之前学习过Object中hashCode方法的作用，hash值的特点以及和对象之间 的关系

可以看出，当链表中元素过多，即hash值相等的元素较多时，查找的效率会变低。

JDK1.8中，哈希表存储采用数组+链表+红黑树进行实现，当链表长度超过阈值（8）时，将链表转换为红黑树，大大提高查找的性能。

Set集合

Set概述

java.util.Set接口继承了Collection接口，是常用的一种集合类型。

Set集合特点如下：除了具有Collection集合的特点，还具有自己的一些特点

• Set是一种无序的集合
• Set是一种不带下标索引的集合
• Set是一种不能存放重复数据的集合

重点学习的Set实现类：

• HashSet 底层借助哈希表实现
• TreeSet 底层借助二叉树实现

注意，TreeSet是Set接口的直接开SortedSet的实现类

基础案例： 实例化一个Set集合，往里面添加元素并输出，注意观察集合特点（无序、不 重复）。

public class Test071_SetBasic {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("hello1");
        set.add("hello2");
        set.add("hello3");
        set.add("hello4");
        set.add("hello5"); // 添加失败 重复元素
        set.add("hello5"); // 添加失败 重复元素
        for (String str : set) {
            System.out.print(str + " ");
        }
        System.out.println("\n---------------------");

        Iterator<String> it = set.iterator();
        while (it.hasNext()) {
            String str = it.next();
            System.out.print(str + " ");
        }
    }
}

HashSet

java.util.HashSet是Set接口的实现类，它使用哈希表（Hash table）作为其底层数据结构来存储数据

HashSet特点：

• 无序性：HashSet中的元素的存储顺序与插入顺序无关

HashSet使用哈希表来存储数据，哈希表根据元素的哈希值来确定元素的存储位置，而哈希值根据元素的内容计算得到的，与插入顺序无关。

• 唯一性：HashSet中不允许重复的元素，即每个允许都是唯一的
• 允许null元素：HashSet允许存储null元素，但只能存储一个null元素，HashSet中不允许重复元素
• 高效性：HashSet的插入、删除和查找操作的时间复杂度都是o(1)

哈希表通过将元素的哈希值映射到数组的索引来实现快速的插入、删除和查找操作

基础案例1： 实例化HashSet对象，往里面插入多个字符串，验证HashSet特点。

public class Test072_Basic {
    public static void main(String[] args) {
        // 1.实例化HashSet对象
        Set<String> set = new HashSet<>();
        // 2.往集合中添加元素
        set.add("hello");
        set.add("world");
        set.add("nihao");
        set.add("hello"); // 不能重复
        set.add(null); 
        set.add(null); // 不能重复
        System.out.println("size: " + set.size());
        // 3.遍历
        for (String str : set) {
            System.out.print(str + " ");
        }
    }
}
// size: 4
// null world nihao hello 
// 会发现null一直在前面

根据结果可知，HashSet无序、唯一、null值可存在。

基础案例2： 实例化HashSet对象，往里面存入多个自定义类Student对象，观察结果。

自定义Student类：

public class Test072_Student {
    public static void main(String[] args) {
        Set<Student> set = new HashSet<>(); // 没有重写Student的hashCode和equals
        set.add(new Student("lwsj", 23));
        set.add(new Student("lwsj", 23));
        set.add(new Student("lwsj", 23));
        System.out.println("size: " + set.size());

        for (Student stu : set) {
            System.out.println(stu);
        }
    }
}

从结果可知，HashSet认为4个数据成员一模一样的Student对象是不同的对象， 成功将它们添加到了集合中。这明显是不合理的，思考为什么？

元素插入过程：

• 当向HashSet中插入元素时，先获取元素的hashCode()值，在检查HashSet中是否存在相同哈希值的元素，如果元素哈希值唯一，则直接插入元素
• 如果存在相同哈希值的元素，会调用元素的equals()方法来进一步判断元素是否是相同。如果相同，则不会插入重复元素；如果不同，则插入。

hashCode() 方法复习：

• hashCode()方法是Object类中的一个方法，它返回一个int类型的哈希码值
• 通常情况下，hashCode()方法会根据对象的属性值计算一个哈希码值（重写自定义类中的hashCode方法）

hashCode的计算：

• 地址值相同的对象，hashCode一定相同
• hashCode相同的两个对象，不一定是同一个对象
• hashCode不同的两个对象，一定是不同对象

结论：如果要往HashSet集合存储自定义类对象，那么一定要重写自定义类中的hashCode方法和equals方法

TreeSet

TreeSet是SortedSet(Set接口的子接口)的实现类，它基于红黑树（Red-Black Tree）数据结构实现

TreeSet特点：

• 有序性

插入的元素会自动排序，每次插入、删除或查询操作后，TreeSet会自动调整元素的顺序，以保持有序性。

• 唯一性

TreeSet中不允许重复的元素，即集合中的元素是唯一的。如果尝试插入一个已经存在的元素，该操作将被忽略

• 动态性

TreeSet是一个动态集合，可以根据需要随时添加、删除和修改元素。插入和删除操作的时间复杂度为o(logn),其中n是集合中的元素数量。

• 高效性

由于TreeSet底层采用红黑树数据结构，它具有快速的查找和插入性能。对于有序集合的操作，TreeSet通常比HashSet更高效。

入门案例1： 准备一个TreeSet集合，放入多个Integer元素，观察是否自动进行排序。

TreeSet是一个有序集合，存储数据时，一定要指定元素的排序规则，有两种指定的方式，具体如下：

TreeSet排序规则：

• 自然排序（元素所属类型要实现 java.lang.Comparable接口）
• 比较器排序

上述2个案例中，Integer存如TreeSet没有报错，是因为Integer类已经实现自然排序，而Person类既没有实现自然排序，也没有额外指定比较器排序规则。

TreeSet：自然排序

如果一个类，实现了java.lang.Comparable接口，并重写了compareTo方法，那么这个类的对象就可以比较大小

public interface Comparable<T> {
 public int compareTo(T o);
}

compareTo方法说明：

int result = this.属性.compareTo(o.属性);

• result的值不大于0,说明this比o大 （交换）
• result的值大于0，说明this比o小 （不换）
• result的值等于0，说明this和o相等（remove是==0的时候删除）

元素插入过程：

当向TreeSet插入元素时，TreeSet会使用元素的compareTo()方法来比较元素之间的大小关系。根据比较结果，TreeSet会将元素插入到合适的位置，以保持有序性。如果两个元素相等（compareTo()方法返回0）,TreeSet会认为这是重复的元素，只会保留一个。

案例展示： 使用自然排序（先按name升序，name相同则按age降序）解决上述案例问题。

package com.briup.chap08.pojo;

public class Person implements Comparable<Person> {
    private String name;
    private int age;

    // 省略get、set、构造

	//重写方法，指定比较规则：先按name升序，name相同则按age降序
    @Override
    public int compareTo(Person o) {
        int r = name.compareTo(o.name);
        if (r == 0) {
            r = o.age - this.age;
        }
        return r;
    }
}

可以看出，Integer的两个对象比较大小，其实就是比较Integer对象对应的int值的大小（比值）

注意：compareTo方法返回值代表的含义（三种情况：正数、负数、零）

补充内容2：整形、浮点型、字符串自然排序规则

对于整形、浮点型元素，它们会按照从小到大的顺序进行排序。对于字符串类型的元素，它们会按照字典顺序进行排序。

注意事项：compareTo方法的返回结果，只关心正数、负数、零，不关心具体的 值是多少

TreeSet：比较器排序

比较器排序步骤：

• 创建一个实现了Comparator接口的比较器类，并重写其中的compare()方法

该方法定义了元素之间的比较规则。在 compare() 方法中，我们可以根据 元素的属性进行比较，并返回负整数、零或正整数，来表示元素之间的大小 关系。

• 创建TreeSet对象时，将比较器对象作为参数传递构造函数，这样，TreeSet会根据比较器来进行排序。

TreeSet构造器：

//实例化TreeSet类对象时，需要额外传入一个比较器类对象
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

java.util.Comparator 接口源码：

package java.util;
@FunctionalInterface // 函数式接口
public interface Comparator<T> {
    /**
    * Compares its two arguments for order. Returns a
    negative integer,
    * zero, or a positive integer as the first argument is
    less than, equal
    * to, or greater than the second.<p>
    */
    int compare(T o1, T o2);
    //省略...
}

compare方法说明：

int result = compare(o1, o2);

• result > 0, 升序
• result < 0, 降序
• resutl = 0, 不能插入

注意，这里和自然排序的规则是一样的，只关心正数、负数、零，不关心具体的 值是多少

案例说明： 使用比较器排序，对上述案例中Person进行排序，要求先按age升序，age相同 则按name降序。

public static void main(String[] args) {
    //1.准备自定义比较器对象
    // 匿名内部类形式
    Comparator<Person> comp = new Comparator<Person>() {
        //重写比较算法：先按按age升序，age相同则按name降序
        @Override
        public int compare(Person o1, Person o2) {
            int r = o1.getAge() - o2.getAge();
            if(r == 0) {
                //注意：字符串比较需要使用compareTo方法
                r = o2.getName().compareTo(o1.getName());
            }
            return r;
        }
    };
    //2.实例化TreeSet,传入自定义比较器对象
    Set<Person> set = new TreeSet<>(comp);
}

注意：如果同时使用自然排序和比较器排序，比较器排序将覆盖自然排序

自然排序：

• 使用元素类实现Comparable接口，并重写其中的**compareTo()**方法
• 元素会按照其自身的比较规则进行排序
• 自然排序是默认的排序方式，可以直接使用TreeSet或Collections.sort()方法进行排序
• 只能有一种自然排序方式

比较器排序：

• 使用Comparator对象来定义元素之间的比较规则
• 可以自定义排序规则，不依赖于元素类的实现Comparable接口
• 需要创建一个实现Comparator接口的比较器类，并重写其中的**compare()**方法
• 可以有多个比较器，根据需要选择不同的比较器进行排序
• 可以通过传入Comparator对象给TreeSet或Collections.sort()方法来进行比较器排序

LinkedHashSet

LinkedHashSet是HashSet的一个子类，具有HashSet的高效性能和唯一性特性，并且保持了元素的插入顺序，其底层基于哈希表和链实现。

案例展示：实例化一个LinkedHashSet集合对象，存入多个String字符串，观察是否唯一及顺序存储。

Set小结

Map集合

很多时候，我们会遇到成对出现的数据，例如，姓名和电话，身份证和人，IP和 域名等等，这种成对出现，并且一一对应的数据关系，叫做映射。 java.util.Map<k,v> 接口，就是专门处理这种映射关系数据的集合类型。 Map集合是一种用于存储键值对（key-value）映射关系的集合类。它提供了一种 快速查找和访问数据的方式，其中每个键都是唯一的，而值可以重复。

Map概述

Collection接口为单列集合的根接口，Map接口为双列集合的根接口。

Map集合与Collection集合，存储数据的形式不同

Map集合特点：

• 存储元素时，必须以key-value（键值对）的方法进行
• 键唯一性：Map集合中的键是唯一的，每个键只能对应一个值
• 可重复值：Map集合中的值可以重复，不同的键可以关联相同的值
• 高效的查找和访问：通过给定键key值(唯一)，可以快速获取与之对应的value值

Map集合内部使用哈希表或红黑树等数据结构来实现高效的查找和访问

Map接口常用方法（注意泛型K代表Key，范型V代表Value）：

//把key-value存到当前Map集合中
V put(K key, V value)
//把指定map中的所有key-value，存到当前Map集合中
void putAll(Map<? extends K,? extends V> m)
//当前Map集合中是否包含指定的key值
boolean containsKey(Object key)
//当前Map集合中是否包含指定的value值
boolean containsValue(Object value)
//清空当前Map集合中的所有数据
void clear()
//在当前Map集合中，通过指定的key值，获取对应的value
V get(Object key)
//在当前Map集合中，移除指定key及其对应的value
V remove(Object key)
//返回当前Map集合中的元素个数（一对key-value，算一个元素数据）
int size()
//判断当前Map集合是否为空
boolean isEmpty()
//返回Map集合中所有的key值
Set<K> keySet()
//返回Map集合中所有的value值
Collection<V> values()
//把Map集合中的的key-value封装成Entry类型对象，再存放到set集合中，并返回
Set<Map.Entry<K,V>> entrySet()

Map集合实现类： Java提供的Map集合实现类，常见的包括HashMap、TreeMap、LinkedHashMap 等。它们在内部实现和性能方面有所不同，可以根据具体需求选择适合的实现 类。

• HashMap

底层借助哈希表实现，元素的存取顺序不能保证一致。由于要保证键的唯一、不重复，需要重写键所属的类和hashCode()方法、equals()方法 (重要+最常用)

• Hashtable

和之前List集合中的Vector的功能类似，可以再多线程环境中，保证集合中的数据的操作安全（线程安全）

• LinkedHashMap

该类是HashMap的子类，存储数据采用哈希表+链表。通过链表结构可以保证元素的存取顺序一致（存入顺序就是取出顺序）

• TreeMap

该类是Map接口的子接口SortedMap下面的实现类，和TreeSet类似，它可以对key值进行排序，同时构造器也可以接收一个比较器对象作为参数。支持key值的自然排序和比较器排序两种方式（支持key排序）

Map遍历

• 第一种思路

借助Map中的keySet方法，获取一个Set集合对象，内部包含了Map集合中所有 的key，进而遍历Set集合获取每一个key值，再根据key获取对应的value。

// 第一种遍历
public static void main(String[] args) {
    Map<Integer, String> map = new HashMap<>();
    map.put(1, "zs");
    map.put(2, "ls");
    map.put(4, "rose");
    map.put(3, "jack");
    map.put(2, "lucy"); // lucy 会把 ls覆盖掉
    Set<Integer> keySet = map.keySet();
    for (Integer k : keySet) {
        String v = map.get(k);
        System.out.println("id: " + k + " name: " + v);
    }
}

• 第二种遍历

借助Map中的entrySet方法，获取一个Set对象，内部包含了Map集合中所有的 键值对，然后对键值对进行拆分，得到key和value进行输出。

// 第二种遍历方式
Set<Entry<Integer, String>> entrySet = map.entrySet();
for (Entry<Integer, String> entry : entrySet) {
    System.out.println(entry.getKey() + " " + entry.getValue());
}

• 第三种遍历方式

// lambda表达式进行遍历
map.forEach((k, v) -> System.out.println(k + " " + v));

HashMap

HashMap底层借助哈希表实现，元素的存取顺序不能保证一致。

HashMap存储的键值对，如果键类型为自定义类，那么一般需要重写键所属类的hashCode()和equals方法() （重要，最常用）

HashMap特点：

• 键唯一
• 值可重复
• 无序性
• 线程不安全
• 键和值允许使用null

public class Test083_HashMap {
    public static void main(String[] args) {
        // 1.实例化HashMap对象，其中key类型为自定义Student
        Map<Student, String> map = new HashMap<>();
        // 2.往集合中添加元素
        // map中插入键值对，调用key所属类的hashCode和equals方法进行判断是否重复
        map.put(new Student("zs", 78), "010");
        map.put(new Student("rose", 82), "005");
        map.put(new Student("lucy", 70), "009");
        map.put(new Student("lucy", 70), "019"); // 相同key，只能保留一项，"019"会覆盖"009"
        map.put(new Student("ww", 67), "002");
        // 注意：HashMap中key和value都可以为null
        map.put(new Student("tom", 86), null);
        map.put(null, "002");
        // 3.基本方法测试
        // 获取长度
        System.out.println("size: " + map.size());
        // 判断key是否存在
        // 借助 key所属类的hashCode和equals方法完成
        System.out.println("Student(ww,67)是否存在: " + map.containsKey(new Student("ww", 67)));
        // 判断value是否存在
        // 借助value所属类型的 equals方法
        System.out.println("是否存在 009: " + map.containsValue("009"));
        // 根据key删除，返回键对应的值
        String value = map.remove(new Student("lucy", 70));
        System.out.println("remove(Student(lucy, 70)): " + value);
        System.out.println("---------------");
        // 4.第一种遍历方法
        Set<Student> keySet = map.keySet();
        for (Student key : keySet) {
            System.out.println(key + ": " + map.get(key));
        }
        System.out.println("---------------");
        // 第二种方式遍历
        Set<Entry<Student, String>> entrySet = map.entrySet();
        for (Entry<Student, String> entry : entrySet) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

结论：key类型如果为自定义类型，重写其hashCode和equals方法！

• HashMap中add（key，value）时，需要判读key是否存在（先hashCode再equals）
• HashMap中containsKey（key），同样要借助hashCode和equals方法
• HashMap中的remove（key），同样要借助hashCode和equals方法

// HashSet源码分析
package java.util;
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    /**
    * Constructs a new, empty set; the backing
    <tt>HashMap</tt> instance has
    * default initial capacity (16) and load factor (0.75).
    */
    public HashSet() {
        map = new HashMap<>();
    }
    //添加元素，value值固定为Object类对象PRESENT
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    //省略...
}

Hashtable

Hashtable是Java中早期的哈希表实现，它实现了Map接口，并提供了键值对的存 储和访问功能。

Hashtable特点：

• JDK1.0提供，接口方法较为复杂，后期实现了Map接口
• 线程安全：Hashtable是线程安全的，相对于HashMap性能稍低
• 键和值不能为null：如果尝试使用null作为键或值，将会抛出NullPointerException
• 哈希表实现：和HashMap一样，内部使用哈希表数据结构来存储键值对

public class Test084_Hashtable {
    public static void main(String[] args) {
        Hashtable<Student, String> map = new Hashtable<>();
        map.put(new Student("zs", 78), "010");
        map.put(new Student("rose", 82), "005");
        map.put(new Student("lucy", 70), "009");
        map.put(new Student("lucy", 70), "019"); // 相同key，只能保留一项，"019"会覆盖"009"
        map.put(new Student("ww", 67), "002");
        // 注意：Hashtable中key和value不能为null，否则抛出NullPointerException
        // map.put(new Student("tom", 86), null);
        // map.put(null, "002");

        // 遍历
        Enumeration<Student> keys = map.keys();
        while (keys.hasMoreElements()) {
            Student key = keys.nextElement();
            String value = map.get(key);
            System.out.println(key + " : " + value);
        }
    }
}

Hashtable小结：

• 单线程环境下建议使用HashMap，性能更好
• 多线程环境下，建议使用HashMap + Collections (请听后序)

TreeMap

TreeMap是有序映射实现类，它实现了SortedMap接口，基于红黑树数据结构来存储键值对

TreeMap特点：

• 键的排序：TreeMap中的键是按照自然顺序或自定义比较器进行排序
• 红黑树实现：TreeMap内部使用红黑树这种自平衡二叉搜索树数据结构来存储键值对
• 键唯一，值可重复
• 线程不安全，如果在多线程环境下使用TreeMap,应该使用Collections工具类处理
• 初始容量：TreeMap没有初始容量的概念，它会根据插入的键值对动态地调整红黑树的大小

TreeMap 自然排序案例： 实例化TreeMap对象，添加元素并遍历，观察程序运行结果。

public class Test085_TreeMap {
    public static void main(String[] args) {
        Map<Integer,String> map = new TreeMap<>();
        map.put(4,"mary");
        map.put(2,"jack");
        map.put(1,"tom");
        map.put(3,"lucy");
        Set<Integer> keys = map.keySet();
        for(Integer key : keys){
            System.out.println(key + ": " + map.get(key));
        }
    }
}
// 1 : lucy
// 2 : tom
// 3 : jack
// 4 : mary

TreeMap 比较器排序案例：

创建TreeMap集合对象，额外指定比较器，要求按名字降序， 如果名字相同则按成绩升序。

public class Test086_TreeMapComparatorTest {
    public static void main(String[] args) {
        Comparator<Student> myComparator = new Comparator<Student>() {

            @Override
            public int compare(Student o1, Student o2) {
                int r = -o1.getName().compareTo(o2.getName());
                if (r == 0) {
                    r = Integer.valueOf(o1.getScore()).compareTo(Integer.valueOf(o2.getScore()));
                }
                return r;
            }
        };
        Map<Student, String> map = new TreeMap<>(myComparator);

        map.put(new Student("zs", 78), "010");
        map.put(new Student("rose", 82), "005");
        map.put(new Student("lucy", 79), "009");
        map.put(new Student("lucy", 79), "009");
        map.put(new Student("tom", 68), "019");
        map.put(new Student("tom", 86), "012");
        map.put(new Student("ww", 67), "002");
        // key不能为null,否则出 NullPointerException
        // map.put(null, "002");

        Set<Entry<Student, String>> entrySet = map.entrySet();
        for (Entry<Student, String> entry : entrySet) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }
    }
}

思考，如果要求重复的元素也能够放入，如何实现？

修改比较器中返回值即可：当r==0，即元素属性一样时，返回非0值即可。

Comparator<Student> myComparator = new Comparator<Student>() {

    @Override
    public int compare(Student o1, Student o2) {
        int r = -o1.getName().compareTo(o2.getName());
        if (r == 0) {
            r = Integer.valueOf(o1.getScore()).compareTo(Integer.valueOf(o2.getScore()));
        }
        // 当 r==0, 即元素属性一样是，返回非0值即可
        return r == 0 ? 1 : r;
    }
};

TreeMap小结：

TreeMap底层借助红黑树实现，它提供了搞笑的有序映射功能，可以用于范围查找、排序何遍历等操作。但红黑树的平衡操作会带来额外的开销，相比于HashMap等实现类，TreeMap在插入和除操作可能稍慢。

LinkedHashMap

LinkedHashMap是HashMap的一个子类，底层在哈希表的基础上，通过维护一个双向链表来保持键值对的有序性，可以保证存取次序一致。

LinkedHashMap 基础案例： 创建LinkedHashMap对象，添加元素，观察是否存取次序一 致。

public class Test086_LinkedHashMap {
 public static void main(String[] args) {
     Map<String, Student> map = new LinkedHashMap<>();
     // 2.添加元素
     map.put("010", new Student("zs", 78));
     map.put("005", new Student("rose", 82));
     map.put("009", new Student("lucy", 70));
     map.put("019", new Student("lucy", 70)); // value可以重复
     map.put("002", null);
     map.put(null, new Student("ww", 67));

     for (String key : map.keySet()) {
         System.out.println(key + " : " + map.get(key));
     }
 }
}

可以看出，数据存入Map中的顺序，就是存储的顺序，也是取出的顺序！

Map小结

Collections

数组工具类是java.util.Arrays,可以专门来操作数组对象，提供静态方法，可直接调用

集合工具类是java.util.Collections, 专门来操作集合对象，里边都是静态方法，可以直接调用。

注意：Collection是单列集合根接口，Collections是集合工具类，两者不同！

• Collections 常用方法：

package java.util;
public class Collections {
    // 类外不能实例化对象，工具类主要调用static方法
    private Collections() {
    }
    //填充元素值
    public static <T> void fill(List<? super T> list, T obj) {
        //省略...
    }
    //获取最大值
    public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) {
        Iterator<? extends T> i = coll.iterator();
        T candidate = i.next();
        while (i.hasNext()) {
            T next = i.next();
            if (next.compareTo(candidate) > 0)
                candidate = next;
        }
        return candidate;
    }
    //排序
    @SuppressWarnings("unchecked")
    public static <T extends Comparable<? super T>> void  sort(List<T> list) {
        list.sort(null);
    }
    //省略 ...
}

具体方法讲解

• fill方法，使用指定元素替换指定列表中的所有元素

List<Integer> list = new ArrayList<>();
list.add(0);
list.add(1);
list.add(2);
Collections.fill(list, 100);
for (Integer num : list) {
    System.out.println(num);
}

• max方法，根据元素的自然顺序，返回给定集合的最大元素

List<Integer> list = new ArrayList<>();
list.add(0);
list.add(65);
list.add(2);
System.out.println(Collections.max(list));

• min 方法，根据元素的自然顺序，返回给定集合的最小元素
• reverse方法，反转集合中的元素

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(9);
list.add(3);
Collections.reverse(list);
for(Integer o : list) {
    System.out.println(o);
}

• sort方法，根据元素的自然顺序，队指定列表按升序进行排序

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(9);
list.add(3);
//如果需要，也可以在第二个参数位置传一个比较器对象
//Collections.sort(list,c);
Collections.sort(list);
for(Integer o : list) {
    System.out.println(o);
}

• shuffle方法，使用默认随机源对指定列表进行置换

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(9);
list.add(3);
Collections.shuffle(list);
for(Integer o : list) {
    System.out.println(o);
}

• addAll方法，往集合中添加一些元素

List<Integer> list = new ArrayList<>();
//注意，addAll的第二个参数，是可变参数
Collections.addAll(list,1,3,5,7);
for(Integer o : list) {
    System.out.println(o);
}

• synchronized相关方法，将非线城安全的集合转为线城安全
  • synchronizedCollection：把非线程安全的Collection类型集合，转为线程安全的集合
  • synchronizedList：List –> 线程安全
  • synchronizedSet: Set –> 线程安全
  • synchronizedMap：Map –> 线程安全

public class Test09_Collections {
    public static void main(String[] args) {
        //1.准备集合并添加元素
        //List<Integer> list = Arrays.asList(5,3,4,2,2,7);
        List<Integer> list = new ArrayList<>();
        //addAll 往集合中添加多个元素
        Collections.addAll(list,5,3,4,2,2,7);
        System.out.println(list);
        //2.max 获取最大值【默认采用自然排序】
        Integer max = Collections.max(list);
        System.out.println("max: " + max);
        //3.min 获取集合最小值
        Integer min = Collections.min(list);
        System.out.println("min: " + min);
        //4.reverse 反转
        Collections.reverse(list);
        System.out.println(list);
        //4.sort 排序【按照 传入的排序算法 进行排序】
        Comparator<Integer> comp = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                // 逆序
                return o2-o1;
            }
        };
        //注意：排序不会删除集合中的元素
        Collections.sort(list,comp);
        System.out.println("逆序: " + list);
        //5.shuffle 随机打乱
        Collections.shuffle(list);
        System.out.println("打乱: " + list);
        //6.sort 排序【默认自然排序】
        Collections.sort(list);
        System.out.println("自然排序： " + list);
        //7.fill 填充
        Collections.fill(list, 20);
        System.out.println("after fill: " + list);
        //8.将ArrayList【线程不安全】的集合 转换成 线程安全集合
        //List<Integer> list2 =
        Collections.synchronizedList(list);
    }
}

注意：Collections.sort排序不会删除集合中的元素。

❤️❤️❤️忙碌的敲代码也不要忘了浪漫鸭！

大鹏一日同风起，扶摇直上九万里。💪