1.集合的体系特点

1.1、集合体系结构

• Collection单列集合，每个元素只包含一个值
• Map双列集合，每个元素包含两个值（键值对）

1.2、Collection集合体系

【Collection】集合特点

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

public class Test {
    public static void main(String[] args) {
        //ArrayList：有序 可重复 存在索引
        Collection list = new ArrayList();
        list.add("Mybatis");
        list.add("Spring");
        list.add("HTML");
        list.add(20);
        list.add(20);
        list.add(false);
        list.add(true);
        System.out.println(list);
        System.out.println("----------------------");
        //HashSet：无需 无重复 无索引
        Collection set = new HashSet();
        set.add("Mybatis");
        set.add("Spring");
        set.add("HTML");
        set.add(20);
        set.add(20);
        set.add(false);
        set.add(true);
        System.out.println(set);
    }
}

1.3、泛型

• 集合都是泛型的形式，可以在编译阶段约束集合只能操作某种数据类型或引用类型

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

• 集合中要存基本数据类型的解决方法：

  • 包装类

2.Collection集合常用API

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

public class Test {
    public static void main(String[] args) {
        //ArrayList：无需 不重复 五索引
        //1.添加元素，添加成功返回true
        Collection<String> list = new ArrayList<>();
        list.add("Java");
        list.add("MyBatis");
        list.add("Java");
        list.add("HTML");
        list.add("浩楠");
        System.out.println(list);
        //2.清空集合的元素
        //list.clear();
        //System.out.println(list);
        //3.判断集合是否为空，是空返回true，反之false
        System.out.println(list.isEmpty());
        //4.获取集合的大小
        System.out.println(list.size());
        //5.判断集合中是否包含某个元素
        System.out.println(list.contains("浩楠"));
        //6.删除某个元素（如果有多个重复元素，删除前面的第一个）
        System.out.println(list.remove("Java"));//true
        System.out.println(list.remove("java"));//false
        //7.把集合转成数组并输出
        Object[] array = list.toArray();
        System.out.println(Arrays.toString(array));
        System.out.println("----------------拓展----------------");
        //API:list.addALL
        Collection<String> list1 = new ArrayList<>();
        list1.add("Java");
        list1.add("浩楠");
        list1.add("程明辉");
        Collection<String> list2 = new ArrayList<>();
        list2.add("李泽");
        list2.add("吴赛");
        list1.addAll(list2);
        System.out.println(list1);
        System.out.println(list2);
    }
}

3.Collection集合的遍历方式

3.1、方式一：迭代器

• 概述
  • 遍历就是一个一个的把容器中的元素访问一遍
  • 迭代器在Java中代表的是Iterator，迭代器是集合的专用遍历方式
• Collection集合获取迭代器

• Iterator中的常用方法

public class Test {
    public static void main(String[] args) {
        Collection<String> list = new ArrayList<>();
        list.add("Java");
        list.add("马浩楠");
        list.add("程明辉");
        list.add("李泽");
        list.add("吴赛");
        //1.得到当前集合的迭代器
        Iterator<String> i = list.iterator();
        //2.定义循环，使用方法遍历数据
        while(i.hasNext()){
            System.out.println(i.next());
        }
    }
}

3.2、方式二：foreach/增强for循环

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

• 修改第三方变量的值不回影响到集合中的元素

public class Test {
    public static void main(String[] args) {
        Collection<String> list = new ArrayList<>();
        list.add("Java");
        list.add("马浩楠");
        list.add("程明辉");
        list.add("李泽");
        list.add("吴赛");
        //使用增强for来遍历数组或集合
        for(String ele:list){
            System.out.println(ele);
        }
    }
}

3.3、方式三：lambda表达式

• Lambda表达式遍历集合
  • 得益于JDK 8开始的新技术Lambda表达式，提供了一种更简单，更直接的遍历集合的方式
• Collection结合Lambda遍历的API

public class Test {
    public static void main(String[] args) {
        Collection<String> list = new ArrayList<>();
        list.add("Java");
        list.add("马浩楠");
        list.add("程明辉");
        list.add("李泽");
        list.add("吴赛");
        //使用Lambda表达式遍历集合
        /*list.forEach(new Consumer<String>() {
            @Override
            public void accept(String s) {
                System.out.println(s);
            }
        });*/
        //简化
        /*list.forEach((String s)->{
            System.out.println(s);
        });*/
        //再简化
        //list.forEach(s -> System.out.println(s));
        //再再简化
        list.forEach(System.out::println);
    }
}

4.Collection集合存储自定义类型的对象

【需求】：某电影院系统需要在后台存储下述三部电影，然后一次展示出来

• Movie

public class Movie {
    private String name;
    private double score;
    private String actor;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getScore() {
        return score;
    }

    public void setScore(double score) {
        this.score = score;
    }

    public String getActor() {
        return actor;
    }

    public void setActor(String actor) {
        this.actor = actor;
    }

    public Movie() {
    }

    public Movie(String name, double score, String actor) {
        this.name = name;
        this.score = score;
        this.actor = actor;
    }
}

• Test

public class Test {
    public static void main(String[] args) {
        Collection<Movie> movies = new ArrayList<>();
        movies.add(new Movie("《你好，李焕英》",9.5,"张小斐，嘉玲，沈腾"));
        movies.add(new Movie("《唐人街探案》",8.5,"王宝强，刘昊然"));
        movies.add(new Movie("《刺杀小说家》",8.6,"雷佳音，杨幂"));
        //遍历
        for (Movie movie : movies) {
            System.out.println("片名："+movie.getName());
            System.out.println("评分："+movie.getScore());
            System.out.println("演员："+movie.getActor());
            System.out.println("-----------------------------");
        }
    }
}

• 内存图

5.常见数据结构

5.1、数据结构概述、栈、队列

• 数据结构概述
  • 数据结构是计算机底层存储、组织数据的方式，是指数据互相之间是以什么方式排列在一起
  • 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率
• 常见的数据结构
  • 栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树..
• 栈数据结构的执行特点
  • 后进先出，先进后出（压子弹）
• 队列数据结构
  • 先进先出，后进后出（排队）

5.2、数组

• 查询速度快
  • 查询数据通过地址和索引定位，查询任意数据耗时相同
• 删除效率低
  • 要将原始数据删除，同时后面每个数据前移
• 添加效率极低
  • 添加位置前，每个数据后移，再添加元素

5.3、链表

• 链表中的元素是再内存中不连续存储的，每个元素节点包含数据值和下一个元素的地址

• 链表查询慢，无论查询哪个数据都要从头开始找
• 链表增删相对较快

5.4、二叉树、二叉查找树

• 二叉树概述

• 特点

  • 只能由一个根节点，每个节点最多支持两个直接子节点
  • 节点的度：节点拥有的子树的个数，二叉树的度不大于2，叶子节点度为0的节点，也称之为终端节点
  • 高度：叶子节点的高度为1，叶子节点的父节点高度为2，以此类推
  • 层：根节点在第一层，以此类推
  • 兄弟节点：拥有共同父节点的节点互称为兄弟节点

• 二叉查找树

  • 每个节点上最多有两个子节点
  • 左子树上所有节点的值都小于根节点的值
  • 右子树上所有节点的值都大于根节点的值
• 二叉查找树添加节点
  • 小左，大右，一样的不存

5.5、平衡二叉树【了解】

• 二叉查找树存在的问题
  • 7、10、11、12、13存入
  • 出现瘸子现象，导致查询的性能与单链表一样，查询速度变慢
• 平衡二叉树
  • 是在满足查找二叉树的大小规则下，让树尽可能矮小，以此提高数据的性能
• 平衡二叉树要求
  • 任意节点的左右两个子树的高度差不过1，任意节点的左右两个子树都是一颗平衡二叉树

• 平衡二叉树在添加元素后可能导致不平衡
  • 基本策略是进行左旋或者右旋保持平衡
• 平衡二叉树-旋转的四种情况
  • 左左
  • 左右
  • 右右
  • 右左

5.6、红黑树

• 概述
  • 红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构
  • 1972年出现，当时被称为平衡二叉B树，1978年被修改为“红黑树”
  • 每个节点可以是红或黑，红黑树不是通过高度平衡的，它的平衡是通过“红黑规则”进行实现

• 红黑规则

  • 每个节点可以是红也可以是黑，根节点必须是黑色
  • 如果某一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点 相连的情况）
  • 对每个节点，从该节点到其所有后代节点的简单路径上，均包含相同数目的黑色节点

• 多的看视频回顾。

6.List系列集合

6.1、List集合特点、特有API

• 集合特点
  • ArrayList、LinedList：有序，可重复，有索引
  • 有序：存储和取出的元素顺序一致
  • 有索引：可以通过索引操作元素
  • 可重复：存储的元素可以重复
• 集合特有方法

6.2、List集合的遍历方式

• 迭代器
• 增强for循环
• lambda表达式
• for循环（List集合存在索引）

6.3、ArrayList集合的底层原理

• ArrayList底层是基于数组实现的：根据索引定位元素快，增删需要做元素的移位操作
• 第一次创建集合并添加第一个元素的时候，在底层创建一个默认长度为10的数组

6.4、LinkedList集合

• 特点
  • 底层数据结构是双链表，查询慢，首尾操作极快，所有多了些首尾操作的特有API
• API方法

public class Test {
    public static void main(String[] args) {
        //1.创建一个ArrayList集合对象，并添加几条元素
        //List:有序，可重复，有索引
        List<String> list = new ArrayList<>();
        list.add("Java");
        list.add("HTML");
        list.add("马浩楠");
        list.add("程明辉");
        list.add("李泽");
        list.add("吴赛");
        //2.在某个索引位置插入元素
        list.add(2,"林燕");
        System.out.println(list);
        //3.根据索引删除元素，返回被删除元素
        System.out.println(list.remove(1));
        System.out.println(list);
        //4.根据索引获取元素
        list.get(3);
        //5.修改索引位置的元素值
        list.set(0,"嗯哈");
        System.out.println(list);
    }
}

• 双向链表

7.集合的并发修改异常问题

• 问题

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

• 存在问题的遍历方式

  • 迭代器遍历集合且直接用集合删除元素存在问题
  • 增强for循环遍历集合且直接用集合删除元素存在问题
• 不出问题的遍历方式
  • 迭代器遍历集合但是用迭代器自己的删除方法解决
  • for循环遍历并删除元素不会存在问题

public class Test {
    public static void main(String[] args) {
        //1.准备数据
        ArrayList<String> list = new ArrayList<>();
        list.add("马浩楠");
        list.add("Java");
        list.add("Java");
        list.add("程明辉");
        list.add("李泽");
        list.add("吴赛");
        //需求：删除全部Java信息
        //删除方式一：迭代器删除
        /*Iterator<String> iterator = list.iterator();
        while(iterator.hasNext()){
            String ele = iterator.next();
            if(ele.equals("Java")){
                //list.remove("Java");会报错
                iterator.remove();//使用迭代器删除当前位置元素，保证不后移
            }
        }*/
        //删除方式二：foreach遍历删除（存在bug）
        /*for (String s : list) {
            if("Java".equals(s)){
                list.remove("Java");
            }
        }*/
        //删除方式三：lambda表达式删除（存在bug）
        /*list.forEach(e->{
            if("Java".equals(e)){
                list.remove("Java");
            }
        });*/
        //删除方式四：for循环删除
        for (int i = 0; i < list.size(); i++) {
            if ("Java".equals(list.get(i))) {
                list.remove("Java");
                i--;//用此运算来防止后移
            }
        }
        System.out.println(list);
    }
}

8.泛型深入

8.1、泛型的概述和优势

• 概述
  • 泛型是JDK5中引入的特性，可以在编译阶段约束操作的数据类型，并进行检查
  • 格式：<数据类型>【泛型只能支持引用数据类型】
  • 集合体系的全部接口和实现接口都是支持泛型使用
• 好处
  • 统一数据类型
  • 把运行时间的问题提到了编译期间，避免了强制类型转换可能出现的异常，因为编译阶段类型就能确定下来

public class Test {
    public static void main(String[] args) {
        String[] names = {"马浩楠","程明辉","李泽","吴赛"};
        printArray(names);
        Integer[] ages = {21,22,80,13};
        printArray(ages);
    }
    public static <T>void printArray(T[] arr){
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]).append(i == arr.length-1 ? "" : ", ");
        }
        sb.append("]");
        System.out.println(sb);
    }
}

8.2、自定义泛型类

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

• 作用：编译阶段可以指定数据类型，类似于集合的作用

• 案例

  • 模拟ArrayList集合自定义一个集合，完成添加和删除功能的泛型设计

public class MyArrayList<T> {
    public static void main(String[] args) {
        MyArrayList<String> mylist = new MyArrayList<>();
        mylist.add("马浩楠");
    }
    public void add(T t){
        System.out.println("添加"+t);
    }
    public void remove(T t){
        System.out.println("删除");
    }
}

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

8.3、自定义泛型接口

• 格式：修饰符 interface 接口名称<泛型变量>{}
• 作用：泛型接口可以让实现类选择当前功能需要操作的数据类型
• 案例
  • 提供一个接口可以约束一定要完成的数据（学生，老实）的增删改

Data接口

public interface Data<E> {
    void add(E e);
    void delete(int id);
    void update(E e);
    void selectById(int id);
}

Student实现类

public class Student implements Data<Student>{
    @Override
    public void add(Student student) {

    }

    @Override
    public void delete(int id) {

    }

    @Override
    public void update(Student student) {

    }

    @Override
    public void selectById(int id) {

    }
}

Teacher实现类

public class Teacher implements Data<Teacher>{
    @Override
    public void add(Teacher teacher) {

    }

    @Override
    public void delete(int id) {

    }

    @Override
    public void update(Teacher teacher) {

    }

    @Override
    public void selectById(int id) {

    }
}

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

8.4、泛型通配符、上下限

• 通配符：?

  • ? 可以在 “使用泛型” 的时候代表一切类型
  • B T K V 是在定义泛型的时候使用

• 案例

  • 开发一个极品飞车的游戏，所有汽车都能一起参与比赛

public class Demo {
    public static void main(String[] args) {
        ArrayList<Ben> bens = new ArrayList<>();
        bens.add(new Ben());
        bens.add(new Ben());
        bens.add(new Ben());
        go(bens);
        ArrayList<Bao> baos = new ArrayList<>();
        baos.add(new Bao());
        baos.add(new Bao());
        baos.add(new Bao());
        baos.add(new Bao());
        go(baos);
        ArrayList<Dog> dogs = new ArrayList<>();
        dogs.add(new Dog());
        dogs.add(new Dog());
        dogs.add(new Dog());
        //go.add(dogs);//不能使用，不符合逻辑，因此加上? extends Car限制引用类型

    }
    //开始比赛
    public static void go(ArrayList<? extends Car> ele){

    }
}
class Ben extends Car{

}
class Bao extends Car{

}
class Car{

}
class Dog{

}

• 泛型的上下限
  • ? extends Car：？必须的Car或者其子类 【泛型上限】
  • ? super Car：？必须是Car或者其父类 【泛型下限】